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