Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

フィボナッチ数列

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

今日は,フィボナッチ数列です。
以下のように,普通の再帰で書くと,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