--Multipart_Thu_Aug_18_15:44:12_2005-1
Content-Type: text/plain; charset=ISO-2022-JP

向井です。

State モナドをなぜ使わないのかも気になったのですが、どう実装するか、と
いう点を説明するために便利なライブラリをいきなり導入するのは避けたのだ
と思いました。
どんどん抽象ていく過程は読んでいて面白いです。
# 読者がどこまでついて来てるかという疑問はありますが

ところで、 lookupTable が Maybe v ではなく [v] を返したり、テーブルで 
Ord を使って整列しているのには何か意図があるのでしょうか? Prelude の 
lookup を使うかどうかはさておき、 Eq で良いのではないかと思ったのです
が……。


State モナドを使った版もい討澆泙靴燭里如添付します;
こんな感じでしょうか。




--
ML: haskell-jp / quickml.com
使い方: http://QuickML.com/
--Multipart_Thu_Aug_18_15:44:12_2005-1
Content-Type: text/plain; charset=US-ASCII
Content-Disposition: inline; filename="memoize.hs"
Content-Transfer-Encoding: 7bit

import Control.Monad.State
import Data.Maybe


type Amount  nteger
type Coin    nteger
type Count   nteger

type Table k v  (k, v)]

emptyTable :: Table k v
emptyTable  ]

lookupTable :: Eq a a -> Table a b -> Maybe b
lookupTable  ookup

insertTable :: Eq a a -> b -> Table a b -> Table a b
insertTable k v  (k, v):)

memoise :: Eq a (a -> State (Table a b) b) -> a -> State (Table a b) b
memoise f x  o tbl <- get
		 v <- fromMaybe (f x) (lookupTable x tbl >> eturn . return)
		 modify (insertTable x v)
		 return v

statecc :: (Amount, [Coin]) -> State (Table (Amount, [Coin]) Count) Count
statecc (0, _)  eturn 1
statecc (_, [])  eturn 0
statecc (a, ccs@(c:cs))
    | a < 0  eturn 0
    | otherwise  o c1 <- memoise statecc (a, cs)
		     c2 <- memoise statecc (a-c, ccs)
		     return (c1 + c2)

--Multipart_Thu_Aug_18_15:44:12_2005-1--