フィボナッチ数列

折角遅延評価とかしてくれるので，フィボナッチしないと勿体ない．ついでに，簡単な制御構造の勉強(条件分岐)を．

まずは簡単なトコロから．

fib :: Integer -> Integer
fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)

hugsでの実行結果です．

Main> map fib [1..20]
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]

いかにHaskellと言えど，hugsインタプリタはショボイのか，実行結果がズルズルと表示される様が見れました．流石にmainを書いてコンパイルしたら早かったけども．([1..30]ってすると，やっぱり遅い)

次は，条件式を使って．先ずはif文．

fib :: Integer -> Integer
fib n = if n == 1 || n == 2 then 1 else fib (n - 1) + fib (n - 2)

短い．そして，言うほど宇宙語じみてない．

case文．

fib :: Integer -> Integer
fib n = case n of
	  	1 -> 1
		2 -> 1
		_ -> fib (n - 1) + fib (n - 2)

_が気になる．

ガード？パターン照合の一種だとか．if文やcase文を読みにくくかっこよくしただけじゃないのかコレは．

fib :: Integer -> Integer
fib n |       (n == 1 || n == 2) = 1
        | not (n == 1 && n == 2) = fib (n - 1) + fib (n -2)

数学チックだなぁ．

追記

前にやった，lambdaってなんだ？ - もちのフィボナッチ数列計算のと早さを比べると，圧倒的にRubyのほうが早かった．そりゃ，ただ足し合わせてるだけだものね．

追記+1

相当気持ち悪いけど，高速化．

main = print $ map (fib 0 1) [1 .. 20]

fib :: Integer -> Integer -> Integer -> Integer
fib n m f = if f > 2 then fib m (n + m) (f - 1) else n + m

実行結果は同じです．段違いに早くなった．なんせただ足し合わせてるだけですもの．しかし気持ち悪い．