Haskellで有名アルゴリズム実装（2）

2日目。フィボナッチ数列について。

フィボナッチ数列をどこで使うのか、何なのか？については、昔書いてるので以下のpost参照のこと。

• フィボナッチあれこれ

Haskellでフィボナッチ数列を書いてみます。いろいろ書き方があるみたいです。

まず、自分がぱっと思いついた書き方は以下のとおりです。

fib a b = a : fib b (a+b)

遅延評価のおかげで、フィボナッチ数列を無限番目の項まで定義できます。使うときには、実際に必要な項までを取り出せばよいです。

例えば、30番目の項までを出力させたかったら、以下のようにします。

main = print $ take 30 $ fib 1 1

次に、一般的（？）な書き方を紹介します。

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

これはクールな書き方ですね。第3項目を知るには、第1項、第2項が分かればOK。第4項目を知るには、第2項、第3項が分かればOK、・・・・。となり、一般的に、第n項を知るには第n-1項、第n-2項まで分かればOKとなっています。

この書き方も、値は必要な時点で分かっていればよいという遅延評価のメリットを活かしています。

Haskell's cool!

Haskellのページに戻る。