Copyright (c) Eduard Sergeev 2011 BSD-style (see the file LICENSE) eduard.sergeev@gmail.com experimental non-portable (multi-param classes, functional dependencies) None Haskell2010

Description

Importing just this module is sufficient for most cases of the package usage

Synopsis

# Documentation

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

Memoization interface

Minimal complete definition

memo

Methods

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

Instances

type MemoState c k v = MemoStateT c k v Identity Source #

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) Source #

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

Returns the result of MonadMemo computation discarding the cache

type MemoStateT s k v = StateCache (Container s) Source #

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) Source #

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

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

type Memo k v = MemoT k v Identity Source #

Memoization monad which uses Map as a cache container

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

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

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) Source #

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

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

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

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) Source #

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

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) Source #

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

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

## ArrayCache for boxed types

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

Memoization monad based on mutable boxed array

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

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) Source # Instance detailsDefined in Control.Monad.Memo.Array.Instances

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

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

Memoization monad based on mutable unboxed array

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

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 Source # Instance detailsDefined in Control.Monad.Memo.Array.Instances

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

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

## VectorCache for boxed types

type VectorCache s e = Cache Vector s e Source #

MonadCache based on boxed vector

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

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

Instances
 MaybeLike (Maybe v) v => VectorMemo v (Maybe v) Source # Instance detailsDefined in Control.Monad.Memo.Vector.Instances

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

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

MonadCache based on unboxed vector

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

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

Instances
 MaybeLike v v => UVectorMemo v v Source # Instance detailsDefined in Control.Monad.Memo.Vector.Instances

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

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

Adapter for memoization of two-argument function

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

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

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

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

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

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

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

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

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 :: (Eq n, 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 :: (Eq n, 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 :: (Eq n, 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 100)

Or using applicative form:

fibm :: (Eq n, 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 :: Integer -> Integer evalFibM2 = startEvalMemo . startEvalMemoT . fibm2 # Example 3: Combining Memo with other transformers MonadMemo can be combined with other monads and transformers: With MonadWriter: fibmw :: (MonadWriter String m, MonadMemo Integer Integer m) => Integer -> m Integer 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 :: Integer -> (Integer, String)
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 :: (Eq n, 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)