-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Memoization monad transformer
--   
--   Memoization monad transformer supporting most of the standard monad
--   transformers and a range of memoization cache types: from default pure
--   maps to extremely fast mutable vectors
--   
--   To add memoization behaviour to a monadic function:
--   
--   1) Add <a>Control.Monad.Memo.memo</a> combinator at the point when
--   memoization is required (i.e. recursive call)
--   
--   <pre>
--   import Control.Monad.Memo
--   
--   fibm 0 = return 0
--   fibm 1 = return 1
--   fibm n = do
--     n1 &lt;- memo fibm (n-1)
--     n2 &lt;- memo fibm (n-2)
--     return (n1+n2)
--   </pre>
--   
--   2) Use approprite <i>*eval*</i> or <i>*run*</i> function to evaluate
--   resulting <a>MonadMemo</a> monad:
--   
--   <pre>
--   startEvalMemo (fibm 100)
--   </pre>
--   
--   See detailed description and examples: <a>Control.Monad.Memo</a>
@package monad-memo
@version 0.5.1


-- | <ul>
--   <li><i>Computation type:</i> Interface for monadic computations which
--   can be memoized.</li>
--   </ul>
module Control.Monad.Memo.Class

-- | Interface for memoization cache Is necessary since memoization
--   mechanism from one transformer can use a cache from other (further
--   down the stack)
class Monad m => MonadCache k v m | m -> k, m -> v
lookup :: MonadCache k v m => k -> m (Maybe v)
add :: MonadCache k v m => k -> v -> m ()

-- | Memoization interface
class Monad m => MonadMemo k v m | m -> k, m -> v
memo :: MonadMemo k v m => (k -> m v) -> k -> m v

-- | Adapter for memoization of two-argument function
for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv

-- | Adapter for memoization of three-argument function
for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mv

-- | Adapter for memoization of four-argument function
for4 :: (((k1, k2, k3, k4) -> mv) -> (k1, k2, k3, k4) -> mv) -> (k1 -> k2 -> k3 -> k4 -> mv) -> k1 -> k2 -> k3 -> k4 -> mv

-- | Memoization for the current transformer in stack using a cache from an
--   arbitrary transformer down the stack
memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) => (forall a. m1 a -> m2 a) -> (k1 -> k2) -> (k1 -> m2 v) -> k1 -> m2 v

-- | Uses current monad's memoization cache
memol0 :: (MonadCache k v m, Monad m) => (k -> m v) -> k -> m v

-- | Uses the 1st transformer in stack for memoization cache
memol1 :: (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v

-- | Uses the 2nd 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 3rd 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 4th 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
instance Control.Monad.Memo.Class.MonadCache k v m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Identity.IdentityT m)
instance Control.Monad.Memo.Class.MonadCache k v m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Cont.ContT r m)
instance Control.Monad.Memo.Class.MonadCache k (GHC.Maybe.Maybe v) m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Maybe.MaybeT m)
instance Control.Monad.Memo.Class.MonadCache k (Data.Either.Either e v) m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Except.ExceptT e m)
instance Control.Monad.Memo.Class.MonadCache (r, k) v m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Reader.ReaderT r m)
instance (GHC.Base.Monoid w, Control.Monad.Memo.Class.MonadCache k (v, w) m) => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Writer.Lazy.WriterT w m)
instance (GHC.Base.Monoid w, Control.Monad.Memo.Class.MonadCache k (v, w) m) => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Writer.Strict.WriterT w m)
instance Control.Monad.Memo.Class.MonadCache (s, k) (v, s) m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.State.Strict.StateT s m)
instance Control.Monad.Memo.Class.MonadCache (s, k) (v, s) m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.State.Lazy.StateT s m)
instance (GHC.Base.Monoid w, Control.Monad.Memo.Class.MonadCache (r, s, k) (v, s, w) m) => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.RWS.Lazy.RWST r w s m)
instance (GHC.Base.Monoid w, Control.Monad.Memo.Class.MonadCache (r, s, k) (v, s, w) m) => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.RWS.Strict.RWST r w s m)


-- | Generic StateCache - wrapper around <a>ReaderT</a>
module Control.Monad.Trans.Memo.ReaderCache
data ReaderCache c m a
evalReaderCache :: ReaderCache r m a -> r -> m a

-- | Returns internal container
container :: Monad m => ReaderCache c m c
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c)
instance Control.Monad.Fix.MonadFix m => Control.Monad.Fix.MonadFix (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Base.MonadPlus m => GHC.Base.MonadPlus (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Base.Monad m => GHC.Base.Monad (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Base.Alternative m => GHC.Base.Alternative (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Base.Applicative m => GHC.Base.Applicative (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Base.Functor m => GHC.Base.Functor (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance Control.Monad.Primitive.PrimMonad m => Control.Monad.Primitive.PrimMonad (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance Data.Array.Base.MArray GHC.IOArray.IOArray e (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c GHC.Types.IO)
instance Data.Array.Base.MArray Data.Array.IO.Internals.IOUArray e GHC.Types.IO => Data.Array.Base.MArray Data.Array.IO.Internals.IOUArray e (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c GHC.Types.IO)
instance Data.Array.Base.MArray (GHC.Arr.STArray s) e (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c (GHC.ST.ST s))
instance Data.Array.Base.MArray (Data.Array.Base.STUArray s) e (GHC.ST.ST s) => Data.Array.Base.MArray (Data.Array.Base.STUArray s) e (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c (GHC.ST.ST s))


-- | Generic StateCache - wrapper around <a>StateT</a>
module Control.Monad.Trans.Memo.StateCache
data StateCache c m a
runStateCache :: StateCache s m a -> s -> m (a, s)

-- | Returns internal container
container :: Monad m => StateCache c m c

-- | Assigns new value to internal container
setContainer :: Monad m => c -> StateCache c m ()

-- | Evaluates computation discarding the resulting container
evalStateCache :: Monad m => StateCache c m a -> c -> m a
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Memo.StateCache.StateCache c)
instance Control.Monad.Fix.MonadFix m => Control.Monad.Fix.MonadFix (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance GHC.Base.MonadPlus m => GHC.Base.MonadPlus (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance GHC.Base.Monad m => GHC.Base.Monad (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance GHC.Base.MonadPlus m => GHC.Base.Alternative (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance GHC.Base.Functor m => GHC.Base.Functor (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance Control.Monad.Primitive.PrimMonad m => Control.Monad.Primitive.PrimMonad (Control.Monad.Trans.Memo.StateCache.StateCache c m)
instance Data.Array.Base.MArray GHC.IOArray.IOArray e (Control.Monad.Trans.Memo.StateCache.StateCache c GHC.Types.IO)
instance Data.Array.Base.MArray Data.Array.IO.Internals.IOUArray e GHC.Types.IO => Data.Array.Base.MArray Data.Array.IO.Internals.IOUArray e (Control.Monad.Trans.Memo.StateCache.StateCache c GHC.Types.IO)
instance Data.Array.Base.MArray (GHC.Arr.STArray s) e (Control.Monad.Trans.Memo.StateCache.StateCache c (GHC.ST.ST s))
instance Data.Array.Base.MArray (Data.Array.Base.STUArray s) e (GHC.ST.ST s) => Data.Array.Base.MArray (Data.Array.Base.STUArray s) e (Control.Monad.Trans.Memo.StateCache.StateCache c (GHC.ST.ST s))


-- | Defines MapLike typeclass - generalized interface to Data.Map,
--   Data.HashMap etc.
module Data.MapLike

-- | An abstract interface to the container which can store <tt>v</tt>
--   indexed by <tt>k</tt>
class MapLike c k v | c -> k, c -> v
lookup :: MapLike c k v => k -> c -> Maybe v
add :: MapLike c k v => k -> v -> c -> c


-- | Defines <a>MemoStateT</a> - generalized (to any <a>Data.MapLike</a>
--   content) memoization monad transformer
module Control.Monad.Trans.Memo.State

-- | Memoization monad transformer based on <a>StateCache</a> to be used
--   with pure cache containers which support <a>MapLike</a> interface
type MemoStateT s k v = StateCache (Container s)

-- | Returns the pair of the result of <a>MonadMemo</a> computation along
--   with the final state of the internal pure container wrapped in monad
runMemoStateT :: Monad m => MemoStateT s k v m a -> s -> m (a, s)

-- | Returns the result of <a>MonadMemo</a> computation wrapped in monad.
--   This function discards the cache
evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a

-- | Memoization monad based on <a>StateCache</a> to be used with pure
--   cache containers which support <a>MapLike</a> interface
type MemoState c k v = MemoStateT c k v Identity

-- | Returns the pair of the result of <a>MonadMemo</a> computation along
--   with the final state of the internal pure container
runMemoState :: MemoState c k v a -> c -> (a, c)

-- | Returns the result of <a>MonadMemo</a> computation discarding the
--   cache
evalMemoState :: MemoState c k v a -> c -> a
newtype Container s
Container :: s -> Container s
[toState] :: Container s -> s
instance (GHC.Base.Monad m, Data.MapLike.MapLike c k v) => Control.Monad.Memo.Class.MonadCache k v (Control.Monad.Trans.Memo.State.MemoStateT c k v m)
instance (GHC.Base.Monad m, Data.MapLike.MapLike c k v) => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Memo.State.MemoStateT c k v m)


-- | Defines MapLike instances declaration for standard data types
module Data.MapLike.Instances

-- | An abstract interface to the container which can store <tt>v</tt>
--   indexed by <tt>k</tt>
class MapLike c k v | c -> k, c -> v
lookup :: MapLike c k v => k -> c -> Maybe v
add :: MapLike c k v => k -> v -> c -> c
instance GHC.Classes.Ord k => Data.MapLike.MapLike (Data.Map.Internal.Map k v) k v
instance Data.MapLike.MapLike (Data.IntMap.Internal.IntMap v) GHC.Types.Int v


-- | Specialization of <a>MemoStateT</a> with <a>Map</a> as a container
module Control.Monad.Trans.Memo.Map

-- | Memoization monad transformer which uses <a>Map</a> as a cache
--   container
type MemoT k v = MemoStateT (Map k v) k v

-- | Given an initial cache, compute the result of a memoized computation
--   along with the final state of the cache
runMemoT :: Monad m => MemoT k v m a -> Map k v -> m (a, Map k v)

-- | Given an initial state, compute the result of a memoized computation
--   discarding the final state of the cache
evalMemoT :: Monad m => MemoT k v m a -> Map k v -> m a

-- | Compute the result of memoized computation along with the final state
--   of the cache. This function uses empty <a>Map</a> as an initial state
startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v)

-- | Compute the result of a memoized computation discarding the final
--   state of the cache. This function uses empty <a>Map</a> as an initial
--   state
startEvalMemoT :: Monad m => MemoT k v m a -> m a

-- | Memoization monad which uses <a>Map</a> as a cache container
type Memo k v = MemoT k v Identity

-- | Given an initial cache, compute the result of a memoized computation
--   along with the final state of the cache
runMemo :: Memo k v a -> Map k v -> (a, Map k v)

-- | Given an initial state, compute the result of a memoized computation
--   discarding the final state of the cache
evalMemo :: Memo k v a -> Map k v -> a

-- | Compute the result of memoized computation along with the final state
--   of the cache. This function uses empty <a>Map</a> as an initial state
startRunMemo :: Memo k v a -> (a, Map k v)

-- | Compute the result of a memoized computation discarding the final
--   state of the cache. This function uses empty <a>Map</a> as an initial
--   state
startEvalMemo :: Memo k v a -> a


-- | Defines MaybeLike typeclass - a generic way to look at some types as
--   if they were Maybe
--   
--   It is currently used to add maybe-ness to <tt>unboxed</tt> primitive
--   types in cases when it isn't possuble to just use `Maybe a` (e.g.
--   unboxed arrays)
module Data.MaybeLike

-- | An abstract interface to a type which may not have a value
class MaybeLike a v | a -> v
nothing :: MaybeLike a v => a
isNothing :: MaybeLike a v => a -> Bool
just :: MaybeLike a v => v -> a
fromJust :: MaybeLike a v => a -> v


-- | VectorCache - mutable-vector-based <a>MonadCache</a> with unsafe
--   operations.
--   
--   This is a version of <a>Control.Monad.Memo.Mutable.Vector</a> but
--   implemented using <i>unsafe*</i> vector operations. Faster than
--   default implementation but you must be sure that your code doesn't try
--   to read/write outside vector boundaries.
module Control.Monad.Memo.Vector.Unsafe

-- | <a>MonadCache</a> based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the <a>VectorCache</a>
--   element.
class MaybeLike e v => VectorMemo v e | v -> e

-- | Evaluate computation using mutable boxed vector and unsafe operations
--   
--   Vector length must covers all possible keys used in computation
--   otherwise the behaviour is undefined (i.e. segfault)
unsafeEvalVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m a

-- | Evaluate computation using mutable boxed vector and unsafe operations.
--   It also returns the final content of the vector cache
--   
--   Vector length must covers all possible keys used in computation
--   otherwise the behaviour is undefined (i.e. segfault)
unsafeRunVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m (a, Vector (PrimState m) e)

-- | <a>MonadCache</a> based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the <a>UVectorCache</a>
--   element
class MaybeLike e v => UVectorMemo v e | v -> e

-- | Evaluate computation using mutable unboxed vector and unsafe
--   operations
--   
--   Vector length must covers all possible keys used in computation
--   otherwise the behaviour is undefined (i.e. segfault)
unsafeEvalUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) => UVectorCache (PrimState m) e m a -> Int -> m a

-- | Evaluate computation using mutable boxed vector and unsafe operations.
--   It also returns the final content of the vector cache
--   
--   Vector length must covers all possible keys used in computation
--   otherwise the behaviour is undefined (i.e. segfault)
unsafeRunUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) => UVectorCache (PrimState m) e m a -> Int -> m (a, UVector (PrimState m) e)
newtype Container vec
Container :: vec -> Container vec
[toVector] :: Container vec -> vec

-- | Generic Vector-based memo cache
type Cache vec k e = ReaderCache (Container (vec k e))
genericUnsafeEvalVectorMemo :: (MaybeLike e v, PrimMonad m, MVector c e) => Cache c (PrimState m) e m a -> Int -> m a
genericUnsafeRunVectorMemo :: (MaybeLike e v, PrimMonad m, MVector c e) => Cache c (PrimState m) e m a -> Int -> m (a, c (PrimState m) e)
instance (Control.Monad.Primitive.PrimMonad m, Control.Monad.Primitive.PrimState m GHC.Types.~ s, Data.MaybeLike.MaybeLike e v, Data.Vector.Generic.Mutable.Base.MVector c e) => Control.Monad.Memo.Class.MonadCache GHC.Types.Int v (Control.Monad.Memo.Vector.Unsafe.Cache c s e m)
instance (Control.Monad.Primitive.PrimMonad m, Control.Monad.Primitive.PrimState m GHC.Types.~ s, Data.MaybeLike.MaybeLike e v, Data.Vector.Generic.Mutable.Base.MVector c e) => Control.Monad.Memo.Class.MonadMemo GHC.Types.Int v (Control.Monad.Memo.Vector.Unsafe.Cache c s e m)


-- | Vector-based <a>MonadCache</a> implementation which dynamically
--   expands the vector during the computation to accomodate all requested
--   keys. This implementation does not require to specify the length of
--   the vector up front, but may be slower than
--   <a>Control.Monad.Memo.Vector</a>.
module Control.Monad.Memo.Vector.Expandable

-- | <a>MonadCache</a> based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the <a>VectorCache</a>
--   element.
class MaybeLike e v => VectorMemo v e | v -> e

-- | Evaluate computation using mutable boxed vector which dynamically
--   grows to accomodate all requested keys
startEvalVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> m a

-- | Evaluate computation using mutable boxed vector which dynamically
--   grows to accomodate all requested keys. This function also returns the
--   final content of the vector cache
startRunVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> m (a, Vector (PrimState m) e)

-- | <a>MonadCache</a> based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the <a>UVectorCache</a>
--   element.
class MaybeLike e v => UVectorMemo v e | v -> e

-- | Evaluate computation using mutable unboxed vector which dynamically
--   grows to accomodate all requested keys
startEvalUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) => UVectorCache (PrimState m) e m a -> m a

-- | Evaluate computation using mutable unboxed vector which dynamically
--   grows to accomodate all requested keys. This function also returns the
--   final content of the vector cache
startRunUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) => UVectorCache (PrimState m) e m a -> m (a, UVector (PrimState m) e)
newtype Container vec
Container :: vec -> Container vec
[toVector] :: Container vec -> vec

-- | Generic Vector-based memo cache
type Cache vec k e = StateCache (Container (vec k e))
genericStartEvalVectorMemo :: (MaybeLike e v, PrimMonad m, MVector vec e) => Cache vec (PrimState m) e m a -> m a
genericStartRunVectorMemo :: (MaybeLike e v, PrimMonad m, MVector vec e) => Cache vec (PrimState m) e m a -> m (a, vec (PrimState m) e)
instance (Control.Monad.Primitive.PrimMonad m, Control.Monad.Primitive.PrimState m GHC.Types.~ s, Data.MaybeLike.MaybeLike e v, Data.Vector.Generic.Mutable.Base.MVector c e) => Control.Monad.Memo.Class.MonadCache GHC.Types.Int v (Control.Monad.Memo.Vector.Expandable.Cache c s e m)
instance (Control.Monad.Primitive.PrimMonad m, Control.Monad.Primitive.PrimState m GHC.Types.~ s, Data.MaybeLike.MaybeLike e v, Data.Vector.Generic.Mutable.Base.MVector c e) => Control.Monad.Memo.Class.MonadMemo GHC.Types.Int v (Control.Monad.Memo.Vector.Expandable.Cache c s e m)


-- | VectorCache - mutable-vector-based (<tt>IO</tt> and <tt>ST</tt>
--   hosted) <a>MonadCache</a>
--   
--   The fastest memoization cache, however it is even more limiting than
--   <a>Control.Monad.Memo.Array</a> due to nature of
--   <a>Data.Vector.Mutable</a>. Still if you can use this cache please do
--   since it will give you dramatic calculation speed up in comparison to
--   pure <a>Map</a>-based cache, especially when unboxed
--   <a>UVectorCache</a> is used.
--   
--   Limitations: Since <a>MVector</a> is used as <a>MonadCache</a> the key
--   must be <a>Int</a> and the size of the cache's vector must be known
--   beforehand with vector being allocated before the first call. In
--   addition unboxed <a>UVectorCache</a> can only store <a>Unbox</a>
--   values (but it does it very efficiently).
module Control.Monad.Memo.Vector

-- | Boxed vector
type Vector = MVector

-- | <a>MonadCache</a> based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the <a>VectorCache</a>
--   element.
class MaybeLike e v => VectorMemo v e | v -> e

-- | Evaluate computation using mutable boxed vector
--   
--   Vector length must covers all possible keys used in computation
--   otherwise <i>index out of bound</i> error is generated by vector code
evalVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m a

-- | 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 <i>index out of bound</i> error is generated by vector code
runVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m (a, Vector (PrimState m) e)

-- | Unboxed vector
type UVector = MVector

-- | <a>MonadCache</a> based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the <a>UVectorCache</a>
--   element.
class MaybeLike e v => UVectorMemo v e | v -> e

-- | Evaluate computation using mutable unboxed vector
--   
--   Vector length must covers all possible keys used in computation
--   otherwise <i>index out of bound</i> error is generated by vector code
evalUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m a

-- | 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 <i>index out of bound</i> error is generated by vector code
runUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m (a, UVector (PrimState m) e)
newtype Container vec
Container :: vec -> Container vec
[toVector] :: Container vec -> vec

-- | Generic Vector-based memo cache
type Cache vec s e = ReaderCache (Container (vec s e))
genericEvalVectorMemo :: (MaybeLike e v, PrimMonad m, MVector c e) => Cache c (PrimState m) e m a -> Int -> m a
genericRunVectorMemo :: (MaybeLike e v, PrimMonad m, MVector c e) => Cache c (PrimState m) e m a -> Int -> m (a, c (PrimState m) e)
instance (Control.Monad.Primitive.PrimMonad m, Control.Monad.Primitive.PrimState m GHC.Types.~ s, Data.MaybeLike.MaybeLike e v, Data.Vector.Generic.Mutable.Base.MVector c e) => Control.Monad.Memo.Class.MonadCache GHC.Types.Int v (Control.Monad.Memo.Vector.Cache c s e m)
instance (Control.Monad.Primitive.PrimMonad m, Control.Monad.Primitive.PrimState m GHC.Types.~ s, Data.MaybeLike.MaybeLike e v, Data.Vector.Generic.Mutable.Base.MVector c e) => Control.Monad.Memo.Class.MonadMemo GHC.Types.Int v (Control.Monad.Memo.Vector.Cache c s e m)


-- | Default instances for <tt>VectorMemo</tt> and <tt>UVectorMemo</tt>
module Control.Monad.Memo.Vector.Instances
instance Data.MaybeLike.MaybeLike (GHC.Maybe.Maybe v) v => Control.Monad.Memo.Vector.VectorMemo v (GHC.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Vector.UVectorMemo v v
instance Data.MaybeLike.MaybeLike (GHC.Maybe.Maybe v) v => Control.Monad.Memo.Vector.Expandable.VectorMemo v (GHC.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Vector.Expandable.UVectorMemo v v
instance Data.MaybeLike.MaybeLike (GHC.Maybe.Maybe v) v => Control.Monad.Memo.Vector.Unsafe.VectorMemo v (GHC.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Vector.Unsafe.UVectorMemo v v


-- | ArrayCache - mutable-array-based (<a>IO</a> and <a>ST</a> hosted)
--   <a>MonadCache</a>
--   
--   Very fast memoization cache. Unfortunatelly it cannot suit every case
--   (see limitations), but if you can use it, please do: it is generally
--   an order of magnitude faster than <a>Map</a>-based <a>Memo</a>,
--   especially <i>unboxed</i> version - try to use it whenever you can.
--   
--   Limitations: Since <a>MArray</a> is used as <a>MonadCache</a> the key
--   range must be known beforehand and the array is allocated before the
--   first call. It is therefore most suitable for the cases when the
--   distribution of possible key values is within reasonable range and is
--   rather dense (the best case: all values withing some range will be
--   used). If this is the case then <a>MArray</a> has O(1) for both lookup
--   and update operations. In addition unboxed <a>UArrayCache</a> can only
--   store unboxed types (but it does it very efficiently).
module Control.Monad.Memo.Array

-- | A family of boxed arrays
type family Array (m :: * -> *) :: * -> * -> *

-- | Memoization monad based on mutable boxed array
type ArrayCache k e m = Cache (Array m) k e m

-- | This is just to be able to infer the type of the <a>ArrayCache</a>
--   element
--   
--   Type families could be used instead but due to the bug in 7.4.* we
--   cannot use them here
class MaybeLike e v => ArrayMemo v e | v -> e

-- | Evaluate computation using boxed array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
evalArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m a

-- | Evaluate computation and the final content of array cache using boxed
--   array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
runArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m (a, Array m k e)

-- | A family of unboxed arrays
type family UArray (m :: * -> *) :: * -> * -> *

-- | Memoization monad based on mutable unboxed array
type UArrayCache k e m = Cache (UArray m) k e m

-- | This is just to be able to infer the type of the <a>UArrayCache</a>
--   element
--   
--   Type families could be used instead but due to the bug in 7.4.* we
--   cannot use them here
class MaybeLike e v => UArrayMemo v e | v -> e

-- | Evaluate computation using unboxed array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
evalUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m a

-- | Evaluate computation and the final content of array cache using
--   unboxed array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
runUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m (a, UArray m k e)
newtype Container arr
Container :: arr -> Container arr
[toArray] :: Container arr -> arr

-- | Generic Array-based memo cache
type Cache arr k e = ReaderCache (Container (arr k e))
genericEvalArrayMemo :: (Ix k, MaybeLike e v, MArray arr e m) => Cache arr k e m a -> (k, k) -> m a
genericRunArrayMemo :: (Ix k, MaybeLike e v, MArray arr e m) => Cache arr k e m a -> (k, k) -> m (a, arr k e)
instance (GHC.Base.Monad m, GHC.Arr.Ix k, Data.MaybeLike.MaybeLike e v, Data.Array.Base.MArray c e m) => Control.Monad.Memo.Class.MonadCache k v (Control.Monad.Memo.Array.Cache c k e m)
instance (GHC.Base.Monad m, GHC.Arr.Ix k, Data.MaybeLike.MaybeLike e v, Data.Array.Base.MArray c e m) => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Memo.Array.Cache c k e m)


-- | Default instances of <a>ArrayMemo</a> and <a>UArrayMemo</a>
module Control.Monad.Memo.Array.Instances
instance Data.MaybeLike.MaybeLike (GHC.Maybe.Maybe v) v => Control.Monad.Memo.Array.ArrayMemo v (GHC.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Array.UArrayMemo v v


-- | Defines default instances of <a>MaybeLike</a> for most primitive
--   <a>Unboxed</a> types
module Data.MaybeLike.Instances
instance Data.MaybeLike.MaybeLike (GHC.Maybe.Maybe a) a
instance Data.MaybeLike.MaybeLike GHC.Types.Char GHC.Types.Char
instance Data.MaybeLike.MaybeLike GHC.Types.Int GHC.Types.Int
instance Data.MaybeLike.MaybeLike GHC.Int.Int8 GHC.Int.Int8
instance Data.MaybeLike.MaybeLike GHC.Int.Int16 GHC.Int.Int16
instance Data.MaybeLike.MaybeLike GHC.Int.Int32 GHC.Int.Int32
instance Data.MaybeLike.MaybeLike GHC.Int.Int64 GHC.Int.Int64
instance Data.MaybeLike.MaybeLike GHC.Types.Word GHC.Types.Word
instance Data.MaybeLike.MaybeLike GHC.Word.Word8 GHC.Word.Word8
instance Data.MaybeLike.MaybeLike GHC.Word.Word16 GHC.Word.Word16
instance Data.MaybeLike.MaybeLike GHC.Word.Word32 GHC.Word.Word32
instance Data.MaybeLike.MaybeLike GHC.Word.Word64 GHC.Word.Word64
instance Data.MaybeLike.MaybeLike GHC.Types.Float GHC.Types.Float
instance Data.MaybeLike.MaybeLike GHC.Types.Double GHC.Types.Double


-- | Importing just this module is sufficient for most cases of the package
--   usage
module Control.Monad.Memo

-- | Memoization interface
class Monad m => MonadMemo k v m | m -> k, m -> v
memo :: MonadMemo k v m => (k -> m v) -> k -> m v

-- | Memoization monad based on <a>StateCache</a> to be used with pure
--   cache containers which support <a>MapLike</a> interface
type MemoState c k v = MemoStateT c k v Identity

-- | Returns the pair of the result of <a>MonadMemo</a> computation along
--   with the final state of the internal pure container
runMemoState :: MemoState c k v a -> c -> (a, c)

-- | Returns the result of <a>MonadMemo</a> computation discarding the
--   cache
evalMemoState :: MemoState c k v a -> c -> a

-- | Memoization monad transformer based on <a>StateCache</a> to be used
--   with pure cache containers which support <a>MapLike</a> interface
type MemoStateT s k v = StateCache (Container s)

-- | Returns the pair of the result of <a>MonadMemo</a> computation along
--   with the final state of the internal pure container wrapped in monad
runMemoStateT :: Monad m => MemoStateT s k v m a -> s -> m (a, s)

-- | Returns the result of <a>MonadMemo</a> computation wrapped in monad.
--   This function discards the cache
evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a

-- | Memoization monad which uses <a>Map</a> as a cache container
type Memo k v = MemoT k v Identity

-- | Given an initial cache, compute the result of a memoized computation
--   along with the final state of the cache
runMemo :: Memo k v a -> Map k v -> (a, Map k v)

-- | Given an initial state, compute the result of a memoized computation
--   discarding the final state of the cache
evalMemo :: Memo k v a -> Map k v -> a

-- | Compute the result of memoized computation along with the final state
--   of the cache. This function uses empty <a>Map</a> as an initial state
startRunMemo :: Memo k v a -> (a, Map k v)

-- | Compute the result of a memoized computation discarding the final
--   state of the cache. This function uses empty <a>Map</a> as an initial
--   state
startEvalMemo :: Memo k v a -> a

-- | Memoization monad transformer which uses <a>Map</a> as a cache
--   container
type MemoT k v = MemoStateT (Map k v) k v

-- | Given an initial cache, compute the result of a memoized computation
--   along with the final state of the cache
runMemoT :: Monad m => MemoT k v m a -> Map k v -> m (a, Map k v)

-- | Given an initial state, compute the result of a memoized computation
--   discarding the final state of the cache
evalMemoT :: Monad m => MemoT k v m a -> Map k v -> m a

-- | Compute the result of memoized computation along with the final state
--   of the cache. This function uses empty <a>Map</a> as an initial state
startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v)

-- | Compute the result of a memoized computation discarding the final
--   state of the cache. This function uses empty <a>Map</a> as an initial
--   state
startEvalMemoT :: Monad m => MemoT k v m a -> m a

-- | Memoization monad based on mutable boxed array
type ArrayCache k e m = Cache (Array m) k e m

-- | This is just to be able to infer the type of the <a>ArrayCache</a>
--   element
--   
--   Type families could be used instead but due to the bug in 7.4.* we
--   cannot use them here
class MaybeLike e v => ArrayMemo v e | v -> e

-- | Evaluate computation using boxed array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
evalArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m a

-- | Evaluate computation and the final content of array cache using boxed
--   array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
runArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m (a, Array m k e)

-- | Memoization monad based on mutable unboxed array
type UArrayCache k e m = Cache (UArray m) k e m

-- | This is just to be able to infer the type of the <a>UArrayCache</a>
--   element
--   
--   Type families could be used instead but due to the bug in 7.4.* we
--   cannot use them here
class MaybeLike e v => UArrayMemo v e | v -> e

-- | Evaluate computation using unboxed array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
evalUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m a

-- | Evaluate computation and the final content of array cache using
--   unboxed array
--   
--   Key range should cover all possible keys used in computation otherwise
--   <i>not in range</i> error is generated by array
runUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m (a, UArray m k e)

-- | <a>MonadCache</a> based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the <a>VectorCache</a>
--   element.
class MaybeLike e v => VectorMemo v e | v -> e

-- | Evaluate computation using mutable boxed vector
--   
--   Vector length must covers all possible keys used in computation
--   otherwise <i>index out of bound</i> error is generated by vector code
evalVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m a

-- | 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 <i>index out of bound</i> error is generated by vector code
runVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m (a, Vector (PrimState m) e)

-- | <a>MonadCache</a> based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the <a>UVectorCache</a>
--   element.
class MaybeLike e v => UVectorMemo v e | v -> e

-- | Evaluate computation using mutable unboxed vector
--   
--   Vector length must covers all possible keys used in computation
--   otherwise <i>index out of bound</i> error is generated by vector code
evalUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m a

-- | 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 <i>index out of bound</i> error is generated by vector code
runUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m (a, UVector (PrimState m) e)

-- | Adapter for memoization of two-argument function
for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv

-- | Adapter for memoization of three-argument function
for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mv

-- | Adapter for memoization of four-argument function
for4 :: (((k1, k2, k3, k4) -> mv) -> (k1, k2, k3, k4) -> mv) -> (k1 -> k2 -> k3 -> k4 -> mv) -> k1 -> k2 -> k3 -> k4 -> mv

-- | Memoization for the current transformer in stack using a cache from an
--   arbitrary transformer down the stack
memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) => (forall a. m1 a -> m2 a) -> (k1 -> k2) -> (k1 -> m2 v) -> k1 -> m2 v

-- | Uses current monad's memoization cache
memol0 :: (MonadCache k v m, Monad m) => (k -> m v) -> k -> m v

-- | Uses the 1st transformer in stack for memoization cache
memol1 :: (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v

-- | Uses the 2nd 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 3rd 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 4th 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
