monad-memo-0.3.0: Memoization monad transformer

Portabilitynon-portable (multi-param classes, functional dependencies)
Stabilityexperimental
Maintainereduard.sergeev@gmail.com

Control.Monad.Memo

Contents

Description

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

Synopsis

Documentation

MonadMemo class

class Monad m => MonadMemo k v m | m -> k, m -> v whereSource

Memoization interface

Methods

memo :: (k -> m v) -> k -> m vSource

Instances

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

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

Constructors

MemoStateT 

Fields

toStateT :: StateT c m a
 

Instances

(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

type Memo k v = MemoT k v IdentitySource

runMemo :: Memo k v a -> Map k v -> (a, Map k v)Source

evalMemo :: Memo k v a -> Map k v -> aSource

startRunMemo :: Memo k v a -> (a, Map k v)Source

Map-based MemoT monad transformer

type MemoT k v = MemoStateT (Map k v) k vSource

runMemoT :: MemoT k v m a -> Map k v -> m (a, Map k v)Source

evalMemoT :: Monad m => MemoT k v m a -> Map k v -> m aSource

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