Create a gist now

Instantly share code, notes, and snippets.

Embed
メモ付きのFibonacci関数(1)
-- 「つまずきの記憶 メモ化(2)」のソースコード
-- メモ付きのFibonacci関数 [mfib-1.hs]
-- 型の定義
-- 「メモ化(1)」の `a`,`b`,`s` がここの`A`,`B`,`S`に対応している。
type A = Int
type B = Integer
type S = [(A,B)]
type St = S -> (B, S)
-- メモ付きFibonacci関数
mfib :: A -> St
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 -> St) -> A -> St
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) -- 新規登録
-- 「メモ操作関数」
getResult :: A -> S -> Maybe B
getResult = lookup
putResult :: (A, B) -> S -> S
putResult = (:)
sEmpty :: S
sEmpty = []
-- メモ付きの関数を走らせ、結果からメモを除去する。
fib :: Int -> Integer
fib n = fst $ mfib n sEmpty
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment