2015-12-08

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 ...

まとめ：

あどけない話