コメントでhaskellでフィボナッチの別解をもらったが、パッと見てもなぜこれでフィボナッチ数列ができるのかいまいちわからんかったので、よく読んでみたヨ。
まずは型チェック。 見ればわかるとおりfibはリストを返す関数ですな。つまり、fibを実行するとフィボナッチ数がどんどこどんどことそれこそとめどなく溢れてくる(はず)
fib :: Num a => [a] fib = 0:1:zipWith (+) fib (tail fib)
これを fib.hsという名前で保存してghciで実行してみる。
$ghci *Main> :l fib.hs *Main> fib
をを～。凄い勢いでフィボナッチ数列がどんどこど(以下略)。ちなみにlengthでリストの長さをはかってみると、プロンプトがかえってこないゾ。さすが無限リスト。
zipWithの型とtailの型はこんな感じ。
Prelude> :t zipWith zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] Prelude> :t tail tail :: [a] -> [a]
zipWithは高階関数で、+関数をfibとtail fibに適用して新しいリストをつくるわけですな。tailは先頭の要素を取り除いたリストを返す関数だから、、、うーんやってることはわかるんだけど、イマイチイメージできん。
と悩んでたら、Wikipediaに書き下されてる表をみつけて納得した。perlで同じことやろうとするとまず有限個の要素をもつ配列があってみたいなところから始まるから、こういう表現はできないな。というわけで、目からうろこっていうか、ちょっと感動した。
ここで考えたようなn-1番目とn番目のフィボナッチ数が与えられたときにn+1番目のフィボナッチ数を求めるということを考えるのではなくて、そもそもフィボナッチ数列とは何かを考えて、それを無限リストとして表現することを考えればよいんですよと。
となると、リスト内包表記も感動するような綺麗さダ。
fibs = 0 : 1 : [ a+b | a <- fibs | b <- tail fibs ]
GHCの並列リスト内包表記(GHCの拡張は特別なコマンドラインフラグによって有効にしなければならない。
とあるのが、なにが問題なんだかわからんので、とりあえず実行してやろう。
fib4.hs:1:15: Illegal parallel list comprehension: use -fglasgow-exts Failed, modules loaded: none.
デフォルトだと、同じリストが複数でてくるような表記の仕方(この場合はfibs)は問題あるということなのかな
ghci -fglasgow-exts
とオプションを指定して実行することで、OK。をを～。凄い勢いでフィボナッチ数列がどんどこど(以下略)。
haskell素敵過ぎ