竹内関数
未踏ユース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 のタイミングがあるかな。