Haskellでメモ化する（初級）

Haskellでメモ化にチャレンジしました。

Haskellのメモ化は、C++やjavaで実装するメモ化とは違って、ひと癖もふた癖もあります。

とりあえず、基本的なメモ化ができるようになるには、2つ壁がありそう。。

1つは、参照透明性による壁。Haskellには副作用がないため、再代入ができない。つまり、メモ化する対象を更新していくというような作業ができないのです。外部変数を用意して、その外部変数に計算した値を格納していくという方法は通じないのです。。

（実は禁断のモナドを使えばできるようですが、それは最後の禁じ手だと思うので、まだ使いません。。）

2つ目は、簡約のされ方について理解が必要なことです。

ちょっと話はそれますが、このメモ化再帰を実装しているときに、改めて気がついたことがありました。

「副作用がない=外部変数を関数間で共有できない。=変数の値が勝手に変えられることはない。」

これは、大規模なプログラムを作る際に、かなり嬉しいです。というのも、参照透明性が保証されていれば、

• ある変数に何がどのタイミングで代入されるのか分からない。
• 実は関数間に順序結合があって、見た目には分かり辛い。
• 呼び出し先で勝手に値が書きかえられていた。。

などの問題から解放されるからです。これは、素晴らしい。

話を戻して、メモ化をどうやって実現するか。。更新ができなければ、毎回更新されたメモ化のコンテナを新しい変数として作成してやればいいことに気付きました。これはHaskellでは常套手段のようです。

まず、やってみたのが、これ。（例題として、フィボナッチ数列を用います。）

-- momorize status
fib n = memorized_fib n !! n

memorized_fib :: Int -> [Integer]
memorized_fib 0 = [1]
memorized_fib 1 = 1 : [1]
memorized_fib x =
   let memo = memorized_fib (x-1)
   in memo ++ [memo !! (x-1) + memo !! (x-2)]

これで、メモ化は出来ています。が、n=5000くらいになると、動きがもっさりしてきます。

Haskellのリストはランダムアクセスではなく、シーケンシャルアクセスなので、遅いのと、

簡約されない状態で値を持ち回っているのが速度を遅くしているようです。（と予想しています。）

上の例では、”値”をメモ化しましたが、Haskellでは、関数を第一級オブジェクトとして扱えるので、"関数"をメモ化することもできます。関数をメモ化するとどうなるのかやってみました。

fib n = ((memorized_fib n) !! n) n

memorized_fib :: Int -> [Int -> Integer]
memorized_fib 0 = [(\x -> 0)]
memorized_fib 1 = memorized_fib 0 ++ [(\x -> 1)]
memorized_fib n = let f  = memorized_fib (n-1)
                 v1 = (f !! (n-1)) 0
                 v2 = (f !! (n-2)) 0
             in f ++ [\x -> v1+v2]

えーっと、見てのとおり、全然だめです。一応動きますが、かなり酷いです。

引数を受け取って、その引数に対する値を返す関数をすべての引数に対してメモ化すればいいのでは？と思いましたが、きれいに書けませんでした。

そして、いろいろとネットをあさって見つけたメモ化再帰のお手本。

memorized_fib :: Int -> Integer
memorized_fib =
let fib 0 = 0
   fib 1 = 1
   fib n = memorized_fib (n-2) + memorized_fib (n-1)
in  (map fib [0 ..] !!)

無駄な処理がなく、見た目も綺麗です。速度も上の2つと比べて、高速です。

並べて比較してみると、自分のはメモ化の結果を再帰的に定義しているから余計な処理が生じているのかなと思います。あくまでもメモ化対象のものは絶対的なものとして一つ存在していて、再帰するのは実際の計算処理のみ。実際の計算と、メモ化する領域をわけて交互に連鎖させる。というかんじで作っていけばいいのでしょうか。

ただ、上のような書き方は、簡約がどのように行われるかまで把握していなければ難しい業だと思いました。Haskellでは、グラフ簡約という簡約が行われていて、一度簡約された値は、二回目以降は計算されないそうです。

ただし、すべてがそうなるわけではありません。もし、すべてがそのように処理されるのであれば、今回やっているようにわざわざ人間の手でメモ化する必要はありません。

どうやら、簡約をやり直す場合と、簡約後の値を参照しにいく、２パターンがあるようです。上のようなメモ化を書くには、”どういう記述をすれば後者のような処理になるのか。”をきちんと把握する必要がありそうです。

また、メモ化には、不動点を使ったメモ化もあるようです。データ構造にもリスト以外にtreeを使ったものがあるよう。。なぜ、そういうものが必要なのかは今の私のHaskell力では、理解できませんが、いつか分かる日が来るでしょう。。そのときに（中級）と（上級）編を書きます。