メモ化についてもう少し考えてみたい。前記事のメモ化では、以下の点に不満が残る:

• 型の定義に A (= Int) などの具体型を書いているので、別の型を扱うたびにそれぞれの memo を書かなければならず、これでは「部品」として使えない。
• memo を利用する側の関数（前記事では mfib）でもメモの入出力を意識しなければならず、使い勝手が良いとは言いがたい。

型変数を使って定義し直す

不満のひとつ目を解決するには型変数を使って任意の型に対応できるようにすれば良い。まず、関数の値を記録しておく場所を Memo として次のように定義する:

type Memo a b = [(a,b)]

getResult :: Ord a => a -> Memo a b -> Maybe b
getResult = lookup

putResult :: Ord a => (a, b) -> Memo a b -> Memo a b
putResult = (:)

sEmpty :: Memo a b
sEmpty = []

型 a の制約を Eq から Ord に変更したのは、リスト以外の構造（例えばマップ）を使う場合に大小比較が必要となるからである。Ord は Eq でもあるので Ord にしておけばリスト構造の場合でも問題無い。メモの実体をリスト以外のものに変更した場合は lookup や (:) を適当なものに置き換えれば良い。Memo の定義を変更するだけで、関数の型を変更する必要はない。

次に、memo を書き換える。

type Mc s b = s -> (b, s)

memo :: Ord a => (a -> Mc (Memo a b)) b -> a -> Mc (Memo a b) b
memo f n s = case getResult n s of
                Just v  -> (v, s)
                Nothing -> let (v, s1) = f n s
                           in  (v, putResult (n, v) s1)

memo が型変数を使って表現されたので、任意の型の関数のメモ化が可能となった。

メモを newtype で定義する

不満点のもうひとつ、メモの隠蔽化に取り組んでみる。

getLine や putStr などのI/O関数は、外界とのやりとりをするためになんらかの状態を扱っているはずなのだが、コードを書く際には状態などは意識せず、xs <- getLine とか putStr "Hello" などとできる。これはIOモナドのおかげなのであるが、これから目指すものも「メモのモナド化」である。それができればメモのやりとりに煩わされず、本来やりたい処理に注力できるはずである。
その前にまず準備として、Mc をMonadのインスタンスとするために Mc の定義を type から newtype に変更しなければならない。

newtype Mc s b = McD {runMc :: s -> (b, s)}

type を使った定義と比べると右辺が複雑になった。newtype ではデータ構築子が必要なので、右辺全体をデータ構築子 McD で囲んでいる。もちろん、型構築子と同じ名前の Mc でも良いのだが、あえて異なる McD にしてみた。また、単に newtype Mc s b = McD (s -> (b, s)) でもいいのだが、データ構築子 McD をはがす runMc があった方が便利なのでこうしておく。

Fibonacci関数のコードの type を newtype に変えてコンパイルすると、たくさんエラーが出てしまう。順に調べていこう。

memo や mfib の引数にある s でまず怒られてしまう。mfib の型は

mfib :: Int -> Mc Integer (Memo Int Integer)

であったが、Mc は type で定義された s -> (s, b) 型の関数であったため、直接 s を渡すことができた。ところが、Mc を newtype で定義してあると、mfib の戻り値が Mc Integer (Memo Int Integer) のひとかたまりとなるので、直接 s を渡すことはできないのである。したがって、mfib の定義は、「mfib x = メモを受け取って（結果, 新しいメモ）を返す関数を McD で包んだもの」となる。擬似コードで書くと、

mfib x = McD (\メモ -> (結果, 更新後のメモ))

となる。このあたりは慣れるまで分かりにくいのではないかと思う。memo に与えている引数 s についても同様である。

ゆっくり考えてみる。Memo Int Integer は長いので説明のため、単に Memo と書く。

まず、Mc を type で定義している場合、

mfib :: Int -> Mc Integer Memo
        これは↓と同じ意味
        Int -> Memo -> (Integer, Memo)

したがって、“mfib n メモ” のように直接メモも渡すことが可能であった。

一方、Mc を type で定義している場合は前述のように McD に包まれていて直接メモを渡すことができないが、runMc という関数を通すと包みがはがれてメモを渡すことのできる関数が露出する。したがって、以下のようにメモを渡すことができる:

mfib n メモ         … とはできないので、
runMc (mfib n) メモ … のように使う。

このあたりは慣れるとなんてことはないのだが、最初はとっつきにくかった。決して中身が難しいことではないと思うので、分かるまで諦めずに粘ることが肝要であろう。

memo mfib ... でエラーとなるのも runMc を使わずにメモを渡そうとしているからである。上記と同様に runMc を仲介してから渡すように修正する。

以上のような変更を施した Fibonacci 関数のコードが↓である(Gist):

type Memo a b = [(a,b)]
newtype Mc s b = McD { runMc :: s -> (b, s) }

mfib :: Int -> Mc (Memo Int Integer) Integer
mfib 0 = McD (\s -> (0, s))
mfib 1 = McD (\s -> (1, s))
mfib n = McD $ \s ->
    let
        (n1, s1) = runMc (memo mfib (n-1)) s
        (n2, s2) = runMc (memo mfib (n-2)) s1
    in
        (n1 + n2, s2)

memo :: Ord a => (a -> Mc (Memo a b) b) -> a -> Mc (Memo a b) b
memo f x = McD $ \s ->
    case getResult x s of
        Just v  -> (v, s)
        Nothing -> let (v, s1) = runMc (f x) s
                   in  (v, putResult (x, v) s1)

getResult :: Ord a => a -> Memo a b -> Maybe b
getResult = lookup

putResult :: Ord a => (a, b) -> Memo a b -> Memo a b
putResult = (:)

sEmpty :: Memo a b
sEmpty = []

fib :: Int -> Integer
fib n = fst $ runMc (mfib n) sEmpty

依然としてメモを扱うコードが陽に残っている。 次の記事ではいよいよモナド化に取り組み、メモ化関連のコードを舞台裏に隠してしまう。