Control.Monad.Memo

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

Documentation

module Control.Monad

module Control.Monad.Trans

module Data.MapLike

module Data.MaybeLike

MonadMemo class

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

Memoization interface

Methods

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

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, s) m => MonadMemo k v (StateT s m)

MonadCache (s, k) (v, s) 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)

(PrimMonad m, ~ * (PrimState m) s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m)

(PrimMonad m, ~ * (PrimState m) s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m)

(PrimMonad m, ~ * (PrimState m) s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m)

(Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m)

(Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m)

(Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadMemo k v (Cache c k e 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 Identity

Memoization monad based on StateCache to be used with pure cache containers which support MapLike interface

runMemoState :: MemoState c k v a -> c -> (a, c)

Returns the pair of the result of MonadMemo computation along with the final state of the internal pure container

evalMemoState :: MemoState c k v a -> c -> a

Returns the result of MonadMemo computation discarding the cache

Generalized MemoStateT monad transformer

type MemoStateT s k v = StateCache (Container s)

Memoization monad transformer based on StateCache to be used with pure cache containers which support MapLike interface

runMemoStateT :: Monad m => MemoStateT s k v m a -> s -> m (a, s)

Returns the pair of the result of MonadMemo computation along with the final state of the internal pure container wrapped in monad

evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a

Returns the result of MonadMemo computation wrapped in monad. This function discards the cache

Map-based Memo monad

type Memo k v = MemoT k v Identity

Memoization monad which uses Map as a cache container

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

Given an initial cache, compute the result of a memoized computation along with the final state of the cache

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

Given an initial state, compute the result of a memoized computation discarding the final state of the cache

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

Compute the result of memoized computation along with the final state of the cache. This function uses empty Map as an initial state

startEvalMemo :: Memo k v a -> a

Compute the result of a memoized computation discarding the final state of the cache. This function uses empty Map as an initial state

Map-based MemoT monad transformer

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

Memoization monad transformer which uses Map as a cache container

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

Given an initial cache, compute the result of a memoized computation along with the final state of the cache

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

Given an initial state, compute the result of a memoized computation discarding the final state of the cache

startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v)

Compute the result of memoized computation along with the final state of the cache. This function uses empty Map as an initial state

startEvalMemoT :: Monad m => MemoT k v m a -> m a

Compute the result of a memoized computation discarding the final state of the cache. This function uses empty Map as an initial state

Array-based Memo monad

ArrayCache for boxed types

type ArrayCache k e m = Cache (Array m) k e m

Memoization monad based on mutable boxed array

class MaybeLike e v => ArrayMemo v e | v -> e

This is just to be able to infer the type of the ArrayCache element

Type families could be used instead but due to the bug in 7.4.* we cannot use them here

Instances

MaybeLike (Maybe v) v => ArrayMemo v (Maybe v)

evalArrayMemo

Arguments

:: (Ix k, MArray (Array m) e m, ArrayMemo v e)

=> ArrayCache k e m a

memoized computation to be evaluated

-> (k, k)

array key range

-> m a

computation result

Evaluate computation using boxed array

Key range should cover all possible keys used in computation otherwise not in range error is generated by array

runArrayMemo

Arguments

:: (Ix k, MArray (Array m) e m, ArrayMemo v e)

=> ArrayCache k e m a

memoized computation to be evaluated

-> (k, k)

array key range

-> m (a, Array m k e)

computation result and final array cache

Evaluate computation and the final content of array cache using boxed array

Key range should cover all possible keys used in computation otherwise not in range error is generated by array

ArrayCache for unboxed types

type UArrayCache k e m = Cache (UArray m) k e m

Memoization monad based on mutable unboxed array

class MaybeLike e v => UArrayMemo v e | v -> e

This is just to be able to infer the type of the UArrayCache element

Type families could be used instead but due to the bug in 7.4.* we cannot use them here

Instances

MaybeLike v v => UArrayMemo v v

evalUArrayMemo

Arguments

:: (Ix k, MArray (UArray m) e m, UArrayMemo v e)

=> UArrayCache k e m a

memoized computation to be evaluated

-> (k, k)

array key range

-> m a

computation result

Evaluate computation using unboxed array

Key range should cover all possible keys used in computation otherwise not in range error is generated by array

runUArrayMemo

Arguments

:: (Ix k, MArray (UArray m) e m, UArrayMemo v e)

=> UArrayCache k e m a

memoized computation to be evaluated

-> (k, k)

array key range

-> m (a, UArray m k e)

computation result and final array cache

Evaluate computation and the final content of array cache using unboxed array

Key range should cover all possible keys used in computation otherwise not in range error is generated by array

Vector-based Memo monad

VectorCache for boxed types

type VectorCache s e = Cache Vector s e

MonadCache based on boxed vector

class MaybeLike e v => VectorMemo v e | v -> e

This is just to be able to infer the type of the VectorCache element.

Instances

MaybeLike (Maybe v) v => VectorMemo v (Maybe v)

evalVectorMemo

Arguments

:: (PrimMonad m, VectorMemo v e)

=> VectorCache (PrimState m) e m a

memoized computation

-> Int

vector length

-> m a

result

Evaluate computation using mutable boxed vector

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

runVectorMemo

Arguments

:: (PrimMonad m, VectorMemo v e)

=> VectorCache (PrimState m) e m a

memoized computation

-> Int

vector length

-> m (a, Vector (PrimState m) e)

result and final vector cache

Evaluate computation using mutable boxed vector. It also returns the final content of the vector cache

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

VectorCache for unboxed types

type UVectorCache s e = Cache UVector s e

MonadCache based on unboxed vector

class MaybeLike e v => UVectorMemo v e | v -> e

This is just to be able to infer the type of the UVectorCache element.

Instances

MaybeLike v v => UVectorMemo v v

evalUVectorMemo

Arguments

:: (PrimMonad m, MVector UVector e, UVectorMemo v e)

=> UVectorCache (PrimState m) e m a

memoized computation

-> Int

vector length

-> m a

result

Evaluate computation using mutable unboxed vector

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

runUVectorMemo

Arguments

:: (PrimMonad m, MVector UVector e, UVectorMemo v e)

=> UVectorCache (PrimState m) e m a

memoized computation

-> Int

vector length

-> m (a, UVector (PrimState m) e)

result and final vector cache

Evaluate computation using mutable unboxed vector. It also returns the final content of the vector cache

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

Adapter for memoization of multi-argument functions

for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv

Adapter for memoization of two-argument function

for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mv

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 -> mv

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 v

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 v

Uses current monad's memoization cache

memol1 :: (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v

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) v

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)) v

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))) v

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 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

Example 5: Alternative memo caches

Given a monadic function definition it is often possible to execute it using different memo-cache (MonadCache) implementations. For example ArrayCache when used can dramatically reduce function computation time and memory usage.

For example the same Fibonacci function:

fibm 0 = return 0
fibm 1 = return 1
fibm n = (+) <$> memo fibm (n-1) <*> memo fibm (n-2)

can easily be run using mutable array in ST monad:

evalFibmSTA :: Integer -> Integer
evalFibmSTA n = runST $ evalArrayMemo (fibm n) (0,n)

or, if we change its return type to a primitive (unboxed) value, we can use even more efficient unboxed array STUArray:

evalFibmSTUA :: Integer -> Double
evalFibmSTUA n = runST $ evalUArrayMemo (fibm n) (0,n)

Finally if we want to achieve the best performance within monad-memo, we can switch to unboxed Vector-based MemoCache (vectors support only Int as a key so we have to change the type):

evalFibmSTUV :: Int -> Double
evalFibmSTUV n = runST $ evalUVectorMemo (fibm n) (n+1)

Note that IO monad can be used instead of ST:

evalFibmIOUV :: Int -> IO Double
evalFibmIOUV n = evalUVectorMemo (fibm n) (n+1)