Namaran

Code daily. Without assist.

2026-10-24

Counts.hs

counts :: Int -> [Int] -> [Int]

xs の要素はどれも 0 以上 n 未満の整数です。0 から n - 1 までの各値が xs に何回現れるかを、値の小さい順に並べた長さ n のリストを返す counts を書いてください。xs が空なら n 個の 0 を返し、n が 0 なら空リストを返します。xs の長さを m として、計算量は O(n + m) に収めます。

入力例 1

counts 4 [1, 3, 1, 0, 1]

出力例 1

[1,3,0,1]

入力例 2

counts 3 []

出力例 2

[0,0,0]
Reference
import Data.Array

counts :: Int -> [Int] -> [Int]
counts n xs = elems (accumArray (+) 0 (0, n - 1) [(x, 1) | x <- xs])

手続き型の言語なら、長さ n の配列を0で埋め、xs を1つずつ見て該当する要素を1増やします。Haskell で同じ形を書くには STUArray のような可変な配列が要りますが、ここで欲しいのは最後にできあがった表だけで、途中の状態を誰にも見せる必要がありません。Data.Array の accumArray を使うと、初期値で埋めてから添字と値の組を順に関数で畳み込むという作り方を、1つの式で書けます。

accumArray (+) 0 (0, n - 1) [(x, 1) | x <- xs] は、添字が 0 から n - 1 の配列を 0 で埋め、xs の各要素 x について添字 x の要素に (+) で 1 を足した配列を返します。返る配列は不変な値なので、作り終えたあとに誰かが中身を書き換える心配はありません。elems は要素を添字の順に並べたリストを返すので、これがそのまま答えです。n が 0 なら範囲 (0, -1) は空になり、空リストが返ります。

値ごとに length (filter (== i) xs) を数える書き方は、xs を n 回走査するので O(n × m) です。Data.Map に1つずつ insertWith する書き方は、1回の挿入ごとに O(log n) かかります。掲載したのは参考実装で、唯一の正解ではありません。runSTUArray で可変な配列を使って書いても、外から見れば同じ純粋な関数になります。