Namaran

Code daily. Without assist.

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つと、まだ読んでいないリストの先頭だけです。

  1. GHC 9.10 に付く base 4.20 からは Prelude も foldl' を公開しているので、検証に使った GHC 9.14 では import が要りません。それより前の GHC では import Data.List (foldl') を足します。