これはHaskellスペースリーク Advent Calendar 2015の8日目の記事です。
IOのコードは、普通に書けば末尾呼び出しの最適化が効く形になる。たとえば、こんな感じ:
foo :: Char -> String -> IO Int foo a b = do c <- bar a b zoo b c woo c woo :: Int -> IO Int woo c = do d <- goo c return $ d + 1
foo が woo を呼び出す時は、fooのフレームを忘れてしまってよい。IOの文脈で再帰関数を書く場合も末尾再帰で十分な場合が多い。
goo :: Int -> IO () goo 0 = return () goo n = do getChar >>= putChar goo (n - 1)
残念なことに、一見末尾再帰に見えるが実はそうなっていなくて、スペースリークするパターンが存在する。たとえば、bracket と組み合わせた場合だ:
boo n = bracket alloc free $ \res -> do ... boo (n - 1)
これは一見末尾再帰に見える。しかし、bracket の実装は、
bracket before after thing = mask $ \restore -> do a <- before r <- restore (thing a) `onException` after a _ <- after a return r
であり、頭の中でコードを展開してみれば、boo はまったく末尾再帰の形になってないことが分かるだろう。これを「にせ末尾再帰」と呼ぶことにする。にせ末尾再帰の他の例としては、finally が挙げられる。
coo n = do { ... ; coo (n - 1) } `finally` finalThing
これらに対処するには、(go や loop といった)末尾再帰のローカル関数を定義すればよい。
boo n = bracket alloc free $ go n where go 0 _ = return () go m res = do ...
まとめ: