-- 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 Control.Monad.Memo.memo combinator at the point when
--   memoization is required (i.e. recursive call)
--   
--   
--   import Control.Monad.Memo
--   
--   fibm 0 = return 0
--   fibm 1 = return 1
--   fibm n = do
--     n1 <- memo fibm (n-1)
--     n2 <- memo fibm (n-2)
--     return (n1+n2)
--   
--   
--   2) Use appropriate *eval* or *run* function to evaluate
--   resulting MonadMemo monad:
--   
--   
--   startEvalMemo (fibm 100)
--   
--   
--   See detailed description and examples: Control.Monad.Memo
@package monad-memo
@version 0.5.4

-- | 
--   
- Computation type: Interface for monadic computations which
--   can be memoized.
--   
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 :: Type -> Type) | 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 :: Type -> Type) | 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 :: forall t1 k v (m :: Type -> Type). (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 :: 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

-- | Uses the 3rd 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

-- | Uses the 4th 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
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.Internal.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 k v m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Identity.IdentityT m)
instance Control.Monad.Memo.Class.MonadCache k (GHC.Internal.Maybe.Maybe v) m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Maybe.MaybeT m)
instance (GHC.Internal.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)
instance (GHC.Internal.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 Control.Monad.Memo.Class.MonadCache (r, k) v m => Control.Monad.Memo.Class.MonadMemo k v (Control.Monad.Trans.Reader.ReaderT r 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 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 (GHC.Internal.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 (GHC.Internal.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)

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

-- | Returns internal container
container :: forall (m :: Type -> Type) c. Monad m => ReaderCache c m c
instance GHC.Internal.Base.Alternative m => GHC.Internal.Base.Alternative (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Internal.Base.Applicative m => GHC.Internal.Base.Applicative (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Internal.Base.Functor m => GHC.Internal.Base.Functor (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance Data.Array.Base.MArray GHC.Internal.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.Internal.Arr.STArray s) e (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c (GHC.Internal.ST.ST s))
instance Data.Array.Base.MArray (Data.Array.Base.STUArray s) e (GHC.Internal.ST.ST s) => Data.Array.Base.MArray (Data.Array.Base.STUArray s) e (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c (GHC.Internal.ST.ST s))
instance GHC.Internal.Control.Monad.Fix.MonadFix m => GHC.Internal.Control.Monad.Fix.MonadFix (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Internal.Base.MonadPlus m => GHC.Internal.Base.MonadPlus (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Monad (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c)
instance Control.Monad.Primitive.PrimMonad m => Control.Monad.Primitive.PrimMonad (Control.Monad.Trans.Memo.ReaderCache.ReaderCache c m)

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

-- | Returns internal container
container :: forall (m :: Type -> Type) c. Monad m => StateCache c m c

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

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

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

-- | An abstract interface to the container which can store v
--   indexed by k
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 MemoStateT - generalized (to any Data.MapLike
--   content) memoization monad transformer
module Control.Monad.Trans.Memo.State

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

-- | Returns the pair of the result of MonadMemo 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 MonadMemo 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 StateCache to be used with pure
--   cache containers which support MapLike interface
type MemoState c k v = MemoStateT c k v Identity

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

-- | Returns the result of MonadMemo 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.Internal.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.Internal.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 v
--   indexed by k
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 Data.MapLike.MapLike (Data.IntMap.Internal.IntMap v) GHC.Types.Int v
instance GHC.Classes.Ord k => Data.MapLike.MapLike (Data.Map.Internal.Map k v) k v

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

-- | Memoization monad transformer which uses Map 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 Map 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 Map as an initial
--   state
startEvalMemoT :: Monad m => MemoT k v m a -> m a

-- | Memoization monad which uses Map 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 Map 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 Map 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 unboxed 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 MonadCache with unsafe
--   operations.
--   
--   This is a version of Control.Monad.Memo.Mutable.Vector but
--   implemented using unsafe* 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

-- | MonadCache based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the VectorCache
--   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)

-- | MonadCache based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the UVectorCache
--   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 :: Type -> Type -> Type) 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 MonadCache 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
--   Control.Monad.Memo.Vector.
module Control.Monad.Memo.Vector.Expandable

-- | MonadCache based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the VectorCache
--   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)

-- | MonadCache based on unboxed vector
type UVectorCache s e = Cache UVector s e

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

-- | Boxed vector
type Vector = MVector

-- | MonadCache based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the VectorCache
--   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 index out of bound 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 index out of bound 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

-- | MonadCache based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the UVectorCache
--   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 index out of bound 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 index out of bound 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 :: Type -> Type -> Type) 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 VectorMemo and UVectorMemo
module Control.Monad.Memo.Vector.Instances
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Vector.Unsafe.UVectorMemo v v
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Vector.Expandable.UVectorMemo v v
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Vector.UVectorMemo v v
instance Data.MaybeLike.MaybeLike (GHC.Internal.Maybe.Maybe v) v => Control.Monad.Memo.Vector.Unsafe.VectorMemo v (GHC.Internal.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike (GHC.Internal.Maybe.Maybe v) v => Control.Monad.Memo.Vector.Expandable.VectorMemo v (GHC.Internal.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike (GHC.Internal.Maybe.Maybe v) v => Control.Monad.Memo.Vector.VectorMemo v (GHC.Internal.Maybe.Maybe v)

-- | ArrayCache - mutable-array-based (IO and ST hosted)
--   MonadCache
--   
--   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 Map-based Memo,
--   especially unboxed version - try to use it whenever you can.
--   
--   Limitations: Since MArray is used as MonadCache 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 MArray has O(1) for both lookup
--   and update operations. In addition unboxed UArrayCache 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 :: Type -> Type) :: Type -> Type -> Type

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

-- | 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
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
--   not in range 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
--   not in range 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 :: Type -> Type) :: Type -> Type -> Type

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

-- | 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
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
--   not in range 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
--   not in range 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 :: Type -> Type -> Type) 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.Internal.Base.Monad m, GHC.Internal.Ix.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.Internal.Base.Monad m, GHC.Internal.Ix.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 ArrayMemo and UArrayMemo
module Control.Monad.Memo.Array.Instances
instance Data.MaybeLike.MaybeLike (GHC.Internal.Maybe.Maybe v) v => Control.Monad.Memo.Array.ArrayMemo v (GHC.Internal.Maybe.Maybe v)
instance Data.MaybeLike.MaybeLike v v => Control.Monad.Memo.Array.UArrayMemo v v

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

-- | 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 :: Type -> Type) | m -> k, m -> v
memo :: MonadMemo k v m => (k -> m v) -> k -> m v

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

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

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

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

-- | Returns the pair of the result of MonadMemo 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 MonadMemo 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 Map 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 Map 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 Map as an initial
--   state
startEvalMemo :: Memo k v a -> a

-- | Memoization monad transformer which uses Map 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 Map 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 Map 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 :: Type -> Type) = Cache Array m k e m

-- | 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
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
--   not in range 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
--   not in range 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 :: Type -> Type) = Cache UArray m k e m

-- | 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
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
--   not in range 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
--   not in range 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)

-- | MonadCache based on boxed vector
type VectorCache s e = Cache Vector s e

-- | This is just to be able to infer the type of the VectorCache
--   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 index out of bound 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 index out of bound 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)

-- | MonadCache based on unboxed vector
type UVectorCache s e = Cache UVector s e

-- | This is just to be able to infer the type of the UVectorCache
--   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 index out of bound 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 index out of bound 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 :: forall t1 k v (m :: Type -> Type). (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 :: 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

-- | Uses the 3rd 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

-- | Uses the 4th 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
