ふえぇわからないよ

なんかTLでHaskellフィボナッチ数列の40項の単純再帰の計算が40秒かかる、とかなんとか話題になっていたので、最近の式の評価戦略のこともあるのでなんか書く。

えーと、普通にフィボナッチ数列のn項"fib n"を求める式を書こうとすると、以下のようになると思います。

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

これを普通に計算すると、確かに時間がかかる。
これは、計算された式の再利用をしないからで、再帰段階のfib (n-1)とかfib (n-2)を別個に計算するから、その度に同じfibが多重に呼び出しされて計算量が膨大になるからといえる。
丁度SICPの1.2.2節にfibの計算の木が載っているので、これを見ればいかに計算量が増えていくかがよく想像できると思う。


じゃあ、どうするか、という話だが。

SICP1.2節には、recursive processとiterative processの2つの計算の戦略を挙げている。前者は、いまやったような式で定義される再帰で、fibのようなのもだと木状の計算構造になる。
一方で、フィボナッチ数列を2変数(x, y)から(y, x+y)への変換のくり返し(iteration)とで生成する列と考える事ができる。
このアルゴリズムHaskellだと次のように実装することができる:

fibgen :: [Int] -> [Int]
fibgen xs = (xs !! 0) + (xs !! 1) : xs

iterate :: Int -> (a -> a) -> (a -> a)
iterate 0 f = \x -> x
iterate n f = f . iterate (n-1) f

fib' :: Int -> Int
fib' n = head $ (iterate (n-1) fibgen) [1,0]

説明すると、fibgenで数列を膨らませる1ステップを表現して、それをiterateで何度も繰り返して、fib'でそのhead(途中まで作ったフィボナッチ数列の末尾項)を取る。

こうすると、ちゃんとfast(processが線形なので)に計算してくれてめでたしめでたし♪


でも実際haskellには正格な評価という概念があるし、正格版の再帰的定義が出来るようになっているし、わざわざこんなことしなくてもいいんですけどねえ。
(すいません、Haskellのことはあまり知らないのです><)


まあ、SICPの話も出ましたし、おぼえがきということで。


ニャンニャン