cf. id:pylet:20060416
最近のトレンドとしては、やっぱりHello, Woldの次はフィボナッチ数列ですよね(!?)
そうそう,フィボナッチ数列だよ。Haskell なら1行で書ける……って,本に書いてあったものを自慢しても仕方がないので,それを見る前に自分で書いたものをさらしておく。
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 ではできない。たぶん。
で,こうすると1行で書ける。
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