日: 2006年4月17日

cf. id:pylet:20060416

最近のトレンドとしては、やっぱりHello, Woldの次はフィボナッチ数列ですよね(!?)

そうそう，フィボナッチ数列だよ。Haskell なら１行で書ける……って，本に書いてあったものを自慢しても仕方がないので，それを見る前に自分で書いたものをさらしておく。

fib 0 = 1
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

*Main> fib 10
89

これは id:pyletさんのfib1（再帰版）に相当する。
リストを得るには関数をもうひとつ。

fibNumbers 0 = [1]
fibNumbers 1 = [1,1]
fibNumbers n = fibNumbers (n-1) ++ [fib n]

これで第n項までのリストが得られる（初項を第0項とする）。

*Main> fibNumbers 10
[1,1,2,3,5,8,13,21,34,55,89]

ちなみに，ループ版は Haskell ではできない。たぶん。

で，こうすると１行で書ける。

fibonacci = 1:1:zipWith (+) fibonacci (tail fibonacci)

これだけ。これでフィボナッチ数列のリストが得られる。注目すべきなのは得られるリストが無限リストだということ。ほっとくといくらでも数字をはき続ける（まぁ，そのうちリソースを食いつぶして止まるんだろうけど）。

*Main> fibonacci
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,
28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,570
2887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,4
33494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,125862
69025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,
365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881
,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723
460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515
533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,89
44394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721
611591,99194853094755497,160500643816367088,259695496911122585,42019614072748967
（以下略）

第10項がほしければこうする。

*Main> fibonacci !! 10
89

id:nobsun さんからコメントをもらった。ありがとうございます。

fib n = fibIter 1 1 n
  where fibIter a b 0 = a
    fibIter a b n = fibIter b (a+b) (n-1)

（※ちょっと変えました）

*Main> map fib [1..10]
[1,2,3,5,8,13,21,34,55,89]

id:nobsun さんはこれ（↑）が id:pyletさんとこのループ版と同等だというのだけど，むしろ反復版（↓これ）と同等じゃないのかなぁ。

def fib3_iter(a, b, i, n):
    if i == n:
        return a
    else:
        return fib3_iter(b, a + b, i + 1, n)

def fib3(n):
    return fib3_iter(1, 1, 0, n)

このPythonの関数（メソッド？）はカウンタに変数 i を使っているけど，重要なのは n と i の差 n-i なんだから n-i -> n に置き換えて n 自身をカウンタに使えば i をなくせる。内側のfib3_iterの引数は n-(i+1) = (n-i)-1 -> n-1 と置き換えられるから

def fib3_iter(a, b, n):
    if n == 0:
        return a
    else:
        return fib3_iter(b, a + b, n - 1)

def fib3(n):
    return fib3_iter(1, 1, n)

これならまさしく上のHaskellと同じだ。

あー，でも，そうか。既知の第0項と第1項をもとにして第n項まで頭から順に計算していく，という点ではどっちも同等だといえるのか。
いや，まて。再帰してる反復版ではスタックを積まなきゃいけないけどループ版ではいらないはずだな。
いやいや，遅延評価するからいらないのか？……違うか？
だめだ。わかんなくなった。