monad-memo 0.2.0 → 0.3.0

raw patch · 10 files changed

+328/−157 lines, 10 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGES +8/−0
• Control/Monad/Memo.hs +34/−9
• Control/Monad/Memo/Class.hs +30/−41
• Control/Monad/Memo/Example.hs +15/−2
• Control/Monad/Trans/Memo/Map.hs +70/−0
• Control/Monad/Trans/Memo/State.hs +97/−0
• Control/Monad/Trans/Memo/Strict.hs +0/−102
• Data/MapLike.hs +30/−0
• Data/MapLike/Instances.hs +37/−0
• monad-memo.cabal +7/−3

@@ -0,0 +1,8 @@+++0.2.0+- Added a set of forX functions (for2, for3 and for4) to adapt curried function into uncuried MemoCache++0.3.0+- Added generalized MemoStateT transformer (to host any Data.MapLike cache-container)+- MemoT is now MemoStateT instantiated with Data.Map

@@ -7,29 +7,38 @@ Stability   :  experimental Portability :  non-portable (multi-param classes, functional dependencies) -[Computation type:] Monadic computations with support for memoization.+Exports all necessary bits and pieces (default set) for memoization.+It should be suficient to import just thim module to be able to ad memoization to your monadic code -Defines monadic interface 'MonadMemo' for memoization and simple implementation 'MemoT' (based on 'Data.Map') -}   module Control.Monad.Memo (+    module Control.Monad,+    module Control.Monad.Trans,+    module Data.MapLike,     -- * MonadMemo class     MonadMemo(..),-    -- * The Memo monad+    -- * Generalized Memo monad+    MemoState(..),+    runMemoState,+    evalMemoState,+    -- * Generalized MemoStateT monad transformer+    MemoStateT(..),+    runMemoStateT,+    evalMemoStateT,+    -- * Map-based Memo monad     Memo,     runMemo,     evalMemo,     startRunMemo,     startEvalMemo,-    -- * The MemoT monad transformer+    -- * Map-based MemoT monad transformer     MemoT(..),     runMemoT,     evalMemoT,     startRunMemoT,     startEvalMemoT,-    module Control.Monad,-    module Control.Monad.Trans,     -- * Adapter for memoization of multi-argument functions     for2,     for3,@@ -56,10 +65,19 @@  import Control.Monad.Memo.Class -import Control.Monad.Trans.Memo.Strict (-    MemoT(..), runMemoT, startRunMemoT, evalMemoT, startEvalMemoT,-    Memo, runMemo, startRunMemo, evalMemo, startEvalMemo )+--import Control.Monad.Trans.Memo.Strict (+--    MemoT(..), runMemoT, startRunMemoT, evalMemoT, startEvalMemoT,+--    Memo, runMemo, startRunMemo, evalMemo, startEvalMemo ) +import Control.Monad.Trans.Memo.State -- (+--    MemoT(..), runMemoT, evalMemoT,+--    Memo, runMemo, evalMemo )++import Control.Monad.Trans.Memo.Map++import Data.MapLike++ import Control.Monad import Control.Monad.Trans @@ -98,6 +116,13 @@ Then it can be run with 'startEvalMemo'  >startEvalMemo . fibm $ 5++Or using applicative form:++>fibm :: (Num n, Ord n) => n -> Memo n n n+>fibm 0 = return 0+>fibm 1 = return 1+>fibm n = (+) <$> memo fibm (n-1) <*> memo fibm (n-2)  -} 

@@ -48,23 +48,25 @@ import Control.Monad.Trans.List import Control.Monad.Trans.Maybe import Control.Monad.Trans.Reader-import qualified Control.Monad.Trans.State.Lazy as Lazy -- (StateT, get, put)-import qualified Control.Monad.Trans.State.Strict as Strict -- (StateT, get, put)-import Control.Monad.Trans.Writer.Lazy as Lazy-import Control.Monad.Trans.Writer.Strict as Strict+import qualified Control.Monad.Trans.State.Lazy as SL+import qualified Control.Monad.Trans.State.Strict as SS+import qualified Control.Monad.Trans.Writer.Lazy as WL+import qualified Control.Monad.Trans.Writer.Strict as WS+import qualified Control.Monad.Trans.RWS.Lazy as RWSL+import qualified Control.Monad.Trans.RWS.Strict as RWSS  -import Control.Arrow-import Prelude (undefined)-+-- | Interface for memoization cache+-- Is necessary since memoization mechanism from one transformer can use a cache from other (further down the stack)  class Monad m => MonadCache k v m | m -> k, m -> v where     lookup :: k -> m (Maybe v)     add :: k -> v -> m () +-- | Memoization interface class Monad m => MonadMemo k v m | m -> k, m -> v where     memo :: (k -> m v) -> k -> m v -+-- | Memoization for the current transformer in stack using a cache from an arbitrary transformer down the stack memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) =>            (forall a.m1 a -> m2 a) -> (k1 -> k2)  -> (k1 -> m2 v) -> k1 -> m2 v memoln fl fk f k = do@@ -76,26 +78,6 @@                 fl $ add (fk k) r                 return r -memoln2 :: (MonadCache k v m1, Monad m1, Monad m2) =>-           (forall a.m1 a -> m2 a) -> (k -> m2 v) -> k -> m2 v-memoln2 fl f k = do-  mr <- fl $ lookup k-  case mr of-    Just r -> return r-    Nothing -> do-                r <- f k-                fl $ add k r-                return r--memov2 f k = do-  mr <- lookup k-  case mr of-    Just r -> return r-    Nothing -> do-                r <- f k-                add k r-                return r- -- | Adapter for memoization of two-argument function for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv for2 m f a b = m (\(a,b) -> f a b) (a,b)@@ -114,7 +96,7 @@ memol0     :: (MonadCache k v m, Monad m) =>        (k -> m v) -> k -> m v-memol0 = memoln2 id+memol0 = memoln id id   -- | Uses the 1st transformer in stack for memoization cache@@ -123,7 +105,7 @@         MonadCache k v m,         Monad (t1 m)) =>        (k -> t1 m v) -> k -> t1 m v-memol1 = memoln2 lift+memol1 = memoln lift id   -- | Uses the 2nd transformer in stack for memoization cache@@ -161,7 +143,6 @@       Monad (t2 (t3 (t4 m))),       Monad (t1 (t2 (t3 (t4 m)))) ) =>      (k -> t1 (t2 (t3 (t4 m))) v) -> k -> t1 (t2 (t3 (t4 m))) v---memol4 :: (MonadTrans t4, MonadCache k v m, Monad (t1 (t2 (t3 (t4 m))))) =>  (k -> t1 (t2 (t3 (t4 m))) v) -> k -> t1 (t2 (t3 (t4 m))) v memol4 = memoln (lift.lift.lift.lift) id  @@ -182,22 +163,30 @@  instance (MonadCache (r,k) v m) => MonadMemo k v (ReaderT r m) where     memo f k = do-      e <- ask-      memoln lift (e,) f k+      r <- ask+      memoln lift (r,) f k -instance (Monoid w, MonadCache k (v,w) m) => MonadMemo k v (Lazy.WriterT w m) where-    memo f = Lazy.WriterT . memol0 (Lazy.runWriterT . f)+instance (Monoid w, MonadCache k (v,w) m) => MonadMemo k v (WL.WriterT w m) where+    memo f = WL.WriterT . memol0 (WL.runWriterT . f) -instance (Monoid w, MonadCache k (v,w) m) => MonadMemo k v (Strict.WriterT w m) where-    memo f = Strict.WriterT . memol0 (Strict.runWriterT . f)+instance (Monoid w, MonadCache k (v,w) m) => MonadMemo k v (WS.WriterT w m) where+    memo f = WS.WriterT . memol0 (WS.runWriterT . f)  -instance (MonadCache (s,k) v m) => MonadMemo k v (Lazy.StateT s m) where+instance (MonadCache (s,k) v m) => MonadMemo k v (SL.StateT s m) where     memo f k = do-      s <- Lazy.get+      s <- SL.get       memoln lift (s,) f k -instance (MonadCache (s,k) v m) => MonadMemo k v (Strict.StateT s m) where+instance (MonadCache (s,k) v m) => MonadMemo k v (SS.StateT s m) where     memo f k = do-      s <- Strict.get+      s <- SS.get       memoln lift (s,) f k+++--instance (Monoid w, MonadCache (r,w,s,k) v m) => MonadMemo k v (RWSL.RWST r w s m) where+--    memo f k = do+--      r <- RWSL.ask+--      s <- RWSL.get+--      (_,w) <- RWSL.listen+--      memoln lift (r,s,w,) f k

@@ -76,8 +76,8 @@  ) where -import Control.Monad.Memo.Class-import Control.Monad.Trans.Memo.Strict+import Control.Monad.Memo+ import Control.Monad.Identity import Control.Monad.List import Control.Monad.Cont@@ -100,6 +100,19 @@  evalFibm :: Integer -> Integer evalFibm = startEvalMemo . fibm++-- infix form+fibm' :: (Num n, Ord n) => n -> Memo n n n+fibm' 0 = return 0+fibm' 1 = return 1+fibm' n = memo fibm' (n-1) `mp` memo fibm' (n-2)+    where mp = liftM2 (+)++-- applicative form+fibm'' :: (Num n, Ord n) => n -> Memo n n n+fibm'' 0 = return 0+fibm'' 1 = return 1+fibm'' n = (+) <$> memo fibm'' (n-1) <*> memo fibm'' (n-2)   --

@@ -0,0 +1,70 @@+{- |+Module      :  Control.Monad.Trans.Memo.Map+Copyright   :  (c) Eduard Sergeev 2011+License     :  BSD-style (see the file LICENSE)++Maintainer  :  eduard.sergeev@gmail.com+Stability   :  experimental+Portability :  non-portable (multi-param classes, functional dependencies)++MemoT as a specialization of MemoStateT with Data.Map as a container++-}++{-# LANGUAGE NoImplicitPrelude, MultiParamTypeClasses, FlexibleInstances #-}++module Control.Monad.Trans.Memo.Map (++   MemoT,+   runMemoT,+   evalMemoT,+   startRunMemoT,+   startEvalMemoT,++   Memo,+   runMemo,+   evalMemo,+   startRunMemo,+   startEvalMemo,++) where++import Data.Ord+import Data.MapLike.Instances++import Control.Monad.Identity+import Control.Monad.Trans.Memo.State++import qualified Data.Map as M+++type MemoT k v = MemoStateT (M.Map k v) k v++type Memo k v = MemoT k v Identity+++runMemoT :: MemoT k v m a -> M.Map k v -> m (a, M.Map k v)+runMemoT = runMemoStateT++evalMemoT :: Monad m => MemoT k v m a -> M.Map k v -> m a+evalMemoT = evalMemoStateT++runMemo :: Memo k v a -> M.Map k v -> (a, M.Map k v)+runMemo = runMemoState++evalMemo :: Memo k v a -> M.Map k v -> a+evalMemo = evalMemoState++++startRunMemoT :: Monad m => MemoT k v m a -> m (a, M.Map k v)+startRunMemoT = (`runMemoT` M.empty)++startEvalMemoT :: Monad m => MemoT k v m a -> m a+startEvalMemoT = (`evalMemoT` M.empty)++startRunMemo :: Memo k v a -> (a, M.Map k v)+startRunMemo = (`runMemo` M.empty)++startEvalMemo :: Memo k v a -> a+startEvalMemo = (`evalMemo` M.empty)

@@ -0,0 +1,97 @@+{- |+Module      :  Control.Monad.Memo+Copyright   :  (c) Eduard Sergeev 2011+License     :  BSD-style (see the file LICENSE)++Maintainer  :  eduard.sergeev@gmail.com+Stability   :  experimental+Portability :  non-portable (multi-param classes, flexible instances)++Defines "MemoStateT" - generalized (to any "Data.MapLike" content) memoization monad transformer++-}++{-# LANGUAGE NoImplicitPrelude, MultiParamTypeClasses, FlexibleInstances #-}++module Control.Monad.Trans.Memo.State+(+ +    MemoStateT(..),+    runMemoStateT,+    evalMemoStateT,++    MemoState,+    runMemoState,+    evalMemoState,++) where+++import Data.Tuple+import Data.Ord+import Data.Function+import Control.Applicative+import Control.Monad.State.Strict+import Control.Monad.Identity++import qualified Data.MapLike as M+import Control.Monad.Memo.Class+++-- MonadMemo and MonadCache implementation using std. 'Control.Monad.State' transformer with generic 'Data.MapLike' container for a cache+newtype MemoStateT c k v m a = MemoStateT { toStateT :: StateT c m a }+++runMemoStateT :: MemoStateT c k v m a -> c -> m (a, c)+runMemoStateT = runStateT . toStateT++evalMemoStateT :: (Monad m) => MemoStateT c k v m a -> c -> m a+evalMemoStateT m s = runMemoStateT m s >>= return . fst+++type MemoState c k v = MemoStateT c k v Identity++runMemoState :: MemoState c k v a -> c -> (a, c)+runMemoState m = runIdentity . runMemoStateT m++evalMemoState :: MemoState c k v a -> c -> a+evalMemoState m = runIdentity . evalMemoStateT m+++instance (Functor m) => Functor (MemoStateT c k v m) where+    fmap f m = MemoStateT $ fmap f (toStateT m)++instance (Functor m, Monad m) => Applicative (MemoStateT c k v m) where+    pure  = return +    (<*>) = ap++instance (Functor m, MonadPlus m) => Alternative (MemoStateT l k v m) where+    empty = mzero+    (<|>) = mplus++instance (Monad m) => Monad (MemoStateT l k v m) where+    return = MemoStateT . return+    m >>= k = MemoStateT $ (toStateT m) >>= (toStateT . k) +    m >> n = MemoStateT $ (toStateT m) >> (toStateT n) ++instance (MonadPlus m) => MonadPlus (MemoStateT l k v m) where+    mzero       = MemoStateT mzero+    m `mplus` n = MemoStateT $ toStateT m `mplus` toStateT n++instance (MonadFix m) => MonadFix (MemoStateT l k v m) where+    mfix f = MemoStateT $ mfix (toStateT . f)+++instance (Monad m, M.MapLike c k v) => MonadCache k v (MemoStateT c k v m) where+    lookup k = MemoStateT $ get >>= return . M.lookup k+    add k v  = MemoStateT $ modify $ \m -> M.add k v m++instance (Monad m, M.MapLike c k v) => MonadMemo k v (MemoStateT c k v m) where+    memo = memol0+++instance (MonadIO m) => MonadIO (MemoStateT l k v m) where+    liftIO = lift . liftIO++instance MonadTrans (MemoStateT l k v) where+    lift = MemoStateT . lift

@@ -1,102 +0,0 @@-{-# LANGUAGE NoImplicitPrelude, NoMonomorphismRestriction,-MultiParamTypeClasses, FlexibleInstances #-}--module Control.Monad.Trans.Memo.Strict-(- -MemoT(..),-runMemoT,-startRunMemoT,-evalMemoT,-startEvalMemoT,--Memo,-runMemo,-startRunMemo,-evalMemo,-startEvalMemo,--) where---import Data.Tuple-import Data.Ord-import Data.Function-import Control.Applicative-import Control.Monad.State.Strict-import Control.Monad.Identity-import qualified Data.Map as M --import Control.Monad.Memo.Class----newtype MemoT k v m a = MemoT { toStateT :: StateT (M.Map k v) m a }---runMemoT :: MemoT k v m a -> M.Map k v -> m (a, M.Map k v)-runMemoT = runStateT . toStateT--startRunMemoT :: MemoT k v m a -> m (a, M.Map k v)-startRunMemoT = (`runMemoT` M.empty)--type Memo k v = MemoT k v Identity--runMemo :: Memo k v a -> M.Map k v -> (a, M.Map k v)-runMemo m = runIdentity . runMemoT m--startRunMemo :: Memo k v a -> (a, M.Map k v)-startRunMemo = (`runMemo`M.empty)--evalMemoT :: (Monad m) => MemoT k v m a -> M.Map k v -> m a-evalMemoT m s = runMemoT m s >>= return . fst--startEvalMemoT :: (Monad m) => MemoT k v m a -> m a-startEvalMemoT = (`evalMemoT` M.empty)--evalMemo :: Memo k v a -> M.Map k v -> a-evalMemo m = runIdentity . evalMemoT m--startEvalMemo :: Memo k v a -> a-startEvalMemo = (`evalMemo`M.empty)-----instance (Functor m) => Functor (MemoT k v m) where-    fmap f m = MemoT $ fmap f (toStateT m)--instance (Functor m, Monad m) => Applicative (MemoT k v m) where-    pure  = return -    (<*>) = ap--instance (Functor m, MonadPlus m) => Alternative (MemoT k v m) where-    empty = mzero-    (<|>) = mplus--instance (Monad m) => Monad (MemoT k v m) where-    return = MemoT . return-    m >>= k = MemoT $ (toStateT m) >>= (toStateT . k) -    m >> n = MemoT $ (toStateT m) >> (toStateT n) --instance (MonadPlus m) => MonadPlus (MemoT k v m) where-    mzero       = MemoT mzero-    m `mplus` n = MemoT $ toStateT m `mplus` toStateT n--instance (MonadFix m) => MonadFix (MemoT k v m) where-    mfix f = MemoT $ mfix (toStateT . f)---instance (Monad m, Ord k) => MonadCache k v (MemoT k v m) where-    lookup k = MemoT $ get >>= return . M.lookup k-    add k v  = MemoT $ modify $ \m -> M.insert k v m--instance (Monad m, Ord k) => MonadMemo k v (MemoT k v m) where-    memo = memol0---instance (MonadIO m) => MonadIO (MemoT k v m) where-    liftIO = lift . liftIO--instance MonadTrans (MemoT k v) where-    lift = MemoT . lift

@@ -0,0 +1,30 @@+{- |+Module      :  Data.MapLike+Copyright   :  (c) Eduard Sergeev 2011+License     :  BSD-style (see the file LICENSE)++Maintainer  :  eduard.sergeev@gmail.com+Stability   :  experimental+Portability :  non-portable (multi-param classes, functional dependencies)++Defines MapLike typeclass - generalized interface to Data.Map, Data.HashMap etc.++-}++{-# LANGUAGE NoImplicitPrelude, MultiParamTypeClasses, FunctionalDependencies #-}++module Data.MapLike (++   MapLike(..),++) where++import Data.Maybe++-- | And abstract interface to the container which can store 'v' indexed by 'k'+class MapLike c k v | c -> k, c -> v where+    lookup :: k -> c -> Maybe v+    add :: k -> v -> c -> c+++

@@ -0,0 +1,37 @@+{- |+Module      :  Data.MapLike.Instances+Copyright   :  (c) Eduard Sergeev 2011+License     :  BSD-style (see the file LICENSE)++Maintainer  :  eduard.sergeev@gmail.com+Stability   :  experimental+Portability :  non-portable (multi-param classes, functional dependencies)++Defines MapLike instances declaration for standard data types++-}++{-# LANGUAGE NoImplicitPrelude, MultiParamTypeClasses, FlexibleInstances #-}++module Data.MapLike.Instances (++   MapLike(..)++) where++import Data.Ord+import Data.Int+import Data.MapLike   +import qualified Data.Map as M+import qualified Data.IntMap as IM+++-- | Data.Map is a default implementation (not the fastest but well-known)+instance Ord k => MapLike (M.Map k v) k v where+    add = M.insert+    lookup = M.lookup++-- | Data.IntMap is usually more efficient that Data.Map if @k :: Int@ +instance MapLike (IM.IntMap v) Int v where+    add = IM.insert+    lookup = IM.lookup

@@ -4,7 +4,7 @@ -- The package version. See the Haskell package versioning policy -- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for -- standards guiding when and how versions should be incremented.-Version:             0.2.0+Version:             0.3.0  -- A short (one-line) description of the package. Synopsis:            Memoization monad transformer@@ -40,7 +40,8 @@  Extra-source-files: 	Tests.hs,-	Control/Monad/Memo/Test.hs+	Control/Monad/Memo/Test.hs,+	CHANGES  source-repository head   type:		  svn@@ -62,7 +63,10 @@   exposed-modules:      Control.Monad.Memo,      Control.Monad.Memo.Class,-     Control.Monad.Trans.Memo.Strict+     Control.Monad.Trans.Memo.State,+     Control.Monad.Trans.Memo.Map,+     Data.MapLike,+     Data.MapLike.Instances    if flag(examples)      exposed-modules: Control.Monad.Memo.Example