今回から「メモ化¹」という技法を題材にして、Haskellの理解を深めて行きたいと思う。書き始めると案外長くなりそうな気配なので、数回に分けることにした。

同じ計算を何度も行うのは非効率的なので、一度計算した結果はどこかに「メモ」しておき、後にまた同じ値が必要となったならば、再計算するのではなくてこのメモした値を取ってこよう…これが「メモ化」という技法であり、発想としてはとても素朴なものである。したがって、Haskell に限った話題ではない。

メモ化については山下伸夫さんの「記憶(memo)する関数²」がとても参考になった。

メモ化が有効となる典型的例として挙げられるのは有名なFibonacci関数である。以下のような単純な実装では呆れるほどに遅い。なぜなら、再帰呼出し fib の中で幾度も同じ計算を行っているからである。

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

GHCiで実行すると、fib 30 で数秒、fib 40 だと分のオーダーとなるであろう。例えば fib 6 の計算は、

fib 6 = fib 5 + fib 4
      = (fib 4 + fib 3) + (fib 3 + fib 2)
      = ((fib 3 + fib 2) + (fib 2 + fib 1)) + ((fib 2 + fib 1) + (fib 1 + fib 0))
      = ・・・

という具合である。計算の手間がかかることを示すためなので、簡約の仕方はテキトーである。例えば fib 3 は3度登場しているが、この値を求めるために毎回

fib 3 = fib 2 + fib 1 = (fib 1 + fib 0) + 1 = 1 + 0 + 1 = 2

を計算しており、いかにもムダであることが分かる。Fibonacci数列を高速に生成する方法は色々知られているが、今は「メモ化」自体が目的なので、メモ化によって高速化を図ってみる。

山下さんの記事では具体例に沿った実装から始めて抽象的な関数を導かれているので、ここでは逆に、「メモ化を実現するには何が必要だろうか？」というところから考え始めてみたいと思う。

メモ化のための準備

いまやりたいことは、関数 f が再帰呼出しを行う際に計算済みかどうかを調べることである。そこで、memo という小道具を登場させる。関数 memo の定義は次のような感じである:

memo :: (a -> b) -> a -> b
memo f x = ...

memo の引数に、計算をしたい関数 f と f に喰わせる値 x を渡す。memo は f x が計算済みかどうかを調べ、もし計算済みならばその値を返し、未計算ならば実際に f x を計算し、この値を記憶しておく・・・おっと、記憶場所が無かった。Haskellは純粋なので、記憶場所が必要ならば引数に与えなければならない。つまり、この型定義ではメモ化はできない。そこで「記憶場所(=メモ)」の登場である。メモしておく場所がどんなものとなるのかはまだ分からないので、とりあえず「s という型のもの」とだけ決めておく。メモを参照するためには引数として渡す必要があり、内容が変更された（かもしれない）メモの中身を得るためには関数の戻り値にも無いといけない。そうすると、memo の定義は次のようになる:

memo :: (a -> b) -> a -> s -> (b, s)    -- sはメモを表す
memo f x s = ・・・

こうすれば、memo は過去の計算結果を参照したり、新しく計算した値を保存したりできそうである。これで f が再帰呼出ししているところで単なる f の代わりに memo f を呼び出してみれば良さそうだが、f の型が元のままの a -> b ではメモを memo に渡すことができない。また、f の計算によってメモの内容が変わるかもしれない。したがって、memo と同様に入出力に s を加える必要がある。それに伴い、memo も再度修正する必要があるので、両者の型は次のようになる:

-- 元の f と区別するため、メモ付きの f ということで mf とした。
mf :: a -> s -> (b, s)                  -- sはメモを表す
mf x s = ...

memo :: (a -> s -> (b, s)) -> a -> s -> (b, s)
memo mf x s = ...

かつての自分ならばこのあたり頭がグラグラしていたんじゃないかと思うので、ここで一息つきながらゆっくり意味を考えてみる。

そもそも求めたかったものは f x であった。しかし、メモ化対応の mf に x を与えても f x の値は（直接的には）返ってこなくて、代わりに s -> (b, s) という型の関数が返ってくる。これは最終的には f x の値を返すのだが、計算の際にメモを活用するので引数にメモが必要であり、計算が終わったら計算結果(= f x)とともに、更新されたかもしれないメモも返す、というものである。s -> (b, s) の型を、「メモを使った計算」ということで、Mc という名前をつけることにする。Mc を使って上の定義を書き換えると下のようになる。型定義に -> がたくさんあるとなんとなく「怖い」感じを受けるので、何か意味のある部分を取り出して別名で定義すると見通しが良くなる。

mf :: a -> Mc                       -- Mc はメモ付きの計算
mf x = \s -> ...

memo :: (a -> Mc) -> a -> Mc
memo mf x = \s -> ...

単に型だけを書き換えても良かったのだが、見た目に合わせて定義本体のほうも変えてみた。つまり、関数の定義を「mf x は「s を受け取って・・・をする関数」を返す」と読むのである。memo の方も同様に変更した。

ここで、memo の中身を考えてみる。memo がやるべきことは、計算しようとしている値がメモに登録済みかどうかを調べ、あればそれを返し、なければ新規に計算して値を登録する、ということを行う。Haskell の擬似コードで書くと次のようになる:

memo :: (a -> Mc) -> a -> Mc
memo g x = \s ->
    if (g xの値を計算済み)
        then (計算済みの値, s)      -- メモ内容に変化無し
        else let (z=計算値, s1=更新されたメモ) = g x s  -- 新規に計算
             in  (z, s1にzを登録したメモ)

では次に元の f を mf に書き換えてみる。s はメモなので、memo とのやりとり以外では戻りとして返すだけである。memo とのやりとりがあるのは再帰呼び出しの部分だけなので、それ以外は元の f のコードのままとなる。

-- f :: a -> b からの書き換え
mf :: a -> Mc
mf x = \s ->
    let
        (y1, s1) = memo mf x1 s      -- 再帰呼び出し(1)
        ・・・
        (y2, s2) = memo mf x2 s1     -- 再帰呼び出し(2)
        ・・・
        z = (mf の値: y1,y2などを使って計算)
    in
        (z, s2)     -- 戻り値 z に更新されたメモを添える

memo を使って mf を呼び出した結果、メモに変化が起きてる（新しい f の値が追加されている）可能性があるので、変化したかもしれないメモを s1 とし、次の再帰呼び出しでは s1 を与える。f の計算が終わったら、出力すべき値と最後の再帰呼び出しから戻ってきたメモの内容（ここではs2）を対にして返す。

ここで注目すべきは、mf におけるメモ(=s,s1,s2)は memo との受け渡しに使っているだけであり、変更はもちろん、中身を見てさえいない。mf にとっての関心事は x から b 型の値 z を計算することだけであり、メモは全く付随的なことにすぎないのである。
逆に memo の側から見ると、メモを使って何の計算をしているのかということは全く分からず（関心も無く）、単に引数で渡された g という関数を使ってメモ関係の処理を行っているだけである。
このように、機能を完全に分離しておくことは大切である。分離されていれば、例えばメモの実装や処理方法が変わったとしても、mf には何の修正も必要無い。きれいに分離されていないと、メモの改造が mf にまで及んだりして大変面倒なことになる。

「メモ」の実装

メモはとりあえず型を s と定めただけで具体的なことはまだ何も決まっていない。まず、どのような機能が備わっていれば良いかというと、

• f x が計算済みかどうか調べ、計算済みならばその値を取得すること
• 新規に計算した f x の値を登録すること
• 計算開始時に与える初期状態

この3つがあれば良い。計算済みかどうかを調べる関数を getResult、登録する関数を putResult、初期状態を sEmpty としておく。これらの関数の型は次のようになろう:

getResult :: a -> s -> Maybe b
putResult :: a -> b -> s -> s
sEmpty :: s

getResult x s は、f x が計算済みならばその値 z を Just z で返し、未計算ならば Nothing を返す。putResult x (f x) s は新規に f x の値をメモし、変更後のメモを返す。メモの初期値は、まだ何も計算結果が記録されていないものとすべきなので、それぞれの実装に応じた「からっぽ」を意味するものとすれば良い。

実装方法は色々考えられるが、ここでは分かりやすさ優先でリストを用いた実装をしてみる。メモの実体となるリストには計算済みの (x, f x) が記録されることになる。

getResult :: Eq a => a -> s -> Maybe b
getResult = lookup

putResult :: (a, b) -> s -> s
putResult = (:)

sEmpty :: s
sEmpty = []

getResult の型 a には lookup を使えるよう Eq の制約をつけており、putResult は定義が簡単になるように引数の型を変更している。

枠組みがだいたいできあがったので、次回はメモ化したFibonacci関数を実装してみようと思う。