Namaran

Code daily. Without assist.

2026-10-04

Tally.hs

import Data.List (foldl')
import qualified Data.Map as M

tally :: [Int] -> M.Map Int Int
tally = foldl' (\m x -> M.insertWith (+) (x `mod` 3) 1 m) M.empty

main :: IO ()
main = print (tally [1 .. 3000000])

tally は、整数を3で割った余りごとに件数を数えるつもりの関数です。foldl' で1件ずつ数えるので、メモリは入力の長さによらずほぼ一定で済むはずです。引数も標準入力も使いません。出力は本来どおり fromList [(0,1000000),(1,1000000),(2,1000000)] ですが、いまは手元で最大常駐メモリが約340MBに達します。正しく直せば、同じ出力のまま約9MBで終わります。

Answer

Wrong

import qualified Data.Map as M

Data.Map は、値を遅延評価する Data.Map.Lazy と同じものです。M.insertWith (+) k 1 は、キーがすでにあると値を 1 + 古い値 というサンクに置き換えるだけで、足し算はしません。foldl' が1歩ごとに評価するのは表そのもの(弱頭部正規形)までで、表の中の値には触れません。そのため各キーの値は100万段の足し算のサンクになり、最後に print が値を表示するときに初めてまとめて評価されます。メモリを使っているのは、この約300万個のサンクです。

Right

import qualified Data.Map.Strict as M

Data.Map.Strict の insertWith は、新しい値を表に入れる前に弱頭部正規形まで評価します。Int の弱頭部正規形は数そのものなので、各キーの値はいつも評価済みの数で、サンクは溜まりません。2つのモジュールは関数の名前も型も同じなので、変えるのは読み込む1行だけです1。

  1. 2つのモジュールの Map は同じ型なので、片方で作った表をもう片方の関数に渡せます。違うのは、関数が値を評価するかどうかだけです。