前回のフィボナッチ数列の記事に, 匿名さんからコメントをいただきまして.
> fib = 0:1:zipWith (+) fib (tail fib)
( http://chomado.ciao.jp/programming/haskell-フィボナッチ数列/#comment-487 )
おおおおお一行や!!! これはキモそうだ!!(大興奮)
zipWith関数 … 二引数関数を使って二つのリストを混ぜ合わせる関数
(＊ [ c ](スペース無し) って書くと, 入れてるプラグインの影響で, C言語だと認識されてしまうので, あえて上では[ｃ(全角)]と書いています )
そんで,
zipWith (+) fib (tail fib)
ここは何をしているかというと…
うーん…
難しい…
最初 fib の中身は
[0, 1, …]（2番目までしか分かってないリスト）
だけで, そこに zipWith (+) fib (tail fib) をくっつけるわけだけど,
この状態での tail fib は [1] だから,
zipWith (+) fib [1]
で,
えーーーーーっと,
ああああ混乱してきた!!!!!! わかんない!!! 難しい!!! あとで考える!!!＞＜
ーーー 追記 ーーーー
Twitterで助言をいただきました(T_T)ありがとうございます
(あと, 理解した後で見てみたら, 何もキモくなくて, 自然なコードだと思った)
@chomado 0,1個目は既に定義済みなので、2個目以降を順に一つずつ計算してみましょう。zipWithの定義から
fib !! 2 = fib !! 0 + fib !! 2
fib !! 3 = fib !! 1 + fib !! 2
…
となりますよね。
— Yb@目指せ量子力学充 (@kunio_Yb) 2014, 11月 4
数列の足し算
fib = 0 :: 1 :: 1 :: 2 :: 3 :: …
+ tail fib = 1 :: 1 :: 2 :: 3 :: 5 :: …
–
1 :: 2 :: 3 :: 5 :: 8 :: …
— Masaki Hara (@qnighy) 2014, 11月 4
@chomado fib=[f0,f1,f2,..]だよね．tail fib=[f1,f2,f3,..]だよね．zipWith(+)fib(tail fib)=[f0+f1,f1+f2,f2+f3,..]=[f2,f3,f4,..]だよね．f0=0，f1=1だよね．だよね 🙂
— Nobuo Yamashita (@nobsun) 2014, 11月 4
自分を信じるのが再帰の基本
— ギターと3Dはじめました (@fumieval) 2014, 11月 4
@chomado @fumievalさんの言うとおりです．とりあえずできたことにして．そんでもって，できてたとしたらどうなっているはずだろうかと考えてみましょう．RT @fumieval: 自分を信じるのが再帰の基本
— Nobuo Yamashita (@nobsun) 2014, 11月 4
@chomado 3項目以降は必要になるまで計算されないので、再帰呼び出しされていても、最初から全部わかっている必要はない
— なべ改 (@_nabbe) 2014, 11月 4
@chomado 最初の2項を明示的に定義して、そのあとは「直前の2項の和」を求めてるだけですよ
— なべ改 (@_nabbe) 2014, 11月 4
fib = 0:1:zipWith (+) fib (tail fib)
の
zipWith (+) fib (tail fib)
これは,
zipWith (+) (0:1…) (1:1…)
=
[(+) 0 1, (+) 1 1, …]
@func_hs @chomado このfib関数は「ずらして重ねる」ってイメージでしのいだ
— ちゅーん (@its_out_of_tune) 2014, 11月 4
無限ループにならないの?
遅延評価だから大丈夫なんだって!
take 10 fib
とかで値を取り出せる!
@chomado 無限ループですが、リストの一つ一つの値は計算できます。他の型も説明されていますが、zipWith (+) (1:1…) (1:2…) = 1 + 1 : zipWith (+) … (2:..)という計算で、'…'の部分を「自給自足」しているのです
— ギターと3Dはじめました (@fumieval) 2014, 11月 4
余談
秀逸なホモ投下
@chomado 父親と息子が禁断のホモで孫を作り、息子と孫がまた禁断のホモで（ｒｙといったように、一世代ずつ生まれては子を作ることを順番に繰り返すイメージ
— 鶏川 ソルト (@tori_kawa_solt) 2014, 11月 4
@chomado 例えば4代目ホモが見たければこんな感じでしょうか。
1. 1代目(0氏)は固定
2. 2代目(1氏)は固定
3. 3代目、1代目と2代目が子作りして0氏+1氏で1君が誕生
4. 4代目、2代目と3代目が子作りして1氏+1君で2様が誕生
5. 4代目は2様だ!!
— 鶏川 ソルト (@tori_kawa_solt) 2014, 11月 4
@chomado その為の遅延評価ではないでしょうか。フィボナッチホモの場合、実は4代目ホモを調べるために3代目ホモが"必要になるまで"1代目と2代目の子作りは止められているのです。悪魔のシステムなのです。
— 鶏川 ソルト (@tori_kawa_solt) 2014, 11月 4
