fib = 0 : 1 : zipWith (+) fib (tail fib)
こちらの記事で紹介されていた キモいフィボナッチ数列がやっとの事で理解できたので, これ見よがしにドヤ顔で解説をしたいと思います.
ただ, 僕はこれを理解するので精一杯な初心者ですので, もし間違いやより良い表現等があれば教えて頂けると幸いです.
まずは見てみる
まず問題のフィボナッチ数列はこちら
fib :: Num a => [a]
fib = 0 : 1 : zipWith (+) fib (tail fib)
ここで注意して頂きたい点があります.
このfib
ですが, このままだと動作しません. 実は僕は最初ここで躓いてしまい, これより先に進む事ができませんでした. 雑魚とか言わないで
このfib
というのは, 関数ではなく定数です(引数を取らない関数である多相定数というやつなのかなーと思っていますが, 多相定数が何なのかイマイチ理解できていません. 教えてエロい人!).
再帰的に定義をしていますし, いつもの関数定義のような形で書いているのでパッと見関数っぽいですが, 定数です.
じゃあ中身は一体どうなってるのさ
fib
の中身は無限リストになっています.
Haskellでは, その値が本当に必要になるまで評価を行わない遅延評価(lazy evaluation)が採用されています. 無限の長さのリストが扱えるのは, LazyなHaskellだからこそできる芸当ですね. どこぞの軽音楽部とは違います
はすける「Please say me "You are lazy!"」
話を元に戻しましょう.
無限リストfib
の中から値を取り出したい場合は, リストの先頭からn
個の要素を取り出したリストを返す関数take n
を用いて,
print $ take 20 fib
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]
このように, フィボでナッチなリストを, あなたのメモリと整数型の上限値が許す限り取り出すことができます.
いよいよ解読開始
ではまず定義を改めて確認していきます.
fib :: Num a => [a]
fib = 0:1:zipWith (+) fib (tail fib)
fib :: Num a => [a]
というのは単純で, fib
はNum型クラスの任意のインスタンスa
のリストを返します, という意味になります.
0:1:
というのは[0, 1]++
(リスト[0, 1]と, その後ろのリストを連結する)と同じ意味です.
関数zipWith
は二引数関数f, リストa, bを引数に取り, a, bの要素を先頭から順にfで合成したリストを返す関数です.
例えばzipWith (+) [1, 2, 3] [4, 5, 6]
だと,
[1, 2, 3]
+ + +
[4, 5, 6]
↓ ↓ ↓
[5, 7, 9]
のようになり, [5, 7, 9]
を返します.
要するに, fib
は, [0, 1]というリストに, fib
とtail fib
の各要素をそれぞれ足したリストを連結した無限リストです
fib
の初期段階で分かっている要素は[0, 1...]
tail fib
の初期段階で分かっている要素はfib
から先頭要素を除いた[1...]
もうお気付きの方も多いかと思いますが, その通りです. この無限リストは, フィボナッチ数列の最初の2つの要素に, それをずらした数列2つの要素を足し合わせたリストを連結したものになっています.
フィボナッチ数列は先頭2つの要素さえあれば後は分かりますから, これで求める事が出来るのです.
これ見よがしの解説
まずは第1段階です.
上に並んだ2つが
fib [0, 1...]
+ +
tail fib [1...]
↓
fib [0, 1]++[1...]
3番目の要素が1である事が分かったので, リストの末尾に追加します.
fib [0, 1, 1...]
+ + +
tail fib [1, 1...]
↓ ↓
fib [0, 1]++[1, 2...]
4番目の要素が2である事が分かったので, リストの末尾に追加.
fib [0, 1, 1, 2...]
+ + + +
tail fib [1, 1, 2...]
↓ ↓ ↓
fib [0, 1]++[1, 2, 3...]
5番目の要素が3である事が分かったので(ry
fib [0, 1, 1, 2, 3...]
+ + + + +
tail fib [1, 1, 2, 3...]
↓ ↓ ↓ ↓
fib [0, 1]++[1, 2, 3, 5...]
6番目の要素が5である(ry
fib [0, 1, 1, 2, 3, 5...]
+ + + + + +
tail fib [1, 1, 2, 3, 5...]
↓ ↓ ↓ ↓ ↓
fib [0, 1]++[1, 2, 3, 5, 8...]
よって, 以下のようなリストになります.
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181...以降無限に続く
以上です
Haskellを思い通りに書けるようになりたいけど, 読むのが精一杯でいざ実装しようとなると全く書き方(文法ではなく考え方)が分からない今日此の頃. 誰か何かおすすめの方法等あれば教えてください.