Namaran

Code daily. Without assist.

2026-09-29

Memo.hs

import Data.IORef
import qualified Data.Map as M

memo :: IORef (M.Map Int Integer) -> (Int -> IO Integer) -> Int -> IO Integer
memo ref f n = do
  cache <- readIORef ref
  case M.lookup n cache of
    Just v -> pure v
    Nothing -> do
      v <- f n
      writeIORef ref (M.insert n v cache)
      pure v

main :: IO ()
main = do
  ref <- newIORef M.empty
  let fib n
        | n < 2 = pure (toInteger n)
        | otherwise = (+) <$> memo ref fib (n - 1) <*> memo ref fib (n - 2)
  memo ref fib 10 >>= print
  readIORef ref >>= print . M.keys

memo は f n の結果を ref の Map に記録し、同じ n で2度目に呼ばれたら記録から返すつもりの関数です。実行すると、本来は 55 と [0,1,2,3,4,5,6,7,8,9,10] の2行を出力するはずですが、いまは 55 と [10] を出力します。値は正しいのに、記録が1件しか残りません。

Answer

Wrong

cache <- readIORef ref
case M.lookup n cache of
  Just v -> pure v
  Nothing -> do
    v <- f n
    writeIORef ref (M.insert n v cache)

memo は最初に読んだ cache で n が未記録だと確かめ、f n を実行してから、その同じ cache に n を足して書き戻します。Map は変更できない値なので、cache は読んだ時点の表のまま残ります。一方 fib は f n の中から memo を呼び直すので、f n を実行している間に、n より小さい引数の結果が ref に書き込まれていきます。

書き戻しは、その記録を知らない古い cache から作った表で ref を丸ごと置き換えるので、内側で入った記録が消えます。最後に書き込むのは一番外側の memo ref fib 10 で、この呼び出しが読んだのは空の表なので、残るのは 10 だけです。記録が消えても計算がやり直されるだけなので、値の 55 は正しく出ます。

Right

v <- f n
modifyIORef' ref (M.insert n v)

modifyIORef' は、書き込む時点の ref の中身に M.insert n v を適用します。f n の間に入った記録を残したまま n を足すので、11件すべてが残ります。最初に読んだ cache は n が未記録かどうかの判断にだけ使い、書き込む表の元にはしません1。

  1. 複数のスレッドから呼ぶなら atomicModifyIORef' を使います。modifyIORef' は読むことと書くことが不可分ではないので、1スレッドの再帰ならこれで足りますが、並行に呼ぶと、書き込みの間に割り込まれて同じように記録が消えます。