Haskellでメモ化する（中級）

　前回のpostで、Haskellでメモ化する方法について書きました。そのとき、疑問点として、「なんで、メモ化と不動点が繋がってるねん！なんでやねん！」というのがありました。その疑問が解決したので中級編を書きます。

　どうやら不動点コンビネータを利用してやりたいことは、「任意の関数が与えられたときに、その計算をメモ化する関数を作成する」ということのようです。この発想にはびっくりです。どれだけ抽象度の高いことをやるんだよ。という感じです。imparative、あんど、object-orientedな思想に育てられた（毒された？）普通のプログラマーである私には思いもよらない発想でした。。

　まずは、メモ化と、不動点コンビネータについて少しおさらいをします。フィボナッチ数列をメモ化再帰で解くプログラムを書いてみます。

memoFib =
   let fib 0 = 1
       fib 1 = 1
       fib n = memoFib (n-1) + memoFib (n-2)
   in (map fib [0..] !!)

これは、list-comprehensionを用いて以下のように書くこともできます。（こっちの方が分かりやすいかも？？）

memoFib = [fib x | x <- [0..]]
         where fib 0 = 1
               fib 1 = 1
               fib n = memoFib !! (n-1) + memoFib !! (n-2)

と、とりあえず、関数がgivenであれば、その関数をメモ化してあげることは出来ます。

　次に、不動点コンビネータについて。Haskellでは、Control.Monad.Fixに不動点コンビネータが定義されています。これを使ってもいいですが、勉強のために自分で実装してみます。再帰関数を不動点コンビネータに書きかえる方法についてはここのページがとても分かりやすいです。

フィボナッチ関数を不動点コンビネータで書きなおします。フィボナッチ数列は、ラムダ式を用いて

fib = (\x -> if x <= 1 then 1 else fib (x-1) + fib (x-2))

と書けます。さらに、再帰で呼び出される関数を引数で与えることにすると、

fib = (\f x -> if x <= 1 then 1 else f (x-1) + f (x-2)) fib

と書けます。上の式をみると、フィボナッチ関数は

(\f x -> if x <= 1 then 1 else f (x-1) + f (x-2))

の不動点となっています。つまりフィボナッチ関数は、

fix (\f x -> if x <= 1 then 1 else f (x-1) + f (x-2))

と書けるというわけです。（詳しくは上のお勧めページ参照。）

　と、準備はここまで。いよいよ任意の関数をメモ化関数に書きかえる関数を定義するわけですが、任意の関数というのは、Haskellビギナーの私にはちと難しいので、(Int -> Int)型の任意の関数をメモ化することにします。

　まず、引数にそのままメモ化したい再帰関数を渡してしまうと意味がない（メモ化機構を入れられない）ので、メモ化したい関数を不動点にとるような関数を引数として渡してあげます。

fix f = f (fix f)

とすると、fを渡すという意味です。

ここまで来ると、なんとなくできそうな感じがします。なんとなく実装したのが、これ。

memorizeCalc f = ([f (memorizeCalc f) x | x <- [0..]] !!)

計算自体は正しいですが、メモ化が機能していないようです。前にも書きましたが、Haskellの場合、グラフ簡約のメモ化（ここでいうメモ化は、グラフ簡約されて同じ計算がされないという意味のメモ化）が働く場合と働かない場合があります。この形は前に見たことがあります。おそらく、引数をやめて実体を無限リストとして定義してあげればグラフ簡約が働くはず。で、書いたのがこちら。

memorizeCalc f = memo
       where memo = ([f memo x | x <- [0..]] !!)

これで、「与えられた関数をメモ化関数に変換する関数」が出来ました。実際に確かめてみます。

fib' = (\f x -> if x <= 1 then 1 else f (x-1) + f (x-2))
trippleFib' = (\f x -> if x <= 2 then 1 else f (x-1) + f (x-2) + f (x-3))

main = do print $ memorizeCalc fib' 300
         print $ memorizeCalc trippleFib' 300

値も正しく、高速化もされていることが確認できました。

　次のテーマは、

• (Int -> Int)型以外の関数のメモ化
• 高速化

です。高速化については、無限平衡二分木を用いた方法が紹介されています。また、Stateモナドを用いた方法があるようです。他にもData.ArrayのArrayが使えるんじゃないかなあ、とにらんでいます。。この辺が出来たら、上級編を書きたいです。