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:を与えているので、あとは再帰して無限フィボナッチ数列の完成です！