フィボナッチがあまりに遅いのでなんとかします．

昨日のフィボナッチはあまりに遅いのです．辛抱できません．遅い理由は簡単で，同じことを何度も何度もしてるからで，Perlの場合はハッシュのクロージャでキャッシュしてました．けど，Haskellじゃそういうことはきっとできません*1．

どうして同じことを繰り返すのかを考えたら，要は「上から計算するから駄目」なんだろうと思い至りました．人間が計算する場合，

0
1
0+1=1
1+1=2
1+2=3
2+3=5

と下から計算していくはずです．再帰ではこれが逆です．上から降りていけばいつかは下限につきあたって停まるので，ある意味，これは自然です．逆に「下から上っていく」と上限はありません．けど，Haskellは遅延評価パワーで無限リストを扱えるので，「フィボナッチ」の無限列を下から作って，与えた添え字に対応する要素をひっぱりだせばいいはずです．実際は遅延評価で，添え字までのリストしか構築されないはずです．つまり，

main = putStr.show.(!!) fiblist.read.head =<< getArgs

となるようなフィボナッチ数からなるリストfiblistを構築すれば解決です．fiblistは漸化式で作ります．

   | 0, 1, 1, 2, 3,  5,  8, 13, 21, 34,  55,  89, ...
0  | 1, 1, 2, 3, 5,  8, 13, 21, 34, 55,  89, ...

     1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

フィボナッチ数列をならべて，次に一個ずらして並べてみました．そして，縦に足してみると，やはりフィボナッチ数列がでてきます．しかも下から順番にいけば，同じものを何度も計算しないはず．そして，二つのリストをとって，それから新しいリストを作るにはzip系の関数をつかうわけで，その中のzipWithを使います．

import System

fiblist :: [Integer] 
fiblist = 0:1:zipWith (+) fiblist (tail fiblist)

main = putStr.show.(!!) fiblist.read.head =<< getArgs

こうなりました．zipWith (+) でfiblistの最初と，fiblistの二番目からのリストを足し算して，それをfiblistに連結します．つまり

  0 1 zipWith (+) [0 1 ...] [1 ...] 
= 0 1 (0+1) zipWith (+)[1 (0+1) ...] [(0+1) ..]
= 0 1 1 zipWith (+) [1 1 ...] [ 1 ...]
= 0 1 1 (1+1) zipWith (+) [1 (1+1) ... ] [(1+1) ...]
= 0 1 1 2 zipWith (+) [1 2 ...] [2 ...]
= ....

と計算してくれて，必要なところまで計算してとまるはずです．

実際，コンパイルすると，

>ghc fib.hs -o fib
>fib 1000
4346655768693745643568852767504062580256466051737178040248
1729089536555417949051890403879840079255169295922593080322
6347752096896232398733224711616429964409065331879382989696
49928516003704476137795166849228875

一瞬で終わります．遅延評価パワー炸裂が実感できました．面白い(^^)

*1:少なくとも，私にはできません（泣笑）