つまずきの記憶 - メモ化(2)

前回の枠組みに基づいてFibonacci関数の「メモ化版」を実装してみる。まず、型の定義から。

type A = Int
type B = Integer
type S = [(A,B)]
type Mc = S -> (B, S)

前記事の a,b,s がここの A,B,S に対応している。次に fib の「メモ化版」である mfib を定義する。前記事の mf に対応している。

mfib :: A -> Mc
mfib 0 = \s -> (0, s)
mfib 1 = \s -> (1, s)
mfib n = \s ->
    let
        (n1, s1) = memo mfib (n-1) s
        (n2, s2) = memo mfib (n-2) s1
    in
        (n1 + n2, s2)

最後に「メモ化関数」と「状態操作関数」を追加すればほぼ完成である。

memo :: (A -> Mc) -> A -> Mc
memo g x = \s ->
    case getResult x s of
        Just v  -> (v, s)                       -- g x は計算済み。
        Nothing -> let (v, s1) = g x s
                   in  (v, putResult (x, v) s1) -- 新規登録

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

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

sEmpty :: s
sEmpty = []

mfib の出力には本来の結果には必要のない「メモ」が付随しているので最終的には取り除く必要がある。また、処理開始時には状態の初期値を与える必要がある。以上を追加すると最終的な関数ができあがる:

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

素朴版ではn=40でも分単位で時間がかかったが、メモ化版ではn=100でも1000でも瞬時に結果が出力される。

*Main> fib 100
354224848179261915075

ソースコードを Gist にあげておいた¹。

次の記事では再び抽象化・汎用化について考えてみたい。

“you are not a human” と言われて苦戦した(笑)。↩