フィボナッチ数列

• たらい回し関数　http://d.hatena.ne.jp/rahaema/20090130
• たらい回し関数(続き…)　http://d.hatena.ne.jp/rahaema/20090203
• たらい回し関数(続・続き…)　http://d.hatena.ne.jp/rahaema/20090205

ここ何日(上記)か，たらい回し関数(竹内関数)を通して，遅延評価の効果についていろいろと勉強することができました。

今日は，フィボナッチ数列です。
以下のように，普通の再帰で書くと，50項目を求める位から相当な時間がかかります。

fibonacci :: Integer -> Integer
fibonacci n
    | n == 1 = 1
    | n == 2 = 1
    | otherwise = fibonacci (n-2) + fibonacci (n-1)

main = print $ fibonacci 50

しかし，以下のように，遅延評価を用いると，一瞬のうちに答えを求めてくれます。

fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)

main = print $ last $ take 50 fibonacci 

実行結果

$ time runhaskell fibo.hs
12586269025

real 0m0.151s
user 0m0.110s
sys 0m0.037s

遅延評価，すばらしい。

追記(2009/2/9)

上記の記述は間違っています。id:SaitoAtsushiさんが丁寧に説明されています。
http://d.hatena.ne.jp/SaitoAtsushi/20090208/1234085992