Control.Monad.Memo (original) (raw)

Documentation

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

Memoization interface

Instances

Instances details

| MonadCache k (Maybe v) m => MonadMemo k v (MaybeT m) Source # | | | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> MaybeT m v) -> k -> MaybeT m v Source # | | | MonadCache (s, k) (v, s) m => MonadMemo k v (StateT s m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> StateT s m v) -> k -> StateT s m v Source # | | | MonadCache (s, k) (v, s) m => MonadMemo k v (StateT s m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> StateT s m v) -> k -> StateT s m v Source # | | | (Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> WriterT w m v) -> k -> WriterT w m v Source # | | | (Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> WriterT w m v) -> k -> WriterT w m v Source # | | | MonadCache (r, k) v m => MonadMemo k v (ReaderT r m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> ReaderT r m v) -> k -> ReaderT r m v Source # | | | MonadCache k (Either e v) m => MonadMemo k v (ExceptT e m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> ExceptT e m v) -> k -> ExceptT e m v Source # | | | MonadCache k v m => MonadMemo k v (IdentityT m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> IdentityT m v) -> k -> IdentityT m v Source # | | | MonadCache k v m => MonadMemo k v (ContT r m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> ContT r m v) -> k -> ContT r m v Source # | | | (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Vector.Unsafe Methodsmemo :: (Int -> Cache c s e m v) -> Int -> Cache c s e m v Source # | | | (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Vector.Expandable Methodsmemo :: (Int -> Cache c s e m v) -> Int -> Cache c s e m v Source # | | | (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Vector Methodsmemo :: (Int -> Cache c s e m v) -> Int -> Cache c s e m v Source # | | | (Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> RWST r w s m v) -> k -> RWST r w s m v Source # | | | (Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Class Methodsmemo :: (k -> RWST r w s m v) -> k -> RWST r w s m v Source # | | | (Monad m, MapLike c k v) => MonadMemo k v (MemoStateT c k v m) Source # | | | Instance detailsDefined in Control.Monad.Trans.Memo.State Methodsmemo :: (k -> MemoStateT c k v m v) -> k -> MemoStateT c k v m v Source # | | | (Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadMemo k v (Cache c k e m) Source # | | | Instance detailsDefined in Control.Monad.Memo.Array Methodsmemo :: (k -> Cache c k e m v) -> k -> Cache c k e m v Source # | |

Generalized Memo monad Generalized MemoStateT monad transformer Map-based Memo monad

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](/package/containers-0.6.2.1/docs/Data-Map-Strict.html#t:Map "Data.Map.Strict") 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](/package/containers-0.6.2.1/docs/Data-Map-Strict.html#t:Map "Data.Map.Strict") as an initial state

Map-based MemoT monad transformer

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 #

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

Array-based Memo monad ArrayCache for boxed types

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

This is just to be able to infer the type of the [ArrayCache](Control-Monad-Memo.html#t:ArrayCache "Control.Monad.Memo") element

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

Instances

Instances details

evalArrayMemo Source #

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

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

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

This is just to be able to infer the type of the [UArrayCache](Control-Monad-Memo.html#t:UArrayCache "Control.Monad.Memo") element

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

Instances

Instances details

evalUArrayMemo Source #

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

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

evalVectorMemo Source #

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

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

evalUVectorMemo Source #

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

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

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](Control-Monad-Memo.html#t:Memo "Control.Monad.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](Control-Monad-Memo.html#v:memo "Control.Monad.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](/package/base-4.14.1.0/docs/Data-Ord.html#t:Ord "Data.Ord") is required since internaly Memo implementation uses [Map](Data.html#v:Map "Data") to store and lookup memoized values

Then it can be run with [startEvalMemo](Control-Monad-Memo.html#v:startEvalMemo "Control.Monad.Memo")

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](Control-Monad-Memo.html#t:MonadMemo "Control.Monad.Memo") 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](Control-Monad-Memo.html#v:for2 "Control.Monad.Memo") 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](Control-Monad-Memo-Class.html#t:MonadCache "Control.Monad.Memo.Class")) implementations. For example [ArrayCache](Control-Monad-Memo.html#t:ArrayCache "Control.Monad.Memo") 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](/package/base-4.14.1.0/docs/Control-Monad-ST.html#v:ST "Control.Monad.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](/package/array-0.5.4.0/docs/Data-Array-ST.html#v:STUArray "Data.Array.ST"):

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](Control-Monad-Memo-Vector.html#t:Vector "Control.Monad.Memo.Vector")-based MemoCache (vectors support only [Int](/package/base-4.14.1.0/docs/Data-Int.html#t:Int "Data.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](/package/base-4.14.1.0/docs/System-IO.html#t:IO "System.IO") monad can be used instead of [ST](/package/base-4.14.1.0/docs/Control-Monad-ST.html#v:ST "Control.Monad.ST"):

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