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


-- | Monads for free
--   
--   Free monads are useful for many tree-like structures and domain
--   specific languages.
--   
--   If <tt>f</tt> is a <a>Functor</a> then the free <a>Monad</a> on
--   <tt>f</tt> is the type of trees whose nodes are labeled with the
--   constructors of <tt>f</tt>. The word "free" is used in the sense of
--   "unrestricted" rather than "zero-cost": <tt>Free f</tt> makes no
--   constraining assumptions beyond those given by <tt>f</tt> and the
--   definition of <a>Monad</a>. As used here it is a standard term from
--   the mathematical theory of adjoint functors.
--   
--   Cofree comonads are dual to free monads. They provide convenient ways
--   to talk about branching streams and rose-trees, and can be used to
--   annotate syntax trees. The cofree comonad can be seen as a stream
--   parameterized by a <a>Functor</a> that controls its branching factor.
--   
--   More information on free monads, including examples, can be found in
--   the following blog posts:
--   <a>http://comonad.com/reader/2008/monads-for-free/</a>
--   <a>http://comonad.com/reader/2011/free-monads-for-less/</a>
@package free
@version 4.9


-- | Automatic generation of free monadic actions.
module Control.Monad.Free.TH

-- | <tt>$(makeFree ''Type)</tt> provides free monadic actions for the
--   constructors of the given type.
makeFree :: Name -> Q [Dec]
instance Show Arg


-- | Monads for free.
module Control.Monad.Free.Class

-- | Monads provide substitution (<a>fmap</a>) and renormalization
--   (<a>join</a>):
--   
--   <pre>
--   m <a>&gt;&gt;=</a> f = <a>join</a> (<a>fmap</a> f m)
--   </pre>
--   
--   A free <a>Monad</a> is one that does no work during the normalization
--   step beyond simply grafting the two monadic values together.
--   
--   <tt>[]</tt> is not a free <a>Monad</a> (in this sense) because
--   <tt><a>join</a> [[a]]</tt> smashes the lists flat.
--   
--   On the other hand, consider:
--   
--   <pre>
--   data Tree a = Bin (Tree a) (Tree a) | Tip a
--   </pre>
--   
--   <pre>
--   instance <a>Monad</a> Tree where
--     <a>return</a> = Tip
--     Tip a <a>&gt;&gt;=</a> f = f a
--     Bin l r <a>&gt;&gt;=</a> f = Bin (l <a>&gt;&gt;=</a> f) (r <a>&gt;&gt;=</a> f)
--   </pre>
--   
--   This <a>Monad</a> is the free <a>Monad</a> of Pair:
--   
--   <pre>
--   data Pair a = Pair a a
--   </pre>
--   
--   And we could make an instance of <a>MonadFree</a> for it directly:
--   
--   <pre>
--   instance <a>MonadFree</a> Pair Tree where
--      <a>wrap</a> (Pair l r) = Bin l r
--   </pre>
--   
--   Or we could choose to program with <tt><a>Free</a> Pair</tt> instead
--   of <tt>Tree</tt> and thereby avoid having to define our own
--   <a>Monad</a> instance.
--   
--   Moreover, <a>Control.Monad.Free.Church</a> provides a <a>MonadFree</a>
--   instance that can improve the <i>asymptotic</i> complexity of code
--   that constructs free monads by effectively reassociating the use of
--   (<a>&gt;&gt;=</a>). You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   See <a>Free</a> for a more formal definition of the free <a>Monad</a>
--   for a <a>Functor</a>.
class Monad m => MonadFree f m | m -> f where wrap = join . lift . wrap . fmap return
wrap :: MonadFree f m => f (m a) -> m a

-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a

-- | A version of wrap for monad transformers over a free monad.
--   
--   <i>Note:</i> that this is the default implementation for <a>wrap</a>
--   for <tt>MonadFree f (t m)</tt>.
wrapT :: (Functor f, MonadFree f m, MonadTrans t, Monad (t m)) => f (t m a) -> t m a
instance (Functor f, MonadFree f m, Error e) => MonadFree f (ErrorT e m)
instance (Functor f, MonadFree f m) => MonadFree f (ListT m)
instance (Functor f, MonadFree f m) => MonadFree f (IdentityT m)
instance (Functor f, MonadFree f m) => MonadFree f (MaybeT m)
instance (Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m)
instance (Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m)
instance (Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m)
instance (Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m)
instance (Functor f, MonadFree f m) => MonadFree f (ContT r m)
instance (Functor f, MonadFree f m) => MonadFree f (StateT s m)
instance (Functor f, MonadFree f m) => MonadFree f (StateT s m)
instance (Functor f, MonadFree f m) => MonadFree f (ReaderT e m)


-- | Based on <a>Capretta's Iterative Monad Transformer</a>
--   
--   Unlike <tt>Free</tt>, this is a true monad transformer.
module Control.Monad.Trans.Iter

-- | The monad supporting iteration based over a base monad <tt>m</tt>.
--   
--   <pre>
--   <a>IterT</a> ~ <tt>FreeT</tt> <a>Identity</a>
--   </pre>
newtype IterT m a
IterT :: m (Either a (IterT m a)) -> IterT m a
runIterT :: IterT m a -> m (Either a (IterT m a))

-- | Plain iterative computations.
type Iter = IterT Identity

-- | Builds an iterative computation from one first step.
--   
--   <pre>
--   runIter . iter == id
--   </pre>
iter :: Either a (Iter a) -> Iter a

-- | Executes the first step of an iterative computation
--   
--   <pre>
--   iter . runIter == id
--   </pre>
runIter :: Iter a -> Either a (Iter a)

-- | Adds an extra layer to a free monad value.
--   
--   In particular, for the iterative monad <a>Iter</a>, this makes the
--   computation require one more step, without changing its final result.
--   
--   <pre>
--   runIter (delay ma) == Right ma
--   </pre>
delay :: (Monad f, MonadFree f m) => m a -> m a

-- | Lift a monad homomorphism from <tt>m</tt> to <tt>n</tt> into a Monad
--   homomorphism from <tt><a>IterT</a> m</tt> to <tt><a>IterT</a> n</tt>.
hoistIterT :: Monad n => (forall a. m a -> n a) -> IterT m b -> IterT n b

-- | Lifts a plain, non-terminating computation into a richer environment.
--   <a>liftIter</a> is a <a>Monad</a> homomorphism.
liftIter :: Monad m => Iter a -> IterT m a

-- | Cuts off an iterative computation after a given number of steps. If
--   the number of steps is 0 or less, no computation nor monadic effects
--   will take place.
--   
--   The step where the final value is produced also counts towards the
--   limit.
--   
--   Some examples (<tt>n ≥ 0</tt>):
--   
--   <pre>
--   <a>cutoff</a> 0     _        ≡ <a>return</a> <a>Nothing</a>
--   <a>cutoff</a> (n+1) <a>.</a> <a>return</a> ≡ <a>return</a> <a>.</a> <a>Just</a>
--   <a>cutoff</a> (n+1) <a>.</a> <a>lift</a>   ≡ <a>lift</a> <a>.</a> <a>liftM</a> <a>Just</a>
--   <a>cutoff</a> (n+1) <a>.</a> <a>delay</a>  ≡ <a>delay</a> . <a>cutoff</a> n
--   <a>cutoff</a> n     <a>never</a>    ≡ <a>iterate</a> <a>delay</a> (<a>return</a> <a>Nothing</a>) <a>!!</a> n
--   </pre>
--   
--   Calling <tt><a>retract</a> <a>.</a> <a>cutoff</a> n</tt> is always
--   terminating, provided each of the steps in the iteration is
--   terminating.
cutoff :: Monad m => Integer -> IterT m a -> IterT m (Maybe a)

-- | A computation that never terminates
never :: (Monad f, MonadFree f m) => m a

-- | Interleaves the steps of a finite list of iterative computations, and
--   collects their results.
--   
--   The resulting computation has as many steps as the longest computation
--   in the list.
interleave :: Monad m => [IterT m a] -> IterT m [a]

-- | Interleaves the steps of a finite list of computations, and discards
--   their results.
--   
--   The resulting computation has as many steps as the longest computation
--   in the list.
--   
--   Equivalent to <tt><tt>void</tt> <a>.</a> <a>interleave</a></tt>.
interleave_ :: Monad m => [IterT m a] -> IterT m ()

-- | <a>retract</a> is the left inverse of <a>lift</a>
--   
--   <pre>
--   <a>retract</a> . <a>lift</a> = <a>id</a>
--   </pre>
retract :: Monad m => IterT m a -> m a

-- | Tear down a <tt>Free</tt> <a>Monad</a> using iteration.
fold :: Monad m => (m a -> a) -> IterT m a -> a

-- | Like <a>fold</a> with monadic result.
foldM :: (Monad m, Monad n) => (m (n a) -> n a) -> IterT m a -> n a

-- | Monads provide substitution (<a>fmap</a>) and renormalization
--   (<a>join</a>):
--   
--   <pre>
--   m <a>&gt;&gt;=</a> f = <a>join</a> (<a>fmap</a> f m)
--   </pre>
--   
--   A free <a>Monad</a> is one that does no work during the normalization
--   step beyond simply grafting the two monadic values together.
--   
--   <tt>[]</tt> is not a free <a>Monad</a> (in this sense) because
--   <tt><a>join</a> [[a]]</tt> smashes the lists flat.
--   
--   On the other hand, consider:
--   
--   <pre>
--   data Tree a = Bin (Tree a) (Tree a) | Tip a
--   </pre>
--   
--   <pre>
--   instance <a>Monad</a> Tree where
--     <a>return</a> = Tip
--     Tip a <a>&gt;&gt;=</a> f = f a
--     Bin l r <a>&gt;&gt;=</a> f = Bin (l <a>&gt;&gt;=</a> f) (r <a>&gt;&gt;=</a> f)
--   </pre>
--   
--   This <a>Monad</a> is the free <a>Monad</a> of Pair:
--   
--   <pre>
--   data Pair a = Pair a a
--   </pre>
--   
--   And we could make an instance of <a>MonadFree</a> for it directly:
--   
--   <pre>
--   instance <a>MonadFree</a> Pair Tree where
--      <a>wrap</a> (Pair l r) = Bin l r
--   </pre>
--   
--   Or we could choose to program with <tt><a>Free</a> Pair</tt> instead
--   of <tt>Tree</tt> and thereby avoid having to define our own
--   <a>Monad</a> instance.
--   
--   Moreover, <a>Control.Monad.Free.Church</a> provides a <a>MonadFree</a>
--   instance that can improve the <i>asymptotic</i> complexity of code
--   that constructs free monads by effectively reassociating the use of
--   (<a>&gt;&gt;=</a>). You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   See <a>Free</a> for a more formal definition of the free <a>Monad</a>
--   for a <a>Functor</a>.
class Monad m => MonadFree f m | m -> f where wrap = join . lift . wrap . fmap return
wrap :: MonadFree f m => f (m a) -> m a
instance (Typeable1 m, Typeable a, Data (m (Either a (IterT m a))), Data a) => Data (IterT m a)
instance Typeable1 m => Typeable1 (IterT m)
instance (Monad m, Monoid a) => Monoid (IterT m a)
instance Monad m => MonadFree Identity (IterT m)
instance MonadCont m => MonadCont (IterT m)
instance MonadIO m => MonadIO (IterT m)
instance MonadError e m => MonadError e (IterT m)
instance MonadState s m => MonadState s (IterT m)
instance MonadWriter w m => MonadWriter w (IterT m)
instance MonadReader e m => MonadReader e (IterT m)
instance (Monad m, Traversable1 m) => Traversable1 (IterT m)
instance (Monad m, Traversable m) => Traversable (IterT m)
instance Foldable1 m => Foldable1 (IterT m)
instance Foldable m => Foldable (IterT m)
instance MonadTrans IterT
instance MonadPlus m => MonadPlus (IterT m)
instance MonadPlus m => Alternative (IterT m)
instance MonadFix m => MonadFix (IterT m)
instance Monad m => Bind (IterT m)
instance Monad m => Apply (IterT m)
instance Monad m => Monad (IterT m)
instance Monad m => Applicative (IterT m)
instance Monad m => Functor (IterT m)
instance Read (m (Either a (IterT m a))) => Read (IterT m a)
instance (Functor m, Read1 m) => Read1 (IterT m)
instance Show (m (Either a (IterT m a))) => Show (IterT m a)
instance (Functor m, Show1 m) => Show1 (IterT m)
instance Ord (m (Either a (IterT m a))) => Ord (IterT m a)
instance (Functor m, Ord1 m) => Ord1 (IterT m)
instance Eq (m (Either a (IterT m a))) => Eq (IterT m a)
instance (Functor m, Eq1 m) => Eq1 (IterT m)


-- | The free monad transformer
module Control.Monad.Trans.Free

-- | The base functor for a free monad.
data FreeF f a b
Pure :: a -> FreeF f a b
Free :: (f b) -> FreeF f a b

-- | The "free monad transformer" for a functor <tt>f</tt>
newtype FreeT f m a
FreeT :: m (FreeF f a (FreeT f m a)) -> FreeT f m a
runFreeT :: FreeT f m a -> m (FreeF f a (FreeT f m a))

-- | The "free monad" for a functor <tt>f</tt>.
type Free f = FreeT f Identity

-- | Pushes a layer into a free monad value.
free :: FreeF f a (Free f a) -> Free f a

-- | Evaluates the first layer out of a free monad value.
runFree :: Free f a -> FreeF f a (Free f a)

-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a

-- | Tear down a free monad transformer using iteration.
iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a

-- | Tear down a free monad transformer using iteration over a transformer.
iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a

-- | Lift a monad homomorphism from <tt>m</tt> to <tt>n</tt> into a monad
--   homomorphism from <tt><a>FreeT</a> f m</tt> to <tt><a>FreeT</a> f
--   n</tt>
--   
--   <pre>
--   <a>hoistFreeT</a> :: (<a>Monad</a> m, <a>Functor</a> f) =&gt; (m ~&gt; n) -&gt; <a>FreeT</a> f m ~&gt; <a>FreeT</a> f n
--   </pre>
hoistFreeT :: (Monad m, Functor f) => (forall a. m a -> n a) -> FreeT f m b -> FreeT f n b

-- | Lift a natural transformation from <tt>f</tt> to <tt>g</tt> into a
--   monad homomorphism from <tt><a>FreeT</a> f m</tt> to <tt><a>FreeT</a>
--   g n</tt>
transFreeT :: (Monad m, Functor g) => (forall a. f a -> g a) -> FreeT f m b -> FreeT g m b

-- | Cuts off a tree of computations at a given depth. If the depth is
--   <tt>0</tt> or less, no computation nor monadic effects will take
--   place.
--   
--   Some examples (<tt>n ≥ 0</tt>):
--   
--   <pre>
--   <a>cutoff</a> 0     _        ≡ <a>return</a> <a>Nothing</a>
--   <a>cutoff</a> (n+1) <a>.</a> <a>return</a> ≡ <a>return</a> <a>.</a> <a>Just</a>
--   <a>cutoff</a> (n+1) <a>.</a> <a>lift</a>   ≡ <a>lift</a> <a>.</a> <a>liftM</a> <a>Just</a>
--   <a>cutoff</a> (n+1) <a>.</a> <a>wrap</a>   ≡ <a>wrap</a> <a>.</a> <a>fmap</a> (<a>cutoff</a> n)
--   </pre>
--   
--   Calling <tt><a>retract</a> <a>.</a> <a>cutoff</a> n</tt> is always
--   terminating, provided each of the steps in the iteration is
--   terminating.
cutoff :: (Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a)

-- | <a>retract</a> is the left inverse of <a>liftF</a>
--   
--   <pre>
--   <a>retract</a> . <a>liftF</a> = <a>id</a>
--   </pre>
retract :: Monad f => Free f a -> f a

-- | Tear down a <a>Free</a> <a>Monad</a> using iteration.
iter :: Functor f => (f a -> a) -> Free f a -> a

-- | Like <a>iter</a> for monadic values.
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> Free f a -> m a

-- | Monads provide substitution (<a>fmap</a>) and renormalization
--   (<a>join</a>):
--   
--   <pre>
--   m <a>&gt;&gt;=</a> f = <a>join</a> (<a>fmap</a> f m)
--   </pre>
--   
--   A free <a>Monad</a> is one that does no work during the normalization
--   step beyond simply grafting the two monadic values together.
--   
--   <tt>[]</tt> is not a free <a>Monad</a> (in this sense) because
--   <tt><a>join</a> [[a]]</tt> smashes the lists flat.
--   
--   On the other hand, consider:
--   
--   <pre>
--   data Tree a = Bin (Tree a) (Tree a) | Tip a
--   </pre>
--   
--   <pre>
--   instance <a>Monad</a> Tree where
--     <a>return</a> = Tip
--     Tip a <a>&gt;&gt;=</a> f = f a
--     Bin l r <a>&gt;&gt;=</a> f = Bin (l <a>&gt;&gt;=</a> f) (r <a>&gt;&gt;=</a> f)
--   </pre>
--   
--   This <a>Monad</a> is the free <a>Monad</a> of Pair:
--   
--   <pre>
--   data Pair a = Pair a a
--   </pre>
--   
--   And we could make an instance of <a>MonadFree</a> for it directly:
--   
--   <pre>
--   instance <a>MonadFree</a> Pair Tree where
--      <a>wrap</a> (Pair l r) = Bin l r
--   </pre>
--   
--   Or we could choose to program with <tt><a>Free</a> Pair</tt> instead
--   of <tt>Tree</tt> and thereby avoid having to define our own
--   <a>Monad</a> instance.
--   
--   Moreover, <a>Control.Monad.Free.Church</a> provides a <a>MonadFree</a>
--   instance that can improve the <i>asymptotic</i> complexity of code
--   that constructs free monads by effectively reassociating the use of
--   (<a>&gt;&gt;=</a>). You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   See <a>Free</a> for a more formal definition of the free <a>Monad</a>
--   for a <a>Functor</a>.
class Monad m => MonadFree f m | m -> f where wrap = join . lift . wrap . fmap return
wrap :: MonadFree f m => f (m a) -> m a
instance Ord (m (FreeF f a (FreeT f m a))) => Ord (FreeT f m a)
instance Eq (m (FreeF f a (FreeT f m a))) => Eq (FreeT f m a)
instance (Eq a, Eq (f b)) => Eq (FreeF f a b)
instance (Ord a, Ord (f b)) => Ord (FreeF f a b)
instance (Show a, Show (f b)) => Show (FreeF f a b)
instance (Read a, Read (f b)) => Read (FreeF f a b)
instance (Typeable1 f, Typeable1 w, Typeable a, Data (w (FreeF f a (FreeT f w a))), Data a) => Data (FreeT f w a)
instance (Typeable1 f, Typeable a, Typeable b, Data a, Data (f b), Data b) => Data (FreeF f a b)
instance (Typeable1 f, Typeable1 w) => Typeable1 (FreeT f w)
instance Typeable1 f => Typeable2 (FreeF f)
instance (Monad m, Traversable m, Traversable f) => Traversable (FreeT f m)
instance (Foldable m, Foldable f) => Foldable (FreeT f m)
instance (Functor f, Monad m) => MonadFree f (FreeT f m)
instance (Functor f, MonadPlus m) => MonadPlus (FreeT f m)
instance (Functor f, MonadPlus m) => Alternative (FreeT f m)
instance (Functor f, MonadCont m) => MonadCont (FreeT f m)
instance (Functor f, MonadError e m) => MonadError e (FreeT f m)
instance (Functor f, MonadState s m) => MonadState s (FreeT f m)
instance (Functor f, MonadWriter w m) => MonadWriter w (FreeT f m)
instance (Functor f, MonadReader r m) => MonadReader r (FreeT f m)
instance (Functor f, MonadIO m) => MonadIO (FreeT f m)
instance MonadTrans (FreeT f)
instance (Functor f, Monad m) => Monad (FreeT f m)
instance (Functor f, Monad m) => Bind (FreeT f m)
instance (Functor f, Monad m) => Apply (FreeT f m)
instance (Functor f, Monad m) => Applicative (FreeT f m)
instance (Functor f, Monad m) => Functor (FreeT f m)
instance Read (m (FreeF f a (FreeT f m a))) => Read (FreeT f m a)
instance (Functor f, Read1 f, Functor m, Read1 m) => Read1 (FreeT f m)
instance Show (m (FreeF f a (FreeT f m a))) => Show (FreeT f m a)
instance (Functor f, Show1 f, Functor m, Show1 m) => Show1 (FreeT f m)
instance (Functor f, Ord1 f, Functor m, Ord1 m) => Ord1 (FreeT f m)
instance (Functor f, Eq1 f, Functor m, Eq1 m) => Eq1 (FreeT f m)
instance Traversable f => Bitraversable (FreeF f)
instance Foldable f => Bifoldable (FreeF f)
instance Functor f => Bifunctor (FreeF f)
instance Traversable f => Traversable (FreeF f a)
instance Foldable f => Foldable (FreeF f a)
instance Functor f => Functor (FreeF f a)
instance (Ord1 f, Ord a) => Ord1 (FreeF f a)
instance Ord1 f => Ord2 (FreeF f)
instance (Eq1 f, Eq a) => Eq1 (FreeF f a)
instance Eq1 f => Eq2 (FreeF f)
instance (Read1 f, Read a) => Read1 (FreeF f a)
instance Read1 f => Read2 (FreeF f)
instance (Show1 f, Show a) => Show1 (FreeF f a)
instance Show1 f => Show2 (FreeF f)


-- | Church-encoded free monad transformer.
module Control.Monad.Trans.Free.Church

-- | The "free monad transformer" for a functor <tt>f</tt>
newtype FT f m a
FT :: (forall r. (a -> m r) -> (f (m r) -> m r) -> m r) -> FT f m a
runFT :: FT f m a -> forall r. (a -> m r) -> (f (m r) -> m r) -> m r

-- | The "free monad" for a functor <tt>f</tt>.
type F f = FT f Identity

-- | Wrap a Church-encoding of a "free monad" as the free monad for a
--   functor.
free :: Functor f => (forall r. (a -> r) -> (f r -> r) -> r) -> F f a

-- | Unwrap the <a>Free</a> monad to obtain it's Church-encoded
--   representation.
runF :: Functor f => F f a -> (forall r. (a -> r) -> (f r -> r) -> r)

-- | Generate a Church-encoded free monad transformer from a <a>FreeT</a>
--   monad transformer.
toFT :: (Monad m, Functor f) => FreeT f m a -> FT f m a

-- | Convert to a <a>FreeT</a> free monad representation.
fromFT :: (Monad m, Functor f) => FT f m a -> FreeT f m a

-- | Tear down a free monad transformer using iteration.
iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FT f m a -> m a

-- | Tear down a free monad transformer using iteration over a transformer.
iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FT f m a -> t m a

-- | Lift a monad homomorphism from <tt>m</tt> to <tt>n</tt> into a monad
--   homomorphism from <tt><a>FT</a> f m</tt> to <tt><a>FT</a> f n</tt>
--   
--   <pre>
--   <a>hoistFT</a> :: (<a>Monad</a> m, <a>Monad</a> n, <a>Functor</a> f) =&gt; (m ~&gt; n) -&gt; <a>FT</a> f m ~&gt; <a>FT</a> f n
--   </pre>
hoistFT :: (Monad m, Monad n, Functor f) => (forall a. m a -> n a) -> FT f m b -> FT f n b

-- | Lift a natural transformation from <tt>f</tt> to <tt>g</tt> into a
--   monad homomorphism from <tt><a>FT</a> f m</tt> to <tt><a>FT</a> g
--   n</tt>
transFT :: (Monad m, Functor g) => (forall a. f a -> g a) -> FT f m b -> FT g m b

-- | Cuts off a tree of computations at a given depth. If the depth is 0 or
--   less, no computation nor monadic effects will take place.
--   
--   Some examples (n ≥ 0):
--   
--   <pre>
--   cutoff 0     _        == return Nothing
--   </pre>
--   
--   <pre>
--   cutoff (n+1) . return == return . Just
--   </pre>
--   
--   <pre>
--   cutoff (n+1) . lift   ==   lift . liftM Just
--   </pre>
--   
--   <pre>
--   cutoff (n+1) . wrap   ==  wrap . fmap (cutoff n)
--   </pre>
--   
--   Calling 'retract . cutoff n' is always terminating, provided each of
--   the steps in the iteration is terminating.
cutoff :: (Functor f, Monad m) => Integer -> FT f m a -> FT f m (Maybe a)

-- | Improve the asymptotic performance of code that builds a free monad
--   with only binds and returns by using <a>F</a> behind the scenes.
--   
--   This is based on the "Free Monads for Less" series of articles by
--   Edward Kmett:
--   
--   <a>http://comonad.com/reader/2011/free-monads-for-less/</a>
--   <a>http://comonad.com/reader/2011/free-monads-for-less-2/</a>
--   
--   and "Asymptotic Improvement of Computations over Free Monads" by Janis
--   Voightländer:
--   
--   <a>http://www.iai.uni-bonn.de/~jv/mpc08.pdf</a>
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a

-- | Convert to another free monad representation.
fromF :: (Functor f, MonadFree f m) => F f a -> m a

-- | Generate a Church-encoded free monad from a <a>Free</a> monad.
toF :: Functor f => Free f a -> F f a

-- | <a>retract</a> is the left inverse of <a>liftF</a>
--   
--   <pre>
--   <a>retract</a> . <a>liftF</a> = <a>id</a>
--   </pre>
retract :: (Functor f, Monad f) => F f a -> f a

-- | Tear down an <a>F</a> <a>Monad</a> using iteration.
iter :: Functor f => (f a -> a) -> F f a -> a

-- | Like <a>iter</a> for monadic values.
iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> F f a -> m a

-- | Monads provide substitution (<a>fmap</a>) and renormalization
--   (<a>join</a>):
--   
--   <pre>
--   m <a>&gt;&gt;=</a> f = <a>join</a> (<a>fmap</a> f m)
--   </pre>
--   
--   A free <a>Monad</a> is one that does no work during the normalization
--   step beyond simply grafting the two monadic values together.
--   
--   <tt>[]</tt> is not a free <a>Monad</a> (in this sense) because
--   <tt><a>join</a> [[a]]</tt> smashes the lists flat.
--   
--   On the other hand, consider:
--   
--   <pre>
--   data Tree a = Bin (Tree a) (Tree a) | Tip a
--   </pre>
--   
--   <pre>
--   instance <a>Monad</a> Tree where
--     <a>return</a> = Tip
--     Tip a <a>&gt;&gt;=</a> f = f a
--     Bin l r <a>&gt;&gt;=</a> f = Bin (l <a>&gt;&gt;=</a> f) (r <a>&gt;&gt;=</a> f)
--   </pre>
--   
--   This <a>Monad</a> is the free <a>Monad</a> of Pair:
--   
--   <pre>
--   data Pair a = Pair a a
--   </pre>
--   
--   And we could make an instance of <a>MonadFree</a> for it directly:
--   
--   <pre>
--   instance <a>MonadFree</a> Pair Tree where
--      <a>wrap</a> (Pair l r) = Bin l r
--   </pre>
--   
--   Or we could choose to program with <tt><a>Free</a> Pair</tt> instead
--   of <tt>Tree</tt> and thereby avoid having to define our own
--   <a>Monad</a> instance.
--   
--   Moreover, <a>Control.Monad.Free.Church</a> provides a <a>MonadFree</a>
--   instance that can improve the <i>asymptotic</i> complexity of code
--   that constructs free monads by effectively reassociating the use of
--   (<a>&gt;&gt;=</a>). You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   See <a>Free</a> for a more formal definition of the free <a>Monad</a>
--   for a <a>Functor</a>.
class Monad m => MonadFree f m | m -> f where wrap = join . lift . wrap . fmap return
wrap :: MonadFree f m => f (m a) -> m a
instance (Functor f, MonadState s m) => MonadState s (FT f m)
instance (Functor f, MonadWriter w m) => MonadWriter w (FT f m)
instance (Functor f, MonadReader r m) => MonadReader r (FT f m)
instance MonadCont m => MonadCont (FT f m)
instance (Functor f, MonadError e m) => MonadError e (FT f m)
instance MonadIO m => MonadIO (FT f m)
instance (Monad m, Traversable m, Traversable f) => Traversable (FT f m)
instance (Foldable f, Foldable m, Monad m) => Foldable (FT f m)
instance MonadPlus m => MonadPlus (FT f m)
instance Alternative m => Alternative (FT f m)
instance MonadTrans (FT f)
instance Functor f => MonadFree f (FT f m)
instance Monad (FT f m)
instance Bind (FT f m)
instance Applicative (FT f m)
instance Apply (FT f m)
instance Functor (FT f m)
instance (Functor f, Monad m, Ord (FreeT f m a)) => Ord (FT f m a)
instance (Functor f, Monad m, Eq (FreeT f m a)) => Eq (FT f m a)


-- | Monads for free
module Control.Monad.Free

-- | Monads provide substitution (<a>fmap</a>) and renormalization
--   (<a>join</a>):
--   
--   <pre>
--   m <a>&gt;&gt;=</a> f = <a>join</a> (<a>fmap</a> f m)
--   </pre>
--   
--   A free <a>Monad</a> is one that does no work during the normalization
--   step beyond simply grafting the two monadic values together.
--   
--   <tt>[]</tt> is not a free <a>Monad</a> (in this sense) because
--   <tt><a>join</a> [[a]]</tt> smashes the lists flat.
--   
--   On the other hand, consider:
--   
--   <pre>
--   data Tree a = Bin (Tree a) (Tree a) | Tip a
--   </pre>
--   
--   <pre>
--   instance <a>Monad</a> Tree where
--     <a>return</a> = Tip
--     Tip a <a>&gt;&gt;=</a> f = f a
--     Bin l r <a>&gt;&gt;=</a> f = Bin (l <a>&gt;&gt;=</a> f) (r <a>&gt;&gt;=</a> f)
--   </pre>
--   
--   This <a>Monad</a> is the free <a>Monad</a> of Pair:
--   
--   <pre>
--   data Pair a = Pair a a
--   </pre>
--   
--   And we could make an instance of <a>MonadFree</a> for it directly:
--   
--   <pre>
--   instance <a>MonadFree</a> Pair Tree where
--      <a>wrap</a> (Pair l r) = Bin l r
--   </pre>
--   
--   Or we could choose to program with <tt><a>Free</a> Pair</tt> instead
--   of <tt>Tree</tt> and thereby avoid having to define our own
--   <a>Monad</a> instance.
--   
--   Moreover, <a>Control.Monad.Free.Church</a> provides a <a>MonadFree</a>
--   instance that can improve the <i>asymptotic</i> complexity of code
--   that constructs free monads by effectively reassociating the use of
--   (<a>&gt;&gt;=</a>). You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   See <a>Free</a> for a more formal definition of the free <a>Monad</a>
--   for a <a>Functor</a>.
class Monad m => MonadFree f m | m -> f where wrap = join . lift . wrap . fmap return
wrap :: MonadFree f m => f (m a) -> m a

-- | The <a>Free</a> <a>Monad</a> for a <a>Functor</a> <tt>f</tt>.
--   
--   <i>Formally</i>
--   
--   A <a>Monad</a> <tt>n</tt> is a free <a>Monad</a> for <tt>f</tt> if
--   every monad homomorphism from <tt>n</tt> to another monad <tt>m</tt>
--   is equivalent to a natural transformation from <tt>f</tt> to
--   <tt>m</tt>.
--   
--   <i>Why Free?</i>
--   
--   Every "free" functor is left adjoint to some "forgetful" functor.
--   
--   If we define a forgetful functor <tt>U</tt> from the category of
--   monads to the category of functors that just forgets the <a>Monad</a>,
--   leaving only the <a>Functor</a>. i.e.
--   
--   <pre>
--   U (M,<a>return</a>,<a>join</a>) = M
--   </pre>
--   
--   then <a>Free</a> is the left adjoint to <tt>U</tt>.
--   
--   Being <a>Free</a> being left adjoint to <tt>U</tt> means that there is
--   an isomorphism between
--   
--   <tt><a>Free</a> f -&gt; m</tt> in the category of monads and <tt>f
--   -&gt; U m</tt> in the category of functors.
--   
--   Morphisms in the category of monads are <a>Monad</a> homomorphisms
--   (natural transformations that respect <a>return</a> and <a>join</a>).
--   
--   Morphisms in the category of functors are <a>Functor</a> homomorphisms
--   (natural transformations).
--   
--   Given this isomorphism, every monad homomorphism from <tt><a>Free</a>
--   f</tt> to <tt>m</tt> is equivalent to a natural transformation from
--   <tt>f</tt> to <tt>m</tt>
--   
--   Showing that this isomorphism holds is left as an exercise.
--   
--   In practice, you can just view a <tt><a>Free</a> f a</tt> as many
--   layers of <tt>f</tt> wrapped around values of type <tt>a</tt>, where
--   <tt>(<a>&gt;&gt;=</a>)</tt> performs substitution and grafts new
--   layers of <tt>f</tt> in for each of the free variables.
--   
--   This can be very useful for modeling domain specific languages, trees,
--   or other constructs.
--   
--   This instance of <a>MonadFree</a> is fairly naive about the encoding.
--   For more efficient free monad implementation see
--   <a>Control.Monad.Free.Church</a>, in particular note the
--   <a>improve</a> combinator. You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   A number of common monads arise as free monads,
--   
--   <ul>
--   <li>Given <tt>data Empty a</tt>, <tt><a>Free</a> Empty</tt> is
--   isomorphic to the <a>Identity</a> monad.</li>
--   <li><tt><a>Free</a> <a>Maybe</a></tt> can be used to model a
--   partiality monad where each layer represents running the computation
--   for a while longer.</li>
--   </ul>
data Free f a
Pure :: a -> Free f a
Free :: (f (Free f a)) -> Free f a

-- | <a>retract</a> is the left inverse of <a>lift</a> and <a>liftF</a>
--   
--   <pre>
--   <a>retract</a> . <a>lift</a> = <a>id</a>
--   <a>retract</a> . <a>liftF</a> = <a>id</a>
--   </pre>
retract :: Monad f => Free f a -> f a

-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a

-- | Tear down a <a>Free</a> <a>Monad</a> using iteration.
iter :: Functor f => (f a -> a) -> Free f a -> a

-- | Like iter for monadic values.
iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a

-- | Lift a natural transformation from <tt>f</tt> to <tt>g</tt> into a
--   natural transformation from <tt><tt>FreeT</tt> f</tt> to
--   <tt><tt>FreeT</tt> g</tt>.
hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b

-- | Convert a <a>Free</a> monad from <a>Control.Monad.Free</a> to a
--   <a>FreeT</a> monad from <a>Control.Monad.Trans.Free</a>.
toFreeT :: (Functor f, Monad m) => Free f a -> FreeT f m a

-- | Cuts off a tree of computations at a given depth. If the depth is 0 or
--   less, no computation nor monadic effects will take place.
--   
--   Some examples (n ≥ 0):
--   
--   <pre>
--   cutoff 0     _        == return Nothing
--   </pre>
--   
--   <pre>
--   cutoff (n+1) . return == return . Just
--   </pre>
--   
--   <pre>
--   cutoff (n+1) . lift   ==   lift . liftM Just
--   </pre>
--   
--   <pre>
--   cutoff (n+1) . wrap   ==  wrap . fmap (cutoff n)
--   </pre>
--   
--   Calling 'retract . cutoff n' is always terminating, provided each of
--   the steps in the iteration is terminating.
cutoff :: Functor f => Integer -> Free f a -> Free f (Maybe a)

-- | This is <tt>Prism' (Free f a) a</tt> in disguise
--   
--   <pre>
--   &gt;&gt;&gt; preview _Pure (Pure 3)
--   Just 3
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; review _Pure 3 :: Free Maybe Int
--   Pure 3
--   </pre>
_Pure :: (Choice p, Applicative m) => p a (m a) -> p (Free f a) (m (Free f a))

-- | This is <tt>Prism' (Free f a) (f (Free f a))</tt> in disguise
--   
--   <pre>
--   &gt;&gt;&gt; preview _Free (review _Free (Just (Pure 3)))
--   Just (Just (Pure 3))
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; review _Free (Just (Pure 3))
--   Free (Just (Pure 3))
--   </pre>
_Free :: (Choice p, Applicative m) => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))
instance (Typeable1 f, Typeable a, Data a, Data (f (Free f a))) => Data (Free f a)
instance Typeable1 f => Typeable1 (Free f)
instance Functor f => MonadFree f (Free f)
instance (Functor m, MonadCont m) => MonadCont (Free m)
instance (Functor m, MonadError e m) => MonadError e (Free m)
instance (Functor m, MonadState s m) => MonadState s (Free m)
instance (Functor m, MonadReader e m) => MonadReader e (Free m)
instance (Functor m, MonadWriter e m) => MonadWriter e (Free m)
instance Traversable1 f => Traversable1 (Free f)
instance Traversable f => Traversable (Free f)
instance Foldable1 f => Foldable1 (Free f)
instance Foldable f => Foldable (Free f)
instance MonadTrans Free
instance (Functor v, MonadPlus v) => MonadPlus (Free v)
instance Alternative v => Alternative (Free v)
instance Functor f => MonadFix (Free f)
instance Functor f => Monad (Free f)
instance Functor f => Bind (Free f)
instance Functor f => Applicative (Free f)
instance Functor f => Apply (Free f)
instance Functor f => Functor (Free f)
instance (Read (f (Free f a)), Read a) => Read (Free f a)
instance (Functor f, Read1 f) => Read1 (Free f)
instance (Show (f (Free f a)), Show a) => Show (Free f a)
instance (Functor f, Show1 f) => Show1 (Free f)
instance (Ord (f (Free f a)), Ord a) => Ord (Free f a)
instance (Functor f, Ord1 f) => Ord1 (Free f)
instance (Eq (f (Free f a)), Eq a) => Eq (Free f a)
instance (Functor f, Eq1 f) => Eq1 (Free f)


-- | "Free Monads for Less"
--   
--   The most straightforward way of implementing free monads is as a
--   recursive datatype that allows for arbitrarily deep nesting of the
--   base functor. This is akin to a tree, with the leaves containing the
--   values, and the nodes being a level of <a>Functor</a> over subtrees.
--   
--   For each time that the <a>fmap</a> or <a>&gt;&gt;=</a> operations is
--   used, the old tree is traversed up to the leaves, a new set of nodes
--   is allocated, and the old ones are garbage collected. Even if the
--   Haskell runtime optimizes some of the overhead through laziness and
--   generational garbage collection, the asymptotic runtime is still
--   quadratic.
--   
--   On the other hand, if the Church encoding is used, the tree only needs
--   to be constructed once, because:
--   
--   <ul>
--   <li>All uses of <a>fmap</a> are collapsed into a single one, so that
--   the values on the _leaves_ are transformed in one pass.</li>
--   </ul>
--   
--   <pre>
--   fmap f . fmap g == fmap (f . g)
--   </pre>
--   
--   <ul>
--   <li>All uses of <a>&gt;&gt;=</a> are right associated, so that every
--   new subtree created is final.</li>
--   </ul>
--   
--   <pre>
--   (m &gt;&gt;= f) &gt;&gt;= g == m &gt;&gt;= (\x -&gt; f x &gt;&gt;= g)
--   </pre>
--   
--   Asymptotically, the Church encoding supports the monadic operations
--   more efficiently than the naïve <a>Free</a>.
--   
--   This is based on the "Free Monads for Less" series of articles by
--   Edward Kmett:
--   
--   <ul>
--   <li><a>Free monads for less — Part 1</a></li>
--   <li><a>Free monads for less — Part 2</a></li>
--   </ul>
module Control.Monad.Free.Church

-- | The Church-encoded free monad for a functor <tt>f</tt>.
--   
--   It is <i>asymptotically</i> more efficient to use (<a>&gt;&gt;=</a>)
--   for <a>F</a> than it is to (<a>&gt;&gt;=</a>) with <a>Free</a>.
--   
--   <a>http://comonad.com/reader/2011/free-monads-for-less-2/</a>
newtype F f a
F :: (forall r. (a -> r) -> (f r -> r) -> r) -> F f a
runF :: F f a -> forall r. (a -> r) -> (f r -> r) -> r

-- | Improve the asymptotic performance of code that builds a free monad
--   with only binds and returns by using <a>F</a> behind the scenes.
--   
--   This is based on the "Free Monads for Less" series of articles by
--   Edward Kmett:
--   
--   <ul>
--   <li><a>Free monads for less — Part 1</a></li>
--   <li><a>Free monads for less — Part 2</a></li>
--   </ul>
--   
--   and <a>\"Asymptotic Improvement of Computations over Free Monads\"</a>
--   by Janis Voightländer.
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a

-- | Convert to another free monad representation.
fromF :: MonadFree f m => F f a -> m a

-- | Like iter for monadic values.
iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> F f a -> m a

-- | Generate a Church-encoded free monad from a <a>Free</a> monad.
toF :: Functor f => Free f a -> F f a

-- | <a>retract</a> is the left inverse of <a>lift</a> and <a>liftF</a>
--   
--   <pre>
--   <a>retract</a> . <a>lift</a> = <a>id</a>
--   <a>retract</a> . <a>liftF</a> = <a>id</a>
--   </pre>
retract :: Monad m => F m a -> m a

-- | Lift a natural transformation from <tt>f</tt> to <tt>g</tt> into a
--   natural transformation from <tt>F f</tt> to <tt>F g</tt>.
hoistF :: (forall x. f x -> g x) -> F f a -> F g a

-- | Monads provide substitution (<a>fmap</a>) and renormalization
--   (<a>join</a>):
--   
--   <pre>
--   m <a>&gt;&gt;=</a> f = <a>join</a> (<a>fmap</a> f m)
--   </pre>
--   
--   A free <a>Monad</a> is one that does no work during the normalization
--   step beyond simply grafting the two monadic values together.
--   
--   <tt>[]</tt> is not a free <a>Monad</a> (in this sense) because
--   <tt><a>join</a> [[a]]</tt> smashes the lists flat.
--   
--   On the other hand, consider:
--   
--   <pre>
--   data Tree a = Bin (Tree a) (Tree a) | Tip a
--   </pre>
--   
--   <pre>
--   instance <a>Monad</a> Tree where
--     <a>return</a> = Tip
--     Tip a <a>&gt;&gt;=</a> f = f a
--     Bin l r <a>&gt;&gt;=</a> f = Bin (l <a>&gt;&gt;=</a> f) (r <a>&gt;&gt;=</a> f)
--   </pre>
--   
--   This <a>Monad</a> is the free <a>Monad</a> of Pair:
--   
--   <pre>
--   data Pair a = Pair a a
--   </pre>
--   
--   And we could make an instance of <a>MonadFree</a> for it directly:
--   
--   <pre>
--   instance <a>MonadFree</a> Pair Tree where
--      <a>wrap</a> (Pair l r) = Bin l r
--   </pre>
--   
--   Or we could choose to program with <tt><a>Free</a> Pair</tt> instead
--   of <tt>Tree</tt> and thereby avoid having to define our own
--   <a>Monad</a> instance.
--   
--   Moreover, <a>Control.Monad.Free.Church</a> provides a <a>MonadFree</a>
--   instance that can improve the <i>asymptotic</i> complexity of code
--   that constructs free monads by effectively reassociating the use of
--   (<a>&gt;&gt;=</a>). You may also want to take a look at the
--   <tt>kan-extensions</tt> package
--   (<a>http://hackage.haskell.org/package/kan-extensions</a>).
--   
--   See <a>Free</a> for a more formal definition of the free <a>Monad</a>
--   for a <a>Functor</a>.
class Monad m => MonadFree f m | m -> f where wrap = join . lift . wrap . fmap return
wrap :: MonadFree f m => f (m a) -> m a

-- | A version of lift that can be used with just a Functor for f.
liftF :: (Functor f, MonadFree f m) => f a -> m a
instance MonadCont m => MonadCont (F m)
instance MonadWriter w m => MonadWriter w (F m)
instance MonadReader e m => MonadReader e (F m)
instance MonadState s m => MonadState s (F m)
instance Functor f => MonadFree f (F f)
instance MonadTrans F
instance MonadPlus f => MonadPlus (F f)
instance (Foldable f, Functor f) => Foldable (F f)
instance MonadFix (F f)
instance Monad (F f)
instance Bind (F f)
instance Alternative f => Alternative (F f)
instance Applicative (F f)
instance Apply (F f)
instance Functor (F f)


module Control.Comonad.Cofree.Class

-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
unwrap :: ComonadCofree f w => w a -> f (w a)
instance (ComonadCofree f w, Semigroup m, Monoid m) => ComonadCofree f (TracedT m w)
instance ComonadCofree f w => ComonadCofree f (StoreT s w)
instance ComonadCofree f w => ComonadCofree f (EnvT e w)
instance ComonadCofree f w => ComonadCofree f (IdentityT w)
instance ComonadCofree (Const b) ((,) b)
instance ComonadCofree Maybe NonEmpty


-- | The cofree comonad transformer
module Control.Comonad.Trans.Cofree

-- | This is a cofree comonad of some functor <tt>f</tt>, with a comonad
--   <tt>w</tt> threaded through it at each level.
newtype CofreeT f w a
CofreeT :: w (CofreeF f a (CofreeT f w a)) -> CofreeT f w a
runCofreeT :: CofreeT f w a -> w (CofreeF f a (CofreeT f w a))

-- | The cofree <a>Comonad</a> of a functor <tt>f</tt>.
type Cofree f = CofreeT f Identity

-- | Wrap another layer around a cofree comonad value.
--   
--   <tt>cofree</tt> is a right inverse of <a>runCofree</a>.
--   
--   <pre>
--   runCofree . cofree == id
--   </pre>
cofree :: CofreeF f a (Cofree f a) -> Cofree f a

-- | Unpeel the first layer off a cofree comonad value.
--   
--   <tt>runCofree</tt> is a right inverse of <a>cofree</a>.
--   
--   <pre>
--   cofree . runCofree == id
--   </pre>
runCofree :: Cofree f a -> CofreeF f a (Cofree f a)

-- | This is the base functor of the cofree comonad transformer.
data CofreeF f a b
(:<) :: a -> f b -> CofreeF f a b

-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
unwrap :: ComonadCofree f w => w a -> f (w a)

-- | Extract the head of the base functor
headF :: CofreeF f a b -> a

-- | Extract the tails of the base functor
tailF :: CofreeF f a b -> f b

-- | Unfold a <tt>CofreeT</tt> comonad transformer from a coalgebra and an
--   initial comonad.
coiterT :: (Functor f, Comonad w) => (w a -> f (w a)) -> w a -> CofreeT f w a
instance (Eq a, Eq (f b)) => Eq (CofreeF f a b)
instance (Ord a, Ord (f b)) => Ord (CofreeF f a b)
instance (Show a, Show (f b)) => Show (CofreeF f a b)
instance (Read a, Read (f b)) => Read (CofreeF f a b)
instance (Typeable1 f, Typeable1 w, Typeable a, Data (w (CofreeF f a (CofreeT f w a))), Data a) => Data (CofreeT f w a)
instance (Typeable1 f, Typeable a, Typeable b, Data a, Data (f b), Data b) => Data (CofreeF f a b)
instance (Typeable1 f, Typeable1 w) => Typeable1 (CofreeT f w)
instance Typeable1 f => Typeable2 (CofreeF f)
instance (Alternative f, MonadZip f, MonadZip m) => MonadZip (CofreeT f m)
instance Alternative f => MonadTrans (CofreeT f)
instance (Alternative f, Applicative w) => Applicative (CofreeT f w)
instance (Alternative f, Monad w) => Monad (CofreeT f w)
instance Ord (w (CofreeF f a (CofreeT f w a))) => Ord (CofreeT f w a)
instance Eq (w (CofreeF f a (CofreeT f w a))) => Eq (CofreeT f w a)
instance Read (w (CofreeF f a (CofreeT f w a))) => Read (CofreeT f w a)
instance Show (w (CofreeF f a (CofreeT f w a))) => Show (CofreeT f w a)
instance (Functor f, Comonad w) => ComonadCofree f (CofreeT f w)
instance Functor f => ComonadTrans (CofreeT f)
instance (Traversable f, Traversable w) => Traversable (CofreeT f w)
instance (Foldable f, Foldable w) => Foldable (CofreeT f w)
instance (Functor f, Comonad w) => Comonad (CofreeT f w)
instance (Functor f, Functor w) => Functor (CofreeT f w)
instance Traversable f => Bitraversable (CofreeF f)
instance Foldable f => Bifoldable (CofreeF f)
instance Functor f => Bifunctor (CofreeF f)
instance Traversable f => Traversable (CofreeF f a)
instance Foldable f => Foldable (CofreeF f a)
instance Functor f => Functor (CofreeF f a)


-- | The coiterative comonad generated by a comonad
module Control.Comonad.Trans.Coiter

-- | This is the coiterative comonad generated by a comonad
newtype CoiterT w a
CoiterT :: w (a, CoiterT w a) -> CoiterT w a
runCoiterT :: CoiterT w a -> w (a, CoiterT w a)

-- | The coiterative comonad
type Coiter = CoiterT Identity

-- | Prepends a result to a coiterative computation.
--   
--   <pre>
--   runCoiter . uncurry coiter == id
--   </pre>
coiter :: a -> Coiter a -> Coiter a

-- | Extracts the first result from a coiterative computation.
--   
--   <pre>
--   uncurry coiter . runCoiter == id
--   </pre>
runCoiter :: Coiter a -> (a, Coiter a)

-- | Unfold a <tt>CoiterT</tt> comonad transformer from a cokleisli arrow
--   and an initial comonadic seed.
unfold :: Comonad w => (w a -> a) -> w a -> CoiterT w a

-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
unwrap :: ComonadCofree f w => w a -> f (w a)
instance (Typeable1 w, Typeable a, Data (w (a, CoiterT w a)), Data a) => Data (CoiterT w a)
instance Typeable1 w => Typeable1 (CoiterT w)
instance Ord (w (a, CoiterT w a)) => Ord (CoiterT w a)
instance Eq (w (a, CoiterT w a)) => Eq (CoiterT w a)
instance Read (w (a, CoiterT w a)) => Read (CoiterT w a)
instance Show (w (a, CoiterT w a)) => Show (CoiterT w a)
instance ComonadStore s w => ComonadStore s (CoiterT w)
instance ComonadTraced m w => ComonadTraced m (CoiterT w)
instance ComonadHoist CoiterT
instance ComonadEnv e w => ComonadEnv e (CoiterT w)
instance Comonad w => ComonadCofree Identity (CoiterT w)
instance ComonadTrans CoiterT
instance Traversable w => Traversable (CoiterT w)
instance Foldable w => Foldable (CoiterT w)
instance Comonad w => Comonad (CoiterT w)
instance Functor w => Functor (CoiterT w)
instance (Functor w, Read1 w) => Read1 (CoiterT w)
instance (Functor w, Show1 w) => Show1 (CoiterT w)
instance (Functor w, Ord1 w) => Ord1 (CoiterT w)
instance (Functor w, Eq1 w) => Eq1 (CoiterT w)


-- | Cofree comonads
module Control.Comonad.Cofree

-- | The <a>Cofree</a> <a>Comonad</a> of a functor <tt>f</tt>.
--   
--   <i>Formally</i>
--   
--   A <a>Comonad</a> <tt>v</tt> is a cofree <a>Comonad</a> for <tt>f</tt>
--   if every comonad homomorphism another comonad <tt>w</tt> to <tt>v</tt>
--   is equivalent to a natural transformation from <tt>w</tt> to
--   <tt>f</tt>.
--   
--   A <tt>cofree</tt> functor is right adjoint to a forgetful functor.
--   
--   Cofree is a functor from the category of functors to the category of
--   comonads that is right adjoint to the forgetful functor from the
--   category of comonads to the category of functors that forgets how to
--   <a>extract</a> and <a>duplicate</a>, leaving you with only a
--   <a>Functor</a>.
--   
--   In practice, cofree comonads are quite useful for annotating syntax
--   trees, or talking about streams.
--   
--   A number of common comonads arise directly as cofree comonads.
--   
--   For instance,
--   
--   <ul>
--   <li><tt><a>Cofree</a> <a>Maybe</a></tt> forms the a comonad for a
--   non-empty list.</li>
--   <li><tt><a>Cofree</a> (<a>Const</a> b)</tt> is a product.</li>
--   <li><tt><a>Cofree</a> <tt>Identity</tt></tt> forms an infinite
--   stream.</li>
--   <li><tt><a>Cofree</a> ((-&gt;) b)'</tt> describes a Moore machine with
--   states labeled with values of type a, and transitions on edges of type
--   b.</li>
--   </ul>
--   
--   Furthermore, if the functor <tt>f</tt> forms a monoid (for example, by
--   being an instance of <a>Alternative</a>), the resulting <a>Comonad</a>
--   is also a <a>Monad</a>. See <a>Monadic Augment and Generalised
--   Shortcut Fusion</a> by Neil Ghani et al., Section 4.3 for more
--   details.
--   
--   In particular, if <tt>f a ≡ [a]</tt>, the resulting data structure is
--   a <a>Rose tree</a>. For a practical application, check <a>Higher
--   Dimensional Trees, Algebraically</a> by Neil Ghani et al.
data Cofree f a
(:<) :: a -> f (Cofree f a) -> Cofree f a

-- | Allows you to peel a layer off a cofree comonad.
class (Functor f, Comonad w) => ComonadCofree f w | w -> f
unwrap :: ComonadCofree f w => w a -> f (w a)

-- | <pre>
--   <a>lower</a> . <a>section</a> = <a>id</a>
--   </pre>
section :: Comonad f => f a -> Cofree f a

-- | Use coiteration to generate a cofree comonad from a seed.
--   
--   <pre>
--   <a>coiter</a> f = <a>unfold</a> (<a>id</a> <a>&amp;&amp;&amp;</a> f)
--   </pre>
coiter :: Functor f => (a -> f a) -> a -> Cofree f a

-- | Unfold a cofree comonad from a seed.
unfold :: Functor f => (b -> (a, f b)) -> b -> Cofree f a

-- | This is a lens that can be used to read or write from the target of
--   <a>extract</a>.
--   
--   Using (^.) from the <tt>lens</tt> package:
--   
--   <pre>
--   foo ^. <a>_extract</a> == <a>extract</a> foo
--   </pre>
--   
--   For more on lenses see the <tt>lens</tt> package on hackage
--   
--   <pre>
--   <a>_extract</a> :: Lens' (<a>Cofree</a> g a) a
--   </pre>
_extract :: Functor f => (a -> f a) -> Cofree g a -> f (Cofree g a)

-- | This is a lens that can be used to read or write to the tails of a
--   <a>Cofree</a> <a>Comonad</a>.
--   
--   Using (^.) from the <tt>lens</tt> package:
--   
--   <pre>
--   foo ^. <a>_unwrap</a> == <a>unwrap</a> foo
--   </pre>
--   
--   For more on lenses see the <tt>lens</tt> package on hackage
--   
--   <pre>
--   <a>_unwrap</a> :: Lens' (<a>Cofree</a> g a) (g (<a>Cofree</a> g a))
--   </pre>
_unwrap :: Functor f => (g (Cofree g a) -> f (g (Cofree g a))) -> Cofree g a -> f (Cofree g a)

-- | Construct a <tt>Lens</tt> into a <tt><a>Cofree</a> f</tt> given a list
--   of lenses into the base functor.
--   
--   For more on lenses see the <tt>lens</tt> package on hackage.
--   
--   <pre>
--   telescoped :: <a>Functor</a> g =&gt; [Lens' (<a>Cofree</a> g a) (g (<a>Cofree</a> g a))] -&gt; Lens' (<a>Cofree</a> g a) a
--   </pre>
telescoped :: (Functor f, Functor g) => [(Cofree g a -> f (Cofree g a)) -> g (Cofree g a) -> f (g (Cofree g a))] -> (a -> f a) -> Cofree g a -> f (Cofree g a)
instance ComonadTraced m w => ComonadTraced m (Cofree w)
instance ComonadStore s w => ComonadStore s (Cofree w)
instance ComonadEnv e w => ComonadEnv e (Cofree w)
instance (Typeable1 f, Data (f (Cofree f a)), Data a) => Data (Cofree f a)
instance (Typeable1 f, Typeable a) => Typeable (Cofree f a)
instance Typeable1 f => Typeable1 (Cofree f)
instance Traversable1 f => Traversable1 (Cofree f)
instance Traversable f => Traversable (Cofree f)
instance Foldable1 f => Foldable1 (Cofree f)
instance Foldable f => Foldable (Cofree f)
instance (Functor f, Ord1 f) => Ord1 (Cofree f)
instance (Ord (f (Cofree f a)), Ord a) => Ord (Cofree f a)
instance (Functor f, Eq1 f) => Eq1 (Cofree f)
instance (Eq (f (Cofree f a)), Eq a) => Eq (Cofree f a)
instance (Read (f (Cofree f a)), Read a) => Read (Cofree f a)
instance (Functor f, Read1 f) => Read1 (Cofree f)
instance (Show (f (Cofree f a)), Show a) => Show (Cofree f a)
instance (Functor f, Show1 f) => Show1 (Cofree f)
instance Alternative f => Applicative (Cofree f)
instance ComonadApply f => ComonadApply (Cofree f)
instance Apply f => Apply (Cofree f)
instance (Alternative f, MonadZip f) => MonadZip (Cofree f)
instance Alternative f => Monad (Cofree f)
instance ComonadTrans Cofree
instance Functor f => Comonad (Cofree f)
instance Functor f => Extend (Cofree f)
instance Functor f => Functor (Cofree f)
instance Distributive f => Distributive (Cofree f)
instance Functor f => ComonadCofree f (Cofree f)


-- | Left distributive <a>Alternative</a> functors for free, based on a
--   design by Stijn van Drongelen.
module Control.Alternative.Free
newtype Alt f a
Alt :: [AltF f a] -> Alt f a
alternatives :: Alt f a -> [AltF f a]
data AltF f a
Ap :: f a -> Alt f (a -> b) -> AltF f b
Pure :: a -> AltF f a

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt>, this
--   gives a canonical monoidal natural transformation from <tt><a>Alt</a>
--   f</tt> to <tt>g</tt>.
runAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g a

-- | A version of <tt>lift</tt> that can be used with just a <a>Functor</a>
--   for <tt>f</tt>.
liftAlt :: Functor f => f a -> Alt f a

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt> this
--   gives a monoidal natural transformation from <tt>Alt f</tt> to <tt>Alt
--   g</tt>.
hoistAlt :: (forall a. f a -> g a) -> Alt f b -> Alt g b
instance Typeable1 f => Typeable1 (AltF f)
instance Typeable1 f => Typeable1 (Alt f)
instance Functor f => Monoid (Alt f a)
instance Functor f => Semigroup (Alt f a)
instance Functor f => Alternative (Alt f)
instance Functor f => Apply (Alt f)
instance Functor f => Applicative (Alt f)
instance Functor f => Applicative (AltF f)
instance Functor f => Functor (Alt f)
instance Functor f => Functor (AltF f)


-- | <a>Applicative</a> functor transformers for free
module Control.Applicative.Trans.Free

-- | The free <a>Applicative</a> transformer for a <a>Functor</a>
--   <tt>f</tt> over <a>Applicative</a> <tt>g</tt>.
newtype ApT f g a
ApT :: g (ApF f g a) -> ApT f g a
getApT :: ApT f g a -> g (ApF f g a)

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
data ApF f g a
Pure :: a -> ApF f g a
Ap :: f a -> ApT f g (a -> b) -> ApF f g b

-- | A version of <tt>lift</tt> that can be used with no constraint for
--   <tt>f</tt>.
liftApT :: Applicative g => f a -> ApT f g a

-- | Lift an action of the "outer" <a>Functor</a> <tt>g a</tt> to
--   <tt><a>ApT</a> f g a</tt>.
liftApO :: Functor g => g a -> ApT f g a

-- | Given natural transformations <tt>f ~&gt; h</tt> and <tt>g . h ~&gt;
--   h</tt> this gives a natural transformation <tt>ApT f g ~&gt; h</tt>.
runApT :: (Applicative h, Functor g) => (forall a. f a -> h a) -> (forall a. g (h a) -> h a) -> ApT f g b -> h b

-- | Given natural transformations <tt>f ~&gt; h</tt> and <tt>g . h ~&gt;
--   h</tt> this gives a natural transformation <tt>ApF f g ~&gt; h</tt>.
runApF :: (Applicative h, Functor g) => (forall a. f a -> h a) -> (forall a. g (h a) -> h a) -> ApF f g b -> h b

-- | Perform a monoidal analysis over <tt><a>ApT</a> f g b</tt> value.
--   
--   Examples:
--   
--   <pre>
--   height :: (<a>Functor</a> g, <a>Foldable</a> g) =&gt; <a>ApT</a> f g a -&gt; <a>Int</a>
--   height = <a>getSum</a> . runApT_ (_ -&gt; <a>Sum</a> 1) <a>maximum</a>
--   </pre>
--   
--   <pre>
--   size :: (<a>Functor</a> g, <a>Foldable</a> g) =&gt; <a>ApT</a> f g a -&gt; <a>Int</a>
--   size = <a>getSum</a> . runApT_ (_ -&gt; <a>Sum</a> 1) <a>fold</a>
--   </pre>
runApT_ :: (Functor g, Monoid m) => (forall a. f a -> m) -> (g m -> m) -> ApT f g b -> m

-- | Given a natural transformation from <tt>f</tt> to <tt>f'</tt> this
--   gives a monoidal natural transformation from <tt>ApT f g</tt> to
--   <tt>ApT f' g</tt>.
hoistApT :: Functor g => (forall a. f a -> f' a) -> ApT f g b -> ApT f' g b

-- | Given a natural transformation from <tt>f</tt> to <tt>f'</tt> this
--   gives a monoidal natural transformation from <tt>ApF f g</tt> to
--   <tt>ApF f' g</tt>.
hoistApF :: Functor g => (forall a. f a -> f' a) -> ApF f g b -> ApF f' g b

-- | Given a natural transformation from <tt>g</tt> to <tt>g'</tt> this
--   gives a monoidal natural transformation from <tt>ApT f g</tt> to
--   <tt>ApT f g'</tt>.
transApT :: Functor g => (forall a. g a -> g' a) -> ApT f g b -> ApT f g' b

-- | Given a natural transformation from <tt>g</tt> to <tt>g'</tt> this
--   gives a monoidal natural transformation from <tt>ApF f g</tt> to
--   <tt>ApF f g'</tt>.
transApF :: Functor g => (forall a. g a -> g' a) -> ApF f g b -> ApF f g' b

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
type Ap f = ApT f Identity

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt>, this
--   gives a canonical monoidal natural transformation from <tt><a>Ap</a>
--   f</tt> to <tt>g</tt>.
--   
--   <pre>
--   runAp t == retractApp . hoistApp t
--   </pre>
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a

-- | Perform a monoidal analysis over free applicative value.
--   
--   Example:
--   
--   <pre>
--   count :: <a>Ap</a> f a -&gt; <a>Int</a>
--   count = <a>getSum</a> . runAp_ (\_ -&gt; <a>Sum</a> 1)
--   </pre>
runAp_ :: Monoid m => (forall x. f x -> m) -> Ap f a -> m

-- | Interprets the free applicative functor over f using the semantics for
--   <a>pure</a> and <a>&lt;*&gt;</a> given by the Applicative instance for
--   f.
--   
--   <pre>
--   retractApp == runAp id
--   </pre>
retractAp :: Applicative f => Ap f a -> f a

-- | The free <a>Alternative</a> for a <a>Functor</a> <tt>f</tt>.
type Alt f = ApT f []

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt>, this
--   gives a canonical monoidal natural transformation from <tt><a>Alt</a>
--   f</tt> to <tt>g</tt>.
runAlt :: (Alternative g, Foldable t) => (forall x. f x -> g x) -> ApT f t a -> g a
instance (Typeable1 f, Typeable1 g) => Typeable1 (ApF f g)
instance (Typeable1 f, Typeable1 g) => Typeable1 (ApT f g)
instance Alternative g => Alternative (ApT f g)
instance Applicative g => Apply (ApT f g)
instance Applicative g => Apply (ApF f g)
instance Applicative g => Applicative (ApT f g)
instance Applicative g => Applicative (ApF f g)
instance Functor g => Functor (ApT f g)
instance Functor g => Functor (ApF f g)


-- | <a>Applicative</a> functors for free
module Control.Applicative.Free

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
data Ap f a
Pure :: a -> Ap f a
Ap :: f a -> Ap f (a -> b) -> Ap f b

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt>, this
--   gives a canonical monoidal natural transformation from <tt><a>Ap</a>
--   f</tt> to <tt>g</tt>.
--   
--   <pre>
--   runAp t == retractApp . hoistApp t
--   </pre>
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a

-- | Perform a monoidal analysis over free applicative value.
--   
--   Example:
--   
--   <pre>
--   count :: Ap f a -&gt; Int
--   count = getSum . runAp_ (\_ -&gt; Sum 1)
--   </pre>
runAp_ :: Monoid m => (forall a. f a -> m) -> Ap f b -> m

-- | A version of <tt>lift</tt> that can be used with just a <a>Functor</a>
--   for <tt>f</tt>.
liftAp :: f a -> Ap f a

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt> this
--   gives a monoidal natural transformation from <tt>Ap f</tt> to <tt>Ap
--   g</tt>.
hoistAp :: (forall a. f a -> g a) -> Ap f b -> Ap g b

-- | Interprets the free applicative functor over f using the semantics for
--   <a>pure</a> and <a>&lt;*&gt;</a> given by the Applicative instance for
--   f.
--   
--   <pre>
--   retractApp == runAp id
--   </pre>
retractAp :: Applicative f => Ap f a -> f a
instance Typeable1 f => Typeable1 (Ap f)
instance Applicative (Ap f)
instance Apply (Ap f)
instance Functor (Ap f)
