Haskellのキモいフィボナッチ数列がやっと理解できたからこれでもかという程に細かく説明してみた #Haskell

#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を用いて,

このように, フィボでナッチなリストを, あなたのメモリと整数型の上限値が許す限り取り出すことができます.

##いよいよ解読開始

ではまず定義を改めて確認していきます.

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]だと,

のようになり, [5, 7, 9]を返します.

要するに, fibは, [0, 1]というリストに, fibとtail fibの各要素をそれぞれ足したリストを連結した無限リストです

fibの初期段階で分かっている要素は[0, 1...] tail fibの初期段階で分かっている要素はfibから先頭要素を除いた[1...]

もうお気付きの方も多いかと思いますが, その通りです. この無限リストは, フィボナッチ数列の最初の2つの要素に, それをずらした数列2つの要素を足し合わせたリストを連結したものになっています. フィボナッチ数列は先頭2つの要素さえあれば後は分かりますから, これで求める事が出来るのです.

##これ見よがしの解説

まずは第1段階です. 上に並んだ2つが

3番目の要素が1である事が分かったので, リストの末尾に追加します.

4番目の要素が2である事が分かったので, リストの末尾に追加.

5番目の要素が3である事が分かったので(ry

6番目の要素が5である(ry

よって, 以下のようなリストになります.

##以上です

Haskellを思い通りに書けるようになりたいけど, 読むのが精一杯でいざ実装しようとなると全く書き方(文法ではなく考え方)が分からない今日此の頃. 誰か何かおすすめの方法等あれば教えてください.