Portability | non-portable (multi-param classes, functional dependencies) |
---|---|
Stability | experimental |
Maintainer | eduard.sergeev@gmail.com |
- MonadMemo class
- The Memo monad
- The 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
- class Monad m => MonadMemo k v m | m -> k, m -> v where
- memo :: (k -> m v) -> k -> m v
- 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
- newtype MemoT k v m a = MemoT {}
- 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 :: MemoT k v m a -> m (a, Map k v)
- startEvalMemoT :: Monad m => MemoT k v m a -> m a
- module Control.Monad
- module Control.Monad.Trans
- 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
MonadMemo class
class Monad m => MonadMemo k v m | m -> k, m -> v whereSource
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, Ord k) => MonadMemo k v (MemoT k v m) |
The Memo monad
startRunMemo :: Memo k v a -> (a, Map k v)Source
startEvalMemo :: Memo k v a -> aSource
The MemoT monad transformer
(Monad m, Ord k) => MonadMemo k v (MemoT k v m) | |
(Monad m, Ord k) => MonadCache k v (MemoT k v m) | |
MonadTrans (MemoT k v) | |
Monad m => Monad (MemoT k v m) | |
Functor m => Functor (MemoT k v m) | |
MonadFix m => MonadFix (MemoT k v m) | |
MonadPlus m => MonadPlus (MemoT k v m) | |
(Functor m, Monad m) => Applicative (MemoT k v m) | |
(Functor m, MonadPlus m) => Alternative (MemoT k v m) | |
MonadIO m => MonadIO (MemoT k v m) |
startRunMemoT :: MemoT k v m a -> m (a, Map k v)Source
startEvalMemoT :: Monad m => MemoT k v m a -> m aSource
module Control.Monad
module Control.Monad.Trans
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
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
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