Namaran

Code daily. Without assist.

2026-11-10

Counts.hs

import Data.IORef
import qualified Data.Map.Strict as Map

main :: IO ()
main = do
  ref <- newIORef Map.empty
  mapM_ (\x -> modifyIORef ref (Map.insertWith (+) (x `mod` 10) 1)) [1 .. 3000000 :: Int]
  counts <- readIORef ref
  print (Map.lookup 7 counts :: Maybe Int)

1から3000000までの整数を10で割った余りごとに数え、余りが7の個数を表示するプログラムです。出力はいまも本来の Just 300000 と一致しますが、最適化なしでビルドして +RTS -s で測ると、実行中に約240MBのデータが残り続け、プロセスは約560MBのメモリを使います。正しく直すと出力は同じまま、使うメモリは6MBほどに収まります。いまのままでは、件数に比例してメモリが増え、件数を増やすといずれメモリが尽きて止まります。

Answer

Wrong

  mapM_ (\x -> modifyIORef ref (Map.insertWith (+) (x `mod` 10) 1)) [1 .. 3000000 :: Int]

Data.Map.Strict の insertWith は、挿入するときに (+) の結果を評価するので、表の中に足し算の式が溜まることはありません。ただしそれは insertWith が実際に呼ばれたときの話です。modifyIORef ref f は、ref の中身 m を f m という未評価の式に置き換えるだけで、f を呼びません。300万回の modifyIORef のあと、ref に入っているのは表ではなく、insertWith の呼び出しが300万段入れ子になった1つの式です。

この式は、最後の print が表を必要としたときに初めて内側から順に計算され、そこでようやく1回ずつの insertWith が正格に値を足していきます。結果が正しいのはそのためで、溜まっていたのは表の値ではなく、表を作る処理のほうです。

Right

  mapM_ (\x -> modifyIORef' ref (Map.insertWith (+) (x `mod` 10) 1)) [1 .. 3000000 :: Int]

modifyIORef' は、新しい中身 f m を弱頭部正規形1まで評価してから書き込みます。Map の弱頭部正規形を求めるには insertWith を最後まで実行するしかないので、1回の modifyIORef' ごとに挿入が済み、正格な Map がその場で個数を足します。ref にはいつも10個の整数を持つ小さな表だけが入り、古い表はすぐに捨てられます。modifyIORef' は Haskell 2010 の報告書には無く、GHC に付く base の Data.IORef にあります。

  1. 弱頭部正規形(weak head normal form、WHNF)は、式を一番外側の構成子かラムダ式が見えるところまで評価した形です。Map は木の形全体が決まらないと一番外側の構成子も決まらないので、表を弱頭部正規形まで評価すると、それまでの挿入はすべて済みます。