| Copyright | (c) Eduard Sergeev 2011 |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | eduard.sergeev@gmail.com |
| Stability | experimental |
| Portability | non-portable (multi-param classes, functional dependencies) |
| Safe Haskell | None |
| Language | Haskell2010 |
Control.Monad.Memo
Contents
- MonadMemo class
- Generalized Memo monad
- Generalized MemoStateT monad transformer
- Map-based Memo monad
- Map-based MemoT monad transformer
- Array-based Memo monad
- Vector-based Memo monad
- 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
- Example 5: Alternative memo caches
Description
Importing just this module is sufficient for most cases of the package usage
Synopsis
- class Applicative m => Monad (m :: Type -> Type) where
- join :: Monad m => m (m a) -> m a
- class Functor (f :: Type -> Type) where
- (=<<) :: Monad m => (a -> m b) -> m a -> m b
- ap :: Monad m => m (a -> b) -> m a -> m b
- liftM :: Monad m => (a1 -> r) -> m a1 -> m r
- liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
- liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
- liftM4 :: Monad m => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r
- liftM5 :: Monad m => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r
- when :: Applicative f => Bool -> f () -> f ()
- (<$!>) :: Monad m => (a -> b) -> m a -> m b
- (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
- (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
- filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
- foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
- foldM_ :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m ()
- forever :: Applicative f => f a -> f b
- mapAndUnzipM :: Applicative m => (a -> m (b, c)) -> [a] -> m ([b], [c])
- mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a
- replicateM :: Applicative m => Int -> m a -> m [a]
- replicateM_ :: Applicative m => Int -> m a -> m ()
- unless :: Applicative f => Bool -> f () -> f ()
- zipWithM :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m [c]
- zipWithM_ :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m ()
- forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
- mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
- msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
- sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
- void :: Functor f => f a -> f ()
- forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
- class (Alternative m, Monad m) => MonadPlus (m :: Type -> Type) where
- mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
- sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)
- guard :: Alternative f => Bool -> f ()
- class Monad m => MonadFail (m :: Type -> Type) where
- fail :: String -> m a
- class (forall (m :: Type -> Type). Monad m => Monad (t m)) => MonadTrans (t :: (Type -> Type) -> Type -> Type) where
- module Data.MapLike
- module Data.MaybeLike
- class Monad m => MonadMemo k v (m :: Type -> Type) | m -> k, m -> v where
- memo :: (k -> m v) -> k -> m v
- type MemoState c k v = MemoStateT c k v Identity
- runMemoState :: MemoState c k v a -> c -> (a, c)
- evalMemoState :: MemoState c k v a -> c -> a
- type MemoStateT s k v = StateCache (Container s)
- runMemoStateT :: Monad m => MemoStateT s k v m a -> s -> m (a, s)
- evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a
- 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
- type MemoT k v = MemoStateT (Map k v) k v
- runMemoT :: Monad m => 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 :: Monad m => MemoT k v m a -> m (a, Map k v)
- startEvalMemoT :: Monad m => MemoT k v m a -> m a
- type ArrayCache k e (m :: Type -> Type) = Cache (Array m) k e m
- class MaybeLike e v => ArrayMemo v e | v -> e
- evalArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m a
- runArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m (a, Array m k e)
- type UArrayCache k e (m :: Type -> Type) = Cache (UArray m) k e m
- class MaybeLike e v => UArrayMemo v e | v -> e
- evalUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m a
- runUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m (a, UArray m k e)
- type VectorCache s e = Cache Vector s e
- class MaybeLike e v => VectorMemo v e | v -> e
- evalVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m a
- runVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m (a, Vector (PrimState m) e)
- type UVectorCache s e = Cache UVector s e
- class MaybeLike e v => UVectorMemo v e | v -> e
- evalUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m a
- runUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m (a, UVector (PrimState m) e)
- 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 :: forall t1 k v (m :: Type -> Type). (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v
- memol2 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (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 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (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 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) (t4 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (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
Documentation
class Applicative m => Monad (m :: Type -> Type) where #
Minimal complete definition
Instances
| Monad Complex | |
| Monad First | |
| Monad Last | |
| Monad Max | |
| Monad Min | |
| Monad Seq | |
| Monad Tree | |
| Monad NonEmpty | |
| Monad Identity | |
| Monad First | |
| Monad Last | |
| Monad Dual | |
| Monad Product | |
| Monad Sum | |
| Monad Par1 | |
| Monad IO | |
| Monad Array | |
| Monad SmallArray | |
Defined in Data.Primitive.SmallArray Methods (>>=) :: SmallArray a -> (a -> SmallArray b) -> SmallArray b # (>>) :: SmallArray a -> SmallArray b -> SmallArray b # return :: a -> SmallArray a # | |
| Monad Q | |
| Monad Vector | |
| Monad Id | |
| Monad Vector | |
| Monad Maybe | |
| Monad Solo | |
| Monad [] | |
| Monad m => Monad (WrappedMonad m) | |
| Monad (SetM s) | |
| ArrowApply a => Monad (ArrowMonad a) | |
| Monad (Either e) | |
| Monad (U1 :: Type -> Type) | |
| Monad (ST s) | |
| Monad m => Monad (MaybeT m) | |
| Monoid a => Monad ((,) a) | |
| (Applicative f, Monad f) => Monad (WhenMissing f x) | |
| Monad m => Monad (Kleisli m a) | |
| Monad f => Monad (Ap f) | |
| Monad f => Monad (Alt f) | |
| Monad f => Monad (Rec1 f) | |
| Monad m => Monad (ReaderCache c m) Source # | |
Defined in Control.Monad.Trans.Memo.ReaderCache Methods (>>=) :: ReaderCache c m a -> (a -> ReaderCache c m b) -> ReaderCache c m b # (>>) :: ReaderCache c m a -> ReaderCache c m b -> ReaderCache c m b # return :: a -> ReaderCache c m a # | |
| Monad m => Monad (StateCache c m) Source # | |
Defined in Control.Monad.Trans.Memo.StateCache Methods (>>=) :: StateCache c m a -> (a -> StateCache c m b) -> StateCache c m b # (>>) :: StateCache c m a -> StateCache c m b -> StateCache c m b # return :: a -> StateCache c m a # | |
| (Monoid w, Functor m, Monad m) => Monad (AccumT w m) | |
| Monad m => Monad (ExceptT e m) | |
| Monad m => Monad (IdentityT m) | |
| Monad m => Monad (ReaderT r m) | |
| Monad m => Monad (SelectT r m) | |
| Monad m => Monad (StateT s m) | |
| Monad m => Monad (StateT s m) | |
| Monad m => Monad (WriterT w m) | |
| (Monoid w, Monad m) => Monad (WriterT w m) | |
| (Monoid w, Monad m) => Monad (WriterT w m) | |
| Monad m => Monad (Reverse m) | |
| (Monoid a, Monoid b) => Monad ((,,) a b) | |
| (Monad f, Monad g) => Monad (Product f g) | |
| (Monad f, Applicative f) => Monad (WhenMatched f x y) | |
| (Applicative f, Monad f) => Monad (WhenMissing f k x) | |
| (Monad f, Monad g) => Monad (f :*: g) | |
| Monad (ContT r m) | |
| (Monoid a, Monoid b, Monoid c) => Monad ((,,,) a b c) | |
| Monad ((->) r) | |
| (Monad f, Applicative f) => Monad (WhenMatched f k x y) | |
| Monad f => Monad (M1 i c f) | |
| Monad m => Monad (RWST r w s m) | |
| (Monoid w, Monad m) => Monad (RWST r w s m) | |
| (Monoid w, Monad m) => Monad (RWST r w s m) | |
class Functor (f :: Type -> Type) where #
Minimal complete definition
Instances
liftM5 :: Monad m => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r #
mapAndUnzipM :: Applicative m => (a -> m (b, c)) -> [a] -> m ([b], [c]) #
replicateM :: Applicative m => Int -> m a -> m [a] #
replicateM_ :: Applicative m => Int -> m a -> m () #
class (Alternative m, Monad m) => MonadPlus (m :: Type -> Type) where #
Minimal complete definition
Nothing
Instances
class Monad m => MonadFail (m :: Type -> Type) where #
Instances
class (forall (m :: Type -> Type). Monad m => Monad (t m)) => MonadTrans (t :: (Type -> Type) -> Type -> Type) where #
Instances
module Data.MapLike
module Data.MaybeLike
MonadMemo class
class Monad m => MonadMemo k v (m :: Type -> Type) | m -> k, m -> v where Source #
Memoization interface
Instances
| MonadCache k (Maybe v) m => MonadMemo k v (MaybeT m) Source # | |
Defined in Control.Monad.Memo.Class | |
| MonadCache k (Either e v) m => MonadMemo k v (ExceptT e m) Source # | |
Defined in Control.Monad.Memo.Class | |
| MonadCache k v m => MonadMemo k v (IdentityT m) Source # | |
Defined in Control.Monad.Memo.Class | |
| MonadCache (r, k) v m => MonadMemo k v (ReaderT r m) Source # | |
Defined in Control.Monad.Memo.Class | |
| MonadCache (s, k) (v, s) m => MonadMemo k v (StateT s m) Source # | |
Defined in Control.Monad.Memo.Class | |
| MonadCache (s, k) (v, s) m => MonadMemo k v (StateT s m) Source # | |
Defined in Control.Monad.Memo.Class | |
| (Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) Source # | |
Defined in Control.Monad.Memo.Class | |
| (Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) Source # | |
Defined in Control.Monad.Memo.Class | |
| MonadCache k v m => MonadMemo k v (ContT r m) Source # | |
Defined in Control.Monad.Memo.Class | |
| (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # | |
| (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # | |
| (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # | |
| (Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadMemo k v (Cache c k e m) Source # | |
| (Monad m, MapLike c k v) => MonadMemo k v (MemoStateT c k v m) Source # | |
Defined in Control.Monad.Trans.Memo.State Methods memo :: (k -> MemoStateT c k v m v) -> k -> MemoStateT c k v m v Source # | |
| (Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m) Source # | |
Defined in Control.Monad.Memo.Class | |
| (Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m) Source # | |
Defined in Control.Monad.Memo.Class | |
Generalized Memo monad
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
Generalized MemoStateT monad transformer
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
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 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
Map-based MemoT monad transformer
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
Array-based Memo monad
ArrayCache for boxed types
type ArrayCache k e (m :: Type -> Type) = 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 # | |
Defined 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 :: Type -> Type) = 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 # | |
Defined 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
Vector-based Memo monad
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 # | |
Defined 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 # | |
Defined 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 #
Uses current monad's memoization cache
memol1 :: forall t1 k v (m :: Type -> Type). (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 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (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 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (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 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) (t4 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (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)