竹内関数

未踏ユースPMの竹内先生はたらいまわしの名人らしい。御本人じゃないのに聞いちゃったらどうしようと結構悩んだ。
tak 12 6 0 を計算。

tak x y z
 | x <= y = y
 | otherwise = tak (tak (x-1) y z)
                   (tak (y-1) z x)
                   (tak (z-1) x y)

(0.02 secs, 528808 bytes)
遅延評価の威力を体感するために `seq` をいれてみる。

tak x y z
 | x <= y = x `seq` z `seq` y
 | otherwise = tak (tak (x-1) y z)
                   (tak (y-1) z x)
                   (tak (z-1) x y)

とすると、(46.00 secs, 645222988 bytes)
さらに、

tak x y z
 | x <= y = x `seq` z `seq` y
 | otherwise = a `seq` b `seq` c `seq` tak a b c
   where a = (tak (x-1) y z)
         b = (tak (y-1) z x)
         c = (tak (z-1) x y)

(36.99 secs, 303765192 bytes)
ありゃ、速くなった。memoしてないのに何で(顔?
もしかすると gc のタイミングがあるかな。