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