Portability | non-portable (multi-param classes, functional dependencies) |
---|---|
Stability | experimental |
Maintainer | eduard.sergeev@gmail.com |
- MonadMemo class
- Generalized Memo monad
- Generalized MemoStateT monad transformer
- Map-based Memo monad
- Map-based MemoT monad transformer
- Adapter for memoization of multi-argument functions
- Memoization cache level access functions
- Example 1: Fibonacci numbers
- Example 2: Mutualy recursive definition with memoization
- Example 3: Combining Memo with other transformers
- Example 4: Memoization of multi-argument function
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
- module Control.Monad
- module Control.Monad.Trans
- module Data.MapLike
- class Monad m => MonadMemo k v m | m -> k, m -> v where
- memo :: (k -> m v) -> k -> m v
- type MemoState c k v = MemoStateT c k v Identity
- runMemoState :: MemoState c k v a -> c -> (a, c)
- evalMemoState :: MemoState c k v a -> c -> a
- newtype MemoStateT c k v m a = MemoStateT {}
- runMemoStateT :: MemoStateT c k v m a -> c -> m (a, c)
- evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a
- type Memo k v = MemoT k v Identity
- runMemo :: Memo k v a -> Map k v -> (a, Map k v)
- evalMemo :: Memo k v a -> Map k v -> a
- startRunMemo :: Memo k v a -> (a, Map k v)
- startEvalMemo :: Memo k v a -> a
- type MemoT k v = MemoStateT (Map k v) k v
- runMemoT :: MemoT k v m a -> Map k v -> m (a, Map k v)
- evalMemoT :: Monad m => MemoT k v m a -> Map k v -> m a
- startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v)
- startEvalMemoT :: Monad m => MemoT k v m a -> m a
- for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv
- for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mv
- for4 :: (((k1, k2, k3, k4) -> mv) -> (k1, k2, k3, k4) -> mv) -> (k1 -> k2 -> k3 -> k4 -> mv) -> k1 -> k2 -> k3 -> k4 -> mv
- memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) => (forall a. m1 a -> m2 a) -> (k1 -> k2) -> (k1 -> m2 v) -> k1 -> m2 v
- memol0 :: (MonadCache k v m, Monad m) => (k -> m v) -> k -> m v
- memol1 :: (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v
- memol2 :: (MonadTrans t1, MonadTrans t2, MonadCache k v m, Monad (t2 m), Monad (t1 (t2 m))) => (k -> t1 (t2 m) v) -> k -> t1 (t2 m) v
- memol3 :: (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadCache k v m, Monad (t3 m), Monad (t2 (t3 m)), Monad (t1 (t2 (t3 m)))) => (k -> t1 (t2 (t3 m)) v) -> k -> t1 (t2 (t3 m)) v
- memol4 :: (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadTrans t4, MonadCache k v m, Monad (t4 m), Monad (t3 (t4 m)), 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
Documentation
module Control.Monad
module Control.Monad.Trans
module Data.MapLike
MonadMemo class
class Monad m => MonadMemo k v m | m -> k, m -> v whereSource
Memoization interface
MonadCache k [v] m => MonadMemo k v (ListT m) | |
MonadCache k (Maybe v) m => MonadMemo k v (MaybeT m) | |
MonadCache k v m => MonadMemo k v (IdentityT m) | |
MonadCache (s, k) v m => MonadMemo k v (StateT s m) | |
MonadCache (s, k) v m => MonadMemo k v (StateT s m) | |
(Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) | |
(Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) | |
MonadCache (r, k) v m => MonadMemo k v (ReaderT r m) | |
(Error e, MonadCache k (Either e v) m) => MonadMemo k v (ErrorT e m) | |
MonadCache k v m => MonadMemo k v (ContT r m) | |
(Monad m, MapLike c k v) => MonadMemo k v (MemoStateT c k v m) |
Generalized Memo monad
type MemoState c k v = MemoStateT c k v IdentitySource
runMemoState :: MemoState c k v a -> c -> (a, c)Source
evalMemoState :: MemoState c k v a -> c -> aSource
Generalized MemoStateT monad transformer
newtype MemoStateT c k v m a Source
(Monad m, MapLike c k v) => MonadMemo k v (MemoStateT c k v m) | |
(Monad m, MapLike c k v) => MonadCache k v (MemoStateT c k v m) | |
MonadTrans (MemoStateT l k v) | |
Monad m => Monad (MemoStateT l k v m) | |
Functor m => Functor (MemoStateT c k v m) | |
MonadFix m => MonadFix (MemoStateT l k v m) | |
MonadPlus m => MonadPlus (MemoStateT l k v m) | |
(Functor m, Monad m) => Applicative (MemoStateT c k v m) | |
(Functor m, MonadPlus m) => Alternative (MemoStateT l k v m) | |
MonadIO m => MonadIO (MemoStateT l k v m) |
runMemoStateT :: MemoStateT c k v m a -> c -> m (a, c)Source
evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m aSource
Map-based Memo monad
startRunMemo :: Memo k v a -> (a, Map k v)Source
startEvalMemo :: Memo k v a -> aSource
Map-based MemoT monad transformer
type MemoT k v = MemoStateT (Map k v) k vSource
startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v)Source
startEvalMemoT :: Monad m => MemoT k v m a -> m aSource
Adapter for memoization of multi-argument functions
for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mvSource
Adapter for memoization of two-argument function
for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mvSource
Adapter for memoization of three-argument function
for4 :: (((k1, k2, k3, k4) -> mv) -> (k1, k2, k3, k4) -> mv) -> (k1 -> k2 -> k3 -> k4 -> mv) -> k1 -> k2 -> k3 -> k4 -> mvSource
Adapter for memoization of four-argument function
Memoization cache level access functions
memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) => (forall a. m1 a -> m2 a) -> (k1 -> k2) -> (k1 -> m2 v) -> k1 -> m2 vSource
Memoization for the current transformer in stack using a cache from an arbitrary transformer down the stack
memol0 :: (MonadCache k v m, Monad m) => (k -> m v) -> k -> m vSource
Uses current monad's memoization cache
memol1 :: (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m vSource
Uses the 1st transformer in stack for memoization cache
memol2 :: (MonadTrans t1, MonadTrans t2, MonadCache k v m, Monad (t2 m), Monad (t1 (t2 m))) => (k -> t1 (t2 m) v) -> k -> t1 (t2 m) vSource
Uses the 2nd transformer in stack for memoization cache
memol3 :: (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadCache k v m, Monad (t3 m), Monad (t2 (t3 m)), Monad (t1 (t2 (t3 m)))) => (k -> t1 (t2 (t3 m)) v) -> k -> t1 (t2 (t3 m)) vSource
Uses the 3rd transformer in stack for memoization cache
memol4 :: (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadTrans t4, MonadCache k v m, Monad (t4 m), Monad (t3 (t4 m)), Monad (t2 (t3 (t4 m))), Monad (t1 (t2 (t3 (t4 m))))) => (k -> t1 (t2 (t3 (t4 m))) v) -> k -> t1 (t2 (t3 (t4 m))) vSource
Uses the 4th transformer in stack for memoization cache
Example 1: Fibonacci numbers
Memoization can be specified whenever monadic computation is taking place. Including recursive definition. Classic example: Fibonacci number function: Here is simple non-monadic definition of it
fib :: (Num n) => n -> n fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
To use Memo
monad we need to convert it into monadic form:
fibm :: (Num n, Monad m) => n -> m n fibm 0 = return 0 fibm 1 = return 1 fibm n = do n1 <- fibm (n-1) n2 <- fibm (n-2) return (n1+n2)
Then we can specify which computation we want to memoize with memo
(both recursive calls to (n-1) and (n-2)):
fibm :: (Num n, Ord n) => n -> Memo n n n fibm 0 = return 0 fibm 1 = return 1 fibm n = do n1 <- memo fibm (n-1) n2 <- memo fibm (n-2) return (n1+n2)
NB: Ord
is required since internaly Memo implementation uses Data.Map
to store and lookup memoized values
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)
Example 2: Mutualy recursive definition with memoization
In order to use memoization for both mutually recursive function we need to use nested MemoT monad transformers
(one for each cache). Let's extend our Fibonacci function with meaningless extra function boo
which in turn uses fibm2
.
Memoization cache type for fibm2
(caches Integer -> Integer
) will be:
type MemoFib = MemoT Integer Integer
While cache for boo
(Double -> String
):
type MemoBoo = MemoT Double String
Stacking them together gives us te overall type for our combined memoization monad:
type MemoFB = MemoFib (MemoBoo Identity)
boo :: Double -> MemoFB String boo 0 = return "" boo n = do n1 <- memol1 boo (n-1) -- uses next in stack transformer (memol_1_): MemoBoo is nested in MemoFib fn <- memol0 fibm2 floor (n-1) -- uses current transformer (memol_0_): MemoFib return (show fn ++ n1)
fibm2 :: Integer -> MemoFB Integer fibm2 0 = return 0 fibm2 1 = return 1 fibm2 n = do l <- memol1 boo (fromInteger n) -- as in 'boo' we need to use 1st nested transformer here f1 <- memol0 fibm2 (n-1) -- and 0st (the current) for fibm2 f2 <- memol0 fibm2 (n-2) return (f1 + f2 + floor (read l))
evalFibM2 = startEvalMemo . startEvalMemoT . fibm2
Example 3: Combining Memo with other transformers
MonadMemo
can be combined with other monads and transformers:
With MonadWriter
:
fibmw :: (Num n, MonadWriter String m, MonadMemo n n m) => n -> m n fibmw 0 = return 0 fibmw 1 = return 1 fibmw n = do f1 <- memo fibmw (n-1) f2 <- memo fibmw (n-2) tell $ show n return (f1+f2)
evalFibmw = startEvalMemo . runWriterT . fibmw
Example 4: Memoization of multi-argument function
Functions with more than one argument (in curried form) can also be memoized with a help of forX
set of function:
For two-argument function we can use for2
function adapter:
-- Ackerman function classic definition ack :: Num n => n -> n -> n ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack m n = ack (m-1) (ack m (n-1)) -- Ackerman function memoized definition ackm :: (Num n, Ord n, MonadMemo (n, n) n m) => n -> n -> m n ackm 0 n = return (n+1) ackm m 0 = for2 memo ackm (m-1) 1 ackm m n = do n1 <- for2 memo ackm m (n-1) for2 memo ackm (m-1) n1 evalAckm :: (Num n, Ord n) => n -> n -> n evalAckm n m = startEvalMemo $ ackm n m