Haskellでフィボナッチ

去年の六月ごろに「すごいHaskell楽しく学ぼう」（以下すごいH）を買って読んでみようと思ったのですが、当時はほとんどプログラミングをしたことがなく、良くわからないまま終わりました。８か月ほど経って経験を積んだのでようやく本棚でほこりをかぶっていた本を読み始めてみました。
とりあえず再帰でフィボナッチ数列を求めてみるコードを書いてみます

fibo1 ::(Num a)=> Int -> a
fibo1 0 = 1
fibo1 1 = 1
fibo1 n = fibo1 (n-1) + fibo1 (n-2)

いやぁ気持ちが良いですね
なんか漸化式をそのまま書くと動くので嬉しいです

このままだとn番目のフィボナッチ数を求めるオーダーが指数オーダーなので動的計画法っぽいことをして、O(n)で計算させてみます。

applyN :: Int ->(a->a) ->a ->a
applyN 0 _ a = a
applyN n f a = f $ applyN (n-1) f a

fibo2 :: Int -> Integer
fibo2 n = fst $ applyN n (\(a,b) -> (a+b, a)) (1,0)

ラムダ計算で書くとなんかそれっぽくてカッコいいですね
それにバグっていないという安心感がありますね
これが副作用がないということなんでしょうか
折角なので行列を繰り返し二乗法で計算してO(log n)で計算するやつをやってみました

data Mat a = Mat a a a a deriving (Show)

mmul:: (Num a)=>Mat a -> Mat a -> Mat a 
Mat x y z w `mmul` Mat i j k l 
    = Mat (x*i+y*k) (x*j+y*l) (z*i+w*k) (z*j+z*l)

getnum :: Mat a -> a
getnum (Mat x _ _ _) = x

fiboMat = Mat 1 1 1 0

appself ::(a-> a->a) -> a -> a
appself f x = f x x

foldn:: Int -> (a -> a-> a)-> a-> a
foldn 1 _ a = a
foldn n f a 
    |even n = appself f (foldn (n `div` 2) f a )
    |otherwise = f a $ appself f (foldn (div n 2) f a )

fibo3 :: Int -> Integer
fibo3 n = getnum (foldn n mmul fiboMat)

関数の名前を付けるセンスがないですねぇ。
いや非常にテンションが上がりますね。行列を定義するのが非常に自然です。
これめちゃくちゃ自然に書けますねぇ
appselfという関数が実は重要で、これを使わないと再帰展開が分岐してしまってO(n)になってしまいます（しまいました）
すごいH本を読み進めていきましょう