読者です 読者をやめる 読者になる 読者になる

shokosブログ

プログラミング

Haskellでワンライナーで書いたフィボナッチ数列がなにをやっているのか

shokos Advent Calendar 2012六日目。

ほとんどHaskell触ったことない人向けです。
社内勉強会で使おうと思っているネタ。


Haskellフィボナッチ数列を定義すると、こうなります。

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

何をやっているのか、式の左側から説明していきます。


コロンは、要素をリストの先頭にくっつけます。
1:1:~は、[1,1,~]を示しています。


zipWithは

zipWith f リストA リストB

リストAとリストBの要素を、それぞれ先頭から順にもってきて、fを適用します。
片方が空リストになったらストップです。


tailはリストの先頭を取り除きます。
つまり、zipWith (+) fib (tail fib)は、fib自身と、fibから先頭を除去したものを、先頭から順番に持ってきて足し算しています。


たとえばこんな感じ。

zipWith (+) [1,1,2,3] (tail [1,1,2,3])
↓
zipWith (+) [1,1,2,3] [1,2,3])
↓
[2,3,5]

すごい!フィボナッチ数列の性質ができた!
これに、初期値1:1:を与えているので、あとは再帰して無限フィボナッチ数列の完成です!