記憶(memo)する関数 @ val it: α → α = fun

>『情報処理』の Haskell 連載について、 State モナドを使ってみた。とりあえず書いたのがこれ。 > >statecc :: (Amount, [Coin]) -> State (Table (Amount, [Coin]) Count) Count
statecc (0, _) = return 1
statecc (_, []) = return 0
statecc (a, ccs@(c:cs))
| a < 0 = return 0
| otherwise = do tbl <- get
case lookupTable (a, ccs) tbl of
Just v -> return v
Nothing -> do c1 <- statecc (a, cs)
c2 <- statecc (a-c, ccs)
modify (insertTable (a, ccs) (c1+c2))
return (c1 + c2) > >こんなもんかと思うけど、 do が二重になっているのは美しくないし、一般化されていないので、記事同様に記憶する箇所を memoise で括り出す。 > >memoise :: Eq a => (a -> State (Table a b) b) -> a -> State (Table a b) b
memoise f x = do tbl <- get
case lookupTable (a, ccs) tbl of
Just v -> return v
Nothing -> do v <- f x
modify (insertTable x v)
return v
statecc :: (Amount, [Coin]) -> State (Table (Amount, [Coin]) Count) Count
statecc (0, _) = return 1
statecc (_, []) = return 0
statecc (a, ccs@(c:cs))
| a < 0 = return 0
| otherwise = do c1 <- memoise statecc (a, cs)
c2 <- memoise statecc (a-c, ccs)
return (c1+c2) > >case は美しくないので、 fromMaybe を使うとこうなるか。 > >memoise :: Eq a => (a -> State (Table a b) b) -> a -> State (Table a b) b
memoise f x = do tbl <- get
v <- fromMaybe (f x) (lookupTable x tbl >>= return . return)
modify (insertTable x v)
return v > >ただこうしちゃうと、一回計算してようが何しようが問答無用でテーブルに挿入してしまうので、テーブルがむちゃくちゃ巨大化するし lookup の速度も落ちる気がする。といっても既にあるデータかどうかのチェックに lookup するのも無駄っぽいしなぁ……と思ったのだが、10000で計算したら実行速度は大差なかった。使用メモリも大差ないのだが、どっちみちオーバーフローしているので差はよくわからないけど、あんまり差はないようだ。んーそういうものか？　まあもともと連想リストの時点でテーブル実装の効率は度外視しているんだから細かいことを気にしても仕方ないのか。 > >return . return がキモくて楽しい。 > >ところで記事ではなんで lookupTable は Maybe v ではなく >

val it: α → α = fun

記憶(memo)する関数

Archives

disclaimer