2026-11-09
SumCount.hs
sumCount :: [Int] -> (Int, Int)
整数のリストを先頭から一度だけたどり、要素の個数と合計の組 (個数, 合計) を返す sumCount を書いてください。リストは巨大なファイルから少しずつ読み出したもので、全体はメモリに収まりません。たどり終えた要素から捨てられ、要素数が増えても使うメモリが増えないように書きます。空リストなら (0, 0) です。
入力例 1
sumCount [3, 1, 4]
出力例 1
(3,8)
入力例 2
sumCount [-5]
出力例 2
(1,-5)
入力例 3
sumCount []
出力例 3
(0,0)
Reference
Reference
sumCount :: [Int] -> (Int, Int)
sumCount = foldl' step (0, 0)
where
step (n, s) x = let n' = n + 1; s' = s + x in n' `seq` s' `seq` (n', s')
(length xs, sum xs) と書くと、リストを2回たどります。1回目をたどっている間も、2回目のために xs の先頭から全体を残しておく必要があるので、要素はいつまでも捨てられません。そこで個数と合計を組にして持ち、foldl' で1回だけたどります。foldl' は1歩ごとに途中の値を評価しますが、評価は一番外側の構築子までで止まります。組なら (,) ができた時点で止まり、中の n + 1 や s + x は計算されないまま、前の計算を指す未評価の式が要素の数だけつながっていきます。step では seq で n' と s' を先に評価してから組を作るので、組の中身はいつも計算済みの数です。これは参考実装で、唯一の正解ではありません。foldl' は Haskell 2010 の Prelude には無く、Data.List にあります1。
入力例1では、組は (0, 0) から (1, 3)、(2, 4)、(3, 8) と進みます。入力例2は1歩で (1, -5) になり、空リストの入力例3は1歩も進まないので、初期値の (0, 0) がそのまま返ります。どの時点でもメモリにあるのは組1つと、まだ読んでいないリストの先頭だけです。
- GHC 9.10 に付く base 4.20 からは Prelude も
foldl'を公開しているので、検証に使った GHC 9.14 では import が要りません。それより前の GHC ではimport Data.List (foldl')を足します。