Haskell入門 フィボナッチ数列を末尾再帰で速くする

参考ページ
お気楽 Haskell プログラミング入門

-- fibo.hs

-- 普通
fibo :: Integer -> Integer
fibo n =
  if n == 0 || n == 1 then n
  else fibo (n - 1) + fibo (n - 2)

-- 末尾再帰
fibo_tail :: Integer -> Integer
fibo_tail n = fibo_sub n 0 1
  where
    fibo_sub 0 a _ = a
    fibo_sub n a b = fibo_sub (n - 1) b (a + b)

実行

Prelude> :set +s

Prelude> :l fibo.hs

*Main> fibo 30
832040
(3.20 secs, 769,826,264 bytes)

*Main> fibo_tail 30
832040
(0.01 secs, 72,976 bytes)