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


-- | 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>https://ekmett.github.io/reader/2008/monads-for-free/</a>
--   <a>https://ekmett.github.io/reader/2011/free-monads-for-less/</a>
@package free
@version 5.2


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

-- | 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 :: forall f g a. Alternative g => (forall x. () => f x -> g x) -> Alt f a -> g a

-- | A version of <tt>lift</tt> that can be used with any <tt>f</tt>.
liftAlt :: 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 Data.Functor.Alt.Alt (Control.Alternative.Free.Alt f)
instance GHC.Internal.Base.Alternative (Control.Alternative.Free.Alt f)
instance GHC.Internal.Base.Applicative (Control.Alternative.Free.Alt f)
instance GHC.Internal.Base.Applicative (Control.Alternative.Free.AltF f)
instance Data.Functor.Bind.Class.Apply (Control.Alternative.Free.Alt f)
instance GHC.Internal.Base.Functor (Control.Alternative.Free.Alt f)
instance GHC.Internal.Base.Functor (Control.Alternative.Free.AltF f)
instance GHC.Internal.Base.Monoid (Control.Alternative.Free.Alt f a)
instance GHC.Internal.Base.Semigroup (Control.Alternative.Free.Alt f a)


-- | Final encoding of free <a>Alternative</a> functors.
module Control.Alternative.Free.Final

-- | The free <a>Alternative</a> for any <tt>f</tt>.
newtype Alt (f :: Type -> Type) a
Alt :: (forall (g :: Type -> Type). Alternative g => (forall x. () => f x -> g x) -> g a) -> Alt (f :: Type -> Type) a
[_runAlt] :: Alt (f :: Type -> Type) a -> forall (g :: Type -> Type). Alternative g => (forall x. () => f x -> g x) -> g 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 :: forall f g a. Alternative g => (forall x. () => f x -> g x) -> Alt f a -> g a

-- | A version of <tt>lift</tt> that can be used with <tt>f</tt>.
liftAlt :: 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 Data.Functor.Alt.Alt (Control.Alternative.Free.Final.Alt f)
instance GHC.Internal.Base.Alternative (Control.Alternative.Free.Final.Alt f)
instance GHC.Internal.Base.Applicative (Control.Alternative.Free.Final.Alt f)
instance Data.Functor.Bind.Class.Apply (Control.Alternative.Free.Final.Alt f)
instance GHC.Internal.Base.Functor (Control.Alternative.Free.Final.Alt f)
instance GHC.Internal.Base.Monoid (Control.Alternative.Free.Final.Alt f a)
instance GHC.Internal.Base.Semigroup (Control.Alternative.Free.Final.Alt f a)


-- | <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 :: Type -> Type) a
[Pure] :: forall a (f :: Type -> Type). a -> Ap f a
[Ap] :: forall (f :: Type -> Type) a1 a. f a1 -> Ap f (a1 -> a) -> Ap f a

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

-- | Tear down a free <a>Applicative</a> using iteration.
iterAp :: Functor g => (g a -> a) -> Ap g a -> 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 GHC.Internal.Base.Applicative (Control.Applicative.Free.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Ap f)
instance Control.Comonad.Comonad f => Control.Comonad.Comonad (Control.Applicative.Free.Ap f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Applicative.Free.Ap f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Applicative.Free.Ap f a)
instance Data.Foldable1.Foldable1 f => Data.Foldable1.Foldable1 (Control.Applicative.Free.Ap f)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Applicative.Free.Ap f)
instance GHC.Internal.Base.Functor (Control.Applicative.Free.Ap f)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Applicative.Free.Ap f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Applicative.Free.Ap f a)


-- | A faster free applicative. Based on <a>Dave Menendez's work</a>.
module Control.Applicative.Free.Fast

-- | The free applicative is composed of a sequence of effects, and a pure
--   function to apply that sequence to. The fast free applicative
--   separates these from each other, so that the sequence may be built up
--   independently, and so that <a>fmap</a> can run in constant time by
--   having immediate access to the pure function.
data ASeq (f :: Type -> Type) a
[ANil] :: forall (f :: Type -> Type). ASeq f ()
[ACons] :: forall (f :: Type -> Type) a1 u. f a1 -> ASeq f u -> ASeq f (a1, u)

-- | Interprets the sequence of effects using the semantics for <a>pure</a>
--   and <a>&lt;*&gt;</a> given by the Applicative instance for <tt>f</tt>.
reduceASeq :: Applicative f => ASeq f u -> f u

-- | Given a natural transformation from <tt>f</tt> to <tt>g</tt> this
--   gives a natural transformation from <tt>ASeq f</tt> to <tt>ASeq
--   g</tt>.
hoistASeq :: (forall x. () => f x -> g x) -> ASeq f a -> ASeq g a

-- | Traverse a sequence with resepect to its interpretation type
--   <tt>f</tt>.
traverseASeq :: Applicative h => (forall x. () => f x -> h (g x)) -> ASeq f a -> h (ASeq g a)

-- | It may not be obvious, but this essentially acts like ++, traversing
--   the first sequence and creating a new one by appending the second
--   sequence. The difference is that this also has to modify the return
--   functions and that the return type depends on the input types.
--   
--   See the source of <a>hoistAp</a> as an example usage.
rebaseASeq :: forall (f :: Type -> Type) u y z v. ASeq f u -> (forall x. () => (x -> y) -> ASeq f x -> z) -> (v -> u -> y) -> ASeq f v -> z

-- | The faster free <a>Applicative</a>.
newtype Ap (f :: Type -> Type) a
Ap :: (forall u y z. () => (forall x. () => (x -> y) -> ASeq f x -> z) -> (u -> a -> y) -> ASeq f u -> z) -> Ap (f :: Type -> Type) a
[unAp] :: Ap (f :: Type -> Type) a -> forall u y z. () => (forall x. () => (x -> y) -> ASeq f x -> z) -> (u -> a -> y) -> ASeq f u -> z

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

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

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

-- | 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 x. () => f x -> g x) -> Ap f a -> Ap g a
instance GHC.Internal.Base.Applicative (Control.Applicative.Free.Fast.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Fast.Ap f)
instance GHC.Internal.Base.Functor (Control.Applicative.Free.Fast.Ap f)


-- | Final encoding of free <a>Applicative</a> functors.
module Control.Applicative.Free.Final

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
newtype Ap (f :: Type -> Type) a
Ap :: (forall (g :: Type -> Type). Applicative g => (forall x. () => f x -> g x) -> g a) -> Ap (f :: Type -> Type) a
[_runAp] :: Ap (f :: Type -> Type) a -> forall (g :: Type -> Type). Applicative g => (forall x. () => f x -> g x) -> g a

-- | 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 GHC.Internal.Base.Applicative (Control.Applicative.Free.Final.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Final.Ap f)
instance GHC.Internal.Base.Functor (Control.Applicative.Free.Final.Ap 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 :: Type -> Type) (g :: Type -> Type) a
ApT :: g (ApF f g a) -> ApT (f :: Type -> Type) (g :: Type -> Type) a
[getApT] :: ApT (f :: Type -> Type) (g :: Type -> Type) a -> g (ApF f g a)

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
data ApF (f :: Type -> Type) (g :: Type -> Type) a
[Pure] :: forall a (f :: Type -> Type) (g :: Type -> Type). a -> ApF f g a
[Ap] :: forall (f :: Type -> Type) a1 (g :: Type -> Type) a. f a1 -> ApT f g (a1 -> a) -> ApF f g a

-- | A version of <tt>lift</tt> that can be used with no constraint for
--   <tt>f</tt>.
liftApT :: forall (g :: Type -> Type) f a. 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 :: forall g a (f :: Type -> Type). 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 = <tt>getSum</tt> . runApT_ (_ -&gt; <tt>Sum</tt> 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 = <tt>getSum</tt> . runApT_ (_ -&gt; <tt>Sum</tt> 1) <tt>fold</tt>
--   </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 :: forall (g :: Type -> Type) f f' b. 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 :: forall (g :: Type -> Type) f f' b. 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 :: forall g g' (f :: Type -> Type) b. 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 :: forall g g' (f :: Type -> Type) b. Functor g => (forall a. () => g a -> g' a) -> ApF f g b -> ApF f g' b

-- | Pull out and join <tt>m</tt> layers of <tt><a>ApT</a> f m a</tt>.
joinApT :: forall m (f :: Type -> Type) a. Monad m => ApT f m a -> m (Ap f a)

-- | The free <a>Applicative</a> for a <a>Functor</a> <tt>f</tt>.
type Ap (f :: Type -> Type) = 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 = <tt>getSum</tt> . runAp_ (\_ -&gt; <tt>Sum</tt> 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 :: Type -> Type) = 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 :: forall g (t :: Type -> Type) f a. (Alternative g, Foldable t) => (forall x. () => f x -> g x) -> ApT f t a -> g a
instance GHC.Internal.Base.Alternative g => GHC.Internal.Base.Alternative (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Internal.Base.Applicative g => GHC.Internal.Base.Applicative (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Internal.Base.Applicative g => GHC.Internal.Base.Applicative (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Internal.Base.Applicative g => Data.Functor.Bind.Class.Apply (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Internal.Base.Applicative g => Data.Functor.Bind.Class.Apply (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Internal.Base.Functor g => GHC.Internal.Base.Functor (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Internal.Base.Functor g => GHC.Internal.Base.Functor (Control.Applicative.Trans.Free.ApT f g)


module Control.Comonad.Cofree.Class

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

-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
instance Control.Comonad.Cofree.Class.ComonadCofree (GHC.Internal.Data.Functor.Const.Const b) ((,) b)
instance Control.Comonad.Cofree.Class.ComonadCofree [] Data.Tree.Tree
instance Control.Comonad.Cofree.Class.ComonadCofree GHC.Internal.Maybe.Maybe GHC.Internal.Base.NonEmpty
instance Control.Comonad.Cofree.Class.ComonadCofree f w => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Env.EnvT e w)
instance Control.Comonad.Cofree.Class.ComonadCofree f w => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Monad.Trans.Identity.IdentityT w)
instance Control.Comonad.Cofree.Class.ComonadCofree f w => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Store.StoreT s w)
instance (Control.Comonad.Cofree.Class.ComonadCofree f w, GHC.Internal.Base.Monoid m) => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Traced.TracedT m 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 from 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 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 :: Type -> Type) a
(:<) :: a -> f (Cofree f a) -> Cofree (f :: Type -> Type) a
infixr 5 :<

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

-- | Remove a layer.
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

-- | Like coiter for comonadic values.
coiterW :: (Comonad w, Functor f) => (w a -> f (w a)) -> w a -> Cofree f a

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

-- | Unfold a cofree comonad from a seed, monadically.
unfoldM :: (Traversable f, Monad m) => (b -> m (a, f b)) -> b -> m (Cofree f a)
hoistCofree :: Functor f => (forall x. () => f x -> g x) -> Cofree f a -> Cofree g 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 :: forall f a (g :: Type -> Type). 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 an <tt>Lens</tt> into a <tt><a>Cofree</a> g</tt> given a
--   list of lenses into the base functor. When the input list is empty,
--   this is equivalent to <a>_extract</a>. When the input list is
--   non-empty, this composes the input lenses with <a>_unwrap</a> to walk
--   through the <tt><a>Cofree</a> g</tt> before using <a>_extract</a> to
--   get the element at the final location.
--   
--   For more on lenses see the <tt>lens</tt> package on hackage.
--   
--   <pre>
--   telescoped :: [Lens' (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]      -&gt; Lens' (<a>Cofree</a> g a) a
--   </pre>
--   
--   <pre>
--   telescoped :: [Traversal' (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)] -&gt; Traversal' (<a>Cofree</a> g a) a
--   </pre>
--   
--   <pre>
--   telescoped :: [Getter (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]     -&gt; Getter (<a>Cofree</a> g a) a
--   </pre>
--   
--   <pre>
--   telescoped :: [Fold (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]       -&gt; Fold (<a>Cofree</a> g a) a
--   </pre>
--   
--   <pre>
--   telescoped :: [Setter' (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]    -&gt; Setter' (<a>Cofree</a> g a) a
--   </pre>
telescoped :: Functor f => [(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)

-- | Construct an <tt>Lens</tt> into a <tt><a>Cofree</a> g</tt> given a
--   list of lenses into the base functor. The only difference between this
--   and <a>telescoped</a> is that <a>telescoped</a> focuses on a single
--   value, but this focuses on the entire remaining subtree. When the
--   input list is empty, this is equivalent to <a>id</a>. When the input
--   list is non-empty, this composes the input lenses with <a>_unwrap</a>
--   to walk through the <tt><a>Cofree</a> g</tt>.
--   
--   For more on lenses see the <tt>lens</tt> package on hackage.
--   
--   <pre>
--   telescoped :: [Lens' (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]      -&gt; Lens' (<a>Cofree</a> g a) (<a>Cofree</a> g a)
--   </pre>
--   
--   <pre>
--   telescoped :: [Traversal' (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)] -&gt; Traversal' (<a>Cofree</a> g a) (<a>Cofree</a> g a)
--   </pre>
--   
--   <pre>
--   telescoped :: [Getter (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]     -&gt; Getter (<a>Cofree</a> g a) (<a>Cofree</a> g a)
--   </pre>
--   
--   <pre>
--   telescoped :: [Fold (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]       -&gt; Fold (<a>Cofree</a> g a) (<a>Cofree</a> g a)
--   </pre>
--   
--   <pre>
--   telescoped :: [Setter' (g (<a>Cofree</a> g a)) (<a>Cofree</a> g a)]    -&gt; Setter' (<a>Cofree</a> g a) (<a>Cofree</a> g a)
--   </pre>
telescoped_ :: Functor f => [(Cofree g a -> f (Cofree g a)) -> g (Cofree g a) -> f (g (Cofree g a))] -> (Cofree g a -> f (Cofree g a)) -> Cofree g a -> f (Cofree g a)

-- | A <tt>Traversal'</tt> that gives access to all non-leaf <tt>a</tt>
--   elements of a <tt><a>Cofree</a> g</tt> a, where non-leaf is defined as
--   <tt>x</tt> from <tt>(x :&lt; xs)</tt> where <tt>null xs</tt> is
--   <tt>False</tt>.
--   
--   Because this doesn't give access to all values in the
--   <tt><a>Cofree</a> g</tt>, it cannot be used to change types.
--   
--   <pre>
--   shoots :: Traversable g =&gt; Traversal' (Cofree g a) a
--   </pre>
--   
--   N.B. On GHC &lt; 7.9, this is slightly less flexible, as it has to use
--   <tt>null (toList xs)</tt> instead.
shoots :: forall f (g :: Type -> Type) a. (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a)

-- | A <tt>Traversal'</tt> that gives access to all leaf <tt>a</tt>
--   elements of a <tt><a>Cofree</a> g</tt> a, where leaf is defined as
--   <tt>x</tt> from <tt>(x :&lt; xs)</tt> where <tt>null xs</tt> is
--   <tt>True</tt>.
--   
--   Because this doesn't give access to all values in the
--   <tt><a>Cofree</a> g</tt>, it cannot be used to change types.
--   
--   <pre>
--   shoots :: Traversable g =&gt; Traversal' (Cofree g a) a
--   </pre>
--   
--   N.B. On GHC &lt; 7.9, this is slightly less flexible, as it has to use
--   <tt>null (toList xs)</tt> instead.
leaves :: forall f (g :: Type -> Type) a. (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a)
instance GHC.Internal.Base.Alternative f => GHC.Internal.Base.Applicative (Control.Comonad.Cofree.Cofree f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.ComonadApply f => Control.Comonad.ComonadApply (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Base.Functor f => Control.Comonad.Comonad (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Base.Functor f => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.Env.Class.ComonadEnv e w => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Cofree.Cofree w)
instance Control.Comonad.Hoist.Class.ComonadHoist Control.Comonad.Cofree.Cofree
instance Control.Comonad.Store.Class.ComonadStore s w => Control.Comonad.Store.Class.ComonadStore s (Control.Comonad.Cofree.Cofree w)
instance Control.Comonad.Traced.Class.ComonadTraced m w => Control.Comonad.Traced.Class.ComonadTraced m (Control.Comonad.Cofree.Cofree w)
instance Control.Comonad.Trans.Class.ComonadTrans Control.Comonad.Cofree.Cofree
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Data.Data (f (Control.Comonad.Cofree.Cofree f a)), GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Control.Comonad.Cofree.Cofree f a)
instance Data.Distributive.Distributive f => Data.Distributive.Distributive (Control.Comonad.Cofree.Cofree f)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Cofree.Cofree f a)
instance GHC.Internal.Base.Functor f => Data.Functor.Extend.Extend (Control.Comonad.Cofree.Cofree f)
instance Data.Foldable1.Foldable1 f => Data.Foldable1.Foldable1 (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Comonad.Cofree.Cofree f)
instance WithIndex.FoldableWithIndex i f => WithIndex.FoldableWithIndex [i] (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Comonad.Cofree.Cofree f)
instance WithIndex.FunctorWithIndex i f => WithIndex.FunctorWithIndex [i] (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Generics.Generic1 (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Generics.Generic (Control.Comonad.Cofree.Cofree f a)
instance GHC.Internal.Base.Alternative f => GHC.Internal.Base.Monad (Control.Comonad.Cofree.Cofree f)
instance (GHC.Internal.Base.Alternative f, GHC.Internal.Control.Monad.Zip.MonadZip f) => GHC.Internal.Control.Monad.Zip.MonadZip (Control.Comonad.Cofree.Cofree f)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Cofree.Cofree f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Read1 f, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Comonad.Cofree.Cofree f a)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Comonad.Cofree.Cofree f)
instance (Data.Functor.Classes.Show1 f, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Comonad.Cofree.Cofree f a)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Comonad.Cofree.Cofree f)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Comonad.Cofree.Cofree f)
instance WithIndex.TraversableWithIndex i f => WithIndex.TraversableWithIndex [i] (Control.Comonad.Cofree.Cofree f)


-- | 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 :: Type -> Type) (w :: Type -> Type) a
CofreeT :: w (CofreeF f a (CofreeT f w a)) -> CofreeT (f :: Type -> Type) (w :: Type -> Type) a
[runCofreeT] :: CofreeT (f :: Type -> Type) (w :: Type -> Type) a -> w (CofreeF f a (CofreeT f w a))

-- | The cofree <a>Comonad</a> of a functor <tt>f</tt>.
type Cofree (f :: Type -> Type) = 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 :: forall (f :: Type -> Type) a. 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 :: forall (f :: Type -> Type) a. Cofree f a -> CofreeF f a (Cofree f a)

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

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

-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)

-- | Extract the head of the base functor
headF :: forall (f :: Type -> Type) a b. CofreeF f a b -> a

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

-- | Lift a natural transformation from <tt>f</tt> to <tt>g</tt> into a
--   comonad homomorphism from <tt><a>CofreeT</a> f w</tt> to
--   <tt><a>CofreeT</a> g w</tt>
transCofreeT :: forall g (w :: Type -> Type) f a. (Functor g, Comonad w) => (forall x. () => f x -> g x) -> CofreeT f w a -> CofreeT g w a

-- | 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 (GHC.Internal.Base.Alternative f, GHC.Internal.Base.Applicative w) => GHC.Internal.Base.Applicative (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Internal.Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Comonad.Trans.Cofree.CofreeF f)
instance GHC.Internal.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Comonad.Trans.Cofree.CofreeF f)
instance GHC.Internal.Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Comonad.Trans.Cofree.CofreeF f)
instance (GHC.Internal.Base.Functor f, Control.Comonad.Comonad w) => Control.Comonad.Comonad (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Internal.Base.Functor f, Control.Comonad.Comonad w) => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Internal.Base.Functor f, Control.Comonad.Env.Class.ComonadEnv e w) => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Internal.Base.Functor f => Control.Comonad.Hoist.Class.ComonadHoist (Control.Comonad.Trans.Cofree.CofreeT f)
instance Control.Comonad.Trans.Class.ComonadTrans (Control.Comonad.Trans.Cofree.CofreeT f)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Data.Data a, GHC.Internal.Data.Data.Data (f b), GHC.Internal.Data.Data.Data b) => GHC.Internal.Data.Data.Data (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Typeable.Internal.Typeable w, GHC.Internal.Data.Data.Data (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))), GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => Data.Functor.Classes.Eq1 (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq2 (Control.Comonad.Trans.Cofree.CofreeF f)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (f b)) => GHC.Classes.Eq (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance GHC.Classes.Eq (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Classes.Eq (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Comonad.Trans.Cofree.CofreeF f a)
instance (GHC.Internal.Data.Foldable.Foldable f, GHC.Internal.Data.Foldable.Foldable w) => GHC.Internal.Data.Foldable.Foldable (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Comonad.Trans.Cofree.CofreeF f a)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Functor w) => GHC.Internal.Base.Functor (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Internal.Generics.Generic1 (Control.Comonad.Trans.Cofree.CofreeF f a)
instance GHC.Internal.Generics.Generic (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Internal.Base.Alternative f, GHC.Internal.Base.Monad w) => GHC.Internal.Base.Monad (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Internal.Base.Alternative f => Control.Monad.Trans.Class.MonadTrans (Control.Comonad.Trans.Cofree.CofreeT f)
instance (GHC.Internal.Base.Alternative f, GHC.Internal.Control.Monad.Zip.MonadZip f, GHC.Internal.Control.Monad.Zip.MonadZip m) => GHC.Internal.Control.Monad.Zip.MonadZip (Control.Comonad.Trans.Cofree.CofreeT f m)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => Data.Functor.Classes.Ord1 (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord2 (Control.Comonad.Trans.Cofree.CofreeF f)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (f b)) => GHC.Classes.Ord (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance GHC.Classes.Ord (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Classes.Ord (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance (Data.Functor.Classes.Read1 f, GHC.Internal.Read.Read a) => Data.Functor.Classes.Read1 (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read2 (Control.Comonad.Trans.Cofree.CofreeF f)
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read (f b)) => GHC.Internal.Read.Read (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance GHC.Internal.Read.Read (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Internal.Read.Read (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance (Data.Functor.Classes.Show1 f, GHC.Internal.Show.Show a) => Data.Functor.Classes.Show1 (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show2 (Control.Comonad.Trans.Cofree.CofreeF f)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show (f b)) => GHC.Internal.Show.Show (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance GHC.Internal.Show.Show (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Internal.Show.Show (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Comonad.Trans.Cofree.CofreeF f a)
instance (GHC.Internal.Data.Traversable.Traversable f, GHC.Internal.Data.Traversable.Traversable w) => GHC.Internal.Data.Traversable.Traversable (Control.Comonad.Trans.Cofree.CofreeT f w)


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

-- | This is the coiterative comonad generated by a comonad
newtype CoiterT (w :: Type -> Type) a
CoiterT :: w (a, CoiterT w a) -> CoiterT (w :: Type -> Type) a
[runCoiterT] :: CoiterT (w :: Type -> Type) 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 :: Type -> Type) (w :: Type -> Type) | w -> f

-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
instance Control.Comonad.Comonad w => Control.Comonad.Cofree.Class.ComonadCofree GHC.Internal.Data.Functor.Identity.Identity (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Comonad w => Control.Comonad.Comonad (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Env.Class.ComonadEnv e w => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Hoist.Class.ComonadHoist Control.Comonad.Trans.Coiter.CoiterT
instance Control.Comonad.Store.Class.ComonadStore s w => Control.Comonad.Store.Class.ComonadStore s (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Traced.Class.ComonadTraced m w => Control.Comonad.Traced.Class.ComonadTraced m (Control.Comonad.Trans.Coiter.CoiterT w)
instance Control.Comonad.Trans.Class.ComonadTrans Control.Comonad.Trans.Coiter.CoiterT
instance (GHC.Internal.Data.Typeable.Internal.Typeable w, GHC.Internal.Data.Data.Data (w (a, Control.Comonad.Trans.Coiter.CoiterT w a)), GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Control.Comonad.Trans.Coiter.CoiterT w a)
instance Data.Functor.Classes.Eq1 w => Data.Functor.Classes.Eq1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance (Data.Functor.Classes.Eq1 w, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Trans.Coiter.CoiterT w a)
instance GHC.Internal.Data.Foldable.Foldable w => GHC.Internal.Data.Foldable.Foldable (Control.Comonad.Trans.Coiter.CoiterT w)
instance GHC.Internal.Base.Functor w => GHC.Internal.Base.Functor (Control.Comonad.Trans.Coiter.CoiterT w)
instance Data.Functor.Classes.Ord1 w => Data.Functor.Classes.Ord1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance (Data.Functor.Classes.Ord1 w, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Trans.Coiter.CoiterT w a)
instance Data.Functor.Classes.Read1 w => Data.Functor.Classes.Read1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance (Data.Functor.Classes.Read1 w, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Comonad.Trans.Coiter.CoiterT w a)
instance Data.Functor.Classes.Show1 w => Data.Functor.Classes.Show1 (Control.Comonad.Trans.Coiter.CoiterT w)
instance (Data.Functor.Classes.Show1 w, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Comonad.Trans.Coiter.CoiterT w a)
instance GHC.Internal.Data.Traversable.Traversable w => GHC.Internal.Data.Traversable.Traversable (Control.Comonad.Trans.Coiter.CoiterT w)


-- | 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => 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 :: forall f (m :: Type -> Type) t a. (Functor f, MonadFree f m, MonadTrans t, Monad (t m)) => f (t m a) -> t m a
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Cont.ContT r m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Except.ExceptT e m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Identity.IdentityT m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Maybe.MaybeT m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Internal.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.RWS.Lazy.RWST r w s m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Internal.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.RWS.Strict.RWST r w s m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Reader.ReaderT e m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.State.Strict.StateT s m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.State.Lazy.StateT s m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Internal.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Writer.Strict.WriterT w m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Internal.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Writer.Lazy.WriterT w m)


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

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

-- | Like <a>makeFree</a>, but does not provide type signatures. This can
--   be used to attach Haddock comments to individual arguments for each
--   generated function.
--   
--   <pre>
--   data LangF x = Output String x
--   
--   makeFree_ 'LangF
--   
--   -- | Output a string.
--   output :: MonadFree LangF m =&gt;
--             String   -- ^ String to output.
--          -&gt; m ()     -- ^ No result.
--   </pre>
--   
--   <a>makeFree_</a> must be called *before* the explicit type signatures.
makeFree_ :: Name -> Q [Dec]

-- | <tt>$(<a>makeFreeCon</a> 'Con)</tt> provides free monadic action for a
--   data constructor <tt>Con</tt>. Note that you can attach Haddock
--   comment to the generated function by placing it before the top-level
--   invocation of <a>makeFreeCon</a>:
--   
--   <pre>
--   -- | Output a string.
--   makeFreeCon 'Output
--   </pre>
makeFreeCon :: Name -> Q [Dec]

-- | Like <a>makeFreeCon</a>, but does not provide a type signature. This
--   can be used to attach Haddock comments to individual arguments.
--   
--   <pre>
--   data LangF x = Output String x
--   
--   makeFreeCon_ 'Output
--   
--   -- | Output a string.
--   output :: MonadFree LangF m =&gt;
--             String   -- ^ String to output.
--          -&gt; m ()     -- ^ No result.
--   </pre>
--   
--   <a>makeFreeCon_</a> must be called *before* the explicit type
--   signature.
makeFreeCon_ :: Name -> Q [Dec]
instance GHC.Internal.Show.Show Control.Monad.Free.TH.Arg


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

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

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

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

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

-- | Evaluates the first layer out of a free monad value.
runFree :: forall (f :: Type -> Type) a. 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 :: forall f (m :: Type -> Type) t a. (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>Functor</a> m, <a>Functor</a> f) =&gt; (m ~&gt; n) -&gt; <a>FreeT</a> f m ~&gt; <a>FreeT</a> f n
--   </pre>
hoistFreeT :: forall m (f :: Type -> Type) n b. (Functor m, Functor f) => (forall a. () => m a -> n a) -> FreeT f m b -> FreeT f n b

-- | The very definition of a free monad transformer is that given a
--   natural transformation you get a monad transformer homomorphism.
foldFreeT :: forall t (m :: Type -> Type) f a. (MonadTrans t, Monad (t m), Monad m) => (forall (n :: Type -> Type) x. Monad n => f x -> t n x) -> FreeT f m a -> t m a

-- | 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 m</tt>
transFreeT :: forall (m :: Type -> Type) g f b. (Monad m, Functor g) => (forall a. () => f a -> g a) -> FreeT f m b -> FreeT g m b

-- | Pull out and join <tt>m</tt> layers of <tt><a>FreeT</a> f m a</tt>.
joinFreeT :: forall m (f :: Type -> Type) a. (Monad m, Traversable f) => FreeT f m a -> m (Free f a)

-- | 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 :: forall (f :: Type -> Type) (m :: Type -> Type) a. (Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a)

-- | <tt>partialIterT n phi m</tt> interprets first <tt>n</tt> layers of
--   <tt>m</tt> using <tt>phi</tt>. This is sort of the opposite for
--   <tt><a>cutoff</a></tt>.
--   
--   Some examples (<tt>n ≥ 0</tt>):
--   
--   <pre>
--   <a>partialIterT</a> 0 _ m              ≡ m
--   <a>partialIterT</a> (n+1) phi <a>.</a> <a>return</a> ≡ <a>return</a>
--   <a>partialIterT</a> (n+1) phi <a>.</a> <a>lift</a>   ≡ <a>lift</a>
--   <a>partialIterT</a> (n+1) phi <a>.</a> <a>wrap</a>   ≡ <a>join</a> . <a>lift</a> . phi
--   </pre>
partialIterT :: Monad m => Integer -> (forall a. () => f a -> m a) -> FreeT f m b -> FreeT f m b

-- | <tt>intersperseT f m</tt> inserts a layer <tt>f</tt> between every two
--   layers in <tt>m</tt>.
--   
--   <pre>
--   <a>intersperseT</a> f <a>.</a> <a>return</a> ≡ <a>return</a>
--   <a>intersperseT</a> f <a>.</a> <a>lift</a>   ≡ <a>lift</a>
--   <a>intersperseT</a> f <a>.</a> <a>wrap</a>   ≡ <a>wrap</a> <a>.</a> <a>fmap</a> (<a>iterTM</a> (<a>wrap</a> <a>.</a> (<a>&lt;$</a> f) <a>.</a> <a>wrap</a>))
--   </pre>
intersperseT :: forall (m :: Type -> Type) f a b. (Monad m, Functor f) => f a -> FreeT f m b -> FreeT f m b

-- | <tt>intercalateT f m</tt> inserts a layer <tt>f</tt> between every two
--   layers in <tt>m</tt> and then retracts the result.
--   
--   <pre>
--   <a>intercalateT</a> f ≡ <a>retractT</a> . <a>intersperseT</a> f
--   </pre>
intercalateT :: forall (m :: Type -> Type) t a b. (Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b

-- | Tear down a free monad transformer using Monad instance for <tt>t
--   m</tt>.
retractT :: forall t (m :: Type -> Type) a. (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.MonadPlus m) => GHC.Internal.Base.Alternative (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => GHC.Internal.Base.Applicative (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Internal.Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Monad.Trans.Free.FreeF f)
instance GHC.Internal.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Internal.Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Typeable.Internal.Typeable b, GHC.Internal.Data.Data.Data a, GHC.Internal.Data.Data.Data (f b)) => GHC.Internal.Data.Data.Data (Control.Monad.Trans.Free.FreeF f a b)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.FreeF f a)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.FreeT f m)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq2 (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (f b)) => GHC.Classes.Eq (Control.Monad.Trans.Free.FreeF f a b)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.FreeT f m a)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Trans.Free.FreeF f a)
instance (GHC.Internal.Data.Foldable.Foldable m, GHC.Internal.Data.Foldable.Foldable f) => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Monad.Trans.Free.FreeF f a)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Functor m) => GHC.Internal.Base.Functor (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Internal.Generics.Generic1 (Control.Monad.Trans.Free.FreeF f a)
instance GHC.Internal.Generics.Generic (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Internal.Base.Functor f, Control.Monad.Base.MonadBase b m) => Control.Monad.Base.MonadBase b (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Control.Monad.Fail.MonadFail m) => GHC.Internal.Control.Monad.Fail.MonadFail (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => GHC.Internal.Base.Monad (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Control.Monad.IO.Class.MonadIO m) => GHC.Internal.Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.MonadPlus m) => GHC.Internal.Base.MonadPlus (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Reader.Class.MonadReader r m) => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Catch.MonadThrow m) => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Internal.Base.Functor f => Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.FreeT f)
instance (GHC.Internal.Base.Functor f, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.FreeF f a)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.FreeT f m)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord2 (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (f b)) => GHC.Classes.Ord (Control.Monad.Trans.Free.FreeF f a b)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.FreeT f m a)
instance (Data.Functor.Classes.Read1 f, GHC.Internal.Read.Read a) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.FreeF f a)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.FreeT f m)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read2 (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read (f b)) => GHC.Internal.Read.Read (Control.Monad.Trans.Free.FreeF f a b)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Monad.Trans.Free.FreeT f m a)
instance (Data.Functor.Classes.Show1 f, GHC.Internal.Show.Show a) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.FreeF f a)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.FreeT f m)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show2 (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show (f b)) => GHC.Internal.Show.Show (Control.Monad.Trans.Free.FreeF f a b)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Monad.Trans.Free.FreeT f m a)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Trans.Free.FreeF f a)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Data.Traversable.Traversable m, GHC.Internal.Data.Traversable.Traversable f) => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Trans.Free.FreeT f m)


-- | 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => 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>.
--   
--   <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 :: Type -> Type) a
Pure :: a -> Free (f :: Type -> Type) a
Free :: f (Free f a) -> Free (f :: Type -> Type) 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 <a>iter</a> for applicative values.
iterA :: (Applicative p, Functor f) => (f (p a) -> p a) -> Free f a -> p a

-- | Like <a>iter</a> 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><a>Free</a> f</tt> to <tt><a>Free</a>
--   g</tt>.
hoistFree :: Functor g => (forall a. () => f a -> g a) -> Free f b -> Free g b

-- | The very definition of a free monad is that given a natural
--   transformation you get a monad homomorphism.
foldFree :: Monad m => (forall x. () => f x -> m x) -> Free f a -> m a

-- | 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 :: forall (f :: Type -> Type) (m :: Type -> Type) a. (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 <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 :: forall (f :: Type -> Type) a. Functor f => Integer -> Free f a -> Free f (Maybe a)

-- | Unfold a free monad from a seed.
unfold :: Functor f => (b -> Either a (f b)) -> b -> Free f a

-- | Unfold a free monad from a seed, monadically.
unfoldM :: (Traversable f, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f 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 :: forall (f :: Type -> Type) m a p. (Choice p, Applicative m) => p a (m a) -> p (Free f a) (m (Free f a))

-- | This is <tt>Prism (Free f a) (Free g a) (f (Free f a)) (g (Free g
--   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 :: forall f g m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (g (Free g a))) -> p (Free f a) (m (Free g a))
instance GHC.Internal.Base.Alternative v => GHC.Internal.Base.Alternative (Control.Monad.Free.Free v)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Applicative (Control.Monad.Free.Free f)
instance GHC.Internal.Base.Functor f => Data.Functor.Bind.Class.Apply (Control.Monad.Free.Free f)
instance GHC.Internal.Base.Functor f => Data.Functor.Bind.Class.Bind (Control.Monad.Free.Free f)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Data.Data (f (Control.Monad.Free.Free f a)), GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Free.Free f a)
instance Data.Foldable1.Foldable1 f => Data.Foldable1.Foldable1 (Control.Monad.Free.Free f)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Free.Free f)
instance WithIndex.FoldableWithIndex i f => WithIndex.FoldableWithIndex [i] (Control.Monad.Free.Free f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Monad.Free.Free f)
instance WithIndex.FunctorWithIndex i f => WithIndex.FunctorWithIndex [i] (Control.Monad.Free.Free f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Generics.Generic1 (Control.Monad.Free.Free f)
instance GHC.Internal.Generics.Generic (Control.Monad.Free.Free f a)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Free m)
instance Control.Monad.Error.Class.MonadError e m => Control.Monad.Error.Class.MonadError e (Control.Monad.Free.Free m)
instance GHC.Internal.Base.Functor f => GHC.Internal.Control.Monad.Fix.MonadFix (Control.Monad.Free.Free f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Monad (Control.Monad.Free.Free f)
instance GHC.Internal.Base.Functor f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Free f)
instance GHC.Internal.Base.MonadPlus v => GHC.Internal.Base.MonadPlus (Control.Monad.Free.Free v)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Free m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Free m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Free
instance Control.Monad.Writer.Class.MonadWriter e m => Control.Monad.Writer.Class.MonadWriter e (Control.Monad.Free.Free m)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Read1 f, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Monad.Free.Free f a)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Monad.Free.Free f)
instance (Data.Functor.Classes.Show1 f, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Monad.Free.Free f a)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Free f)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Free.Free f)
instance WithIndex.TraversableWithIndex i f => WithIndex.TraversableWithIndex [i] (Control.Monad.Free.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>https://ekmett.github.io/reader/2011/free-monads-for-less-2/</a>
newtype F (f :: Type -> Type) a
F :: (forall r. () => (a -> r) -> (f r -> r) -> r) -> F (f :: Type -> Type) a
[runF] :: F (f :: Type -> Type) 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 :: forall (f :: Type -> Type) a. Functor f => (forall (m :: Type -> Type). MonadFree f m => m a) -> Free f a

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

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

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

-- | Generate a Church-encoded free monad from a <a>Free</a> monad.
toF :: forall (f :: Type -> Type) a. 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

-- | The very definition of a free monad is that given a natural
--   transformation you get a monad homomorphism.
foldF :: Monad m => (forall x. () => f x -> m x) -> 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => 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

-- | 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 (<tt>n ≥ 0</tt>):
--   
--   <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 <tt><a>retract</a> . <a>cutoff</a> n</tt> is always
--   terminating, provided each of the steps in the iteration is
--   terminating.
cutoff :: forall (f :: Type -> Type) a. Functor f => Integer -> F f a -> F f (Maybe a)
instance GHC.Internal.Base.Alternative f => GHC.Internal.Base.Alternative (Control.Monad.Free.Church.F f)
instance GHC.Internal.Base.Applicative (Control.Monad.Free.Church.F f)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Free.Church.F f)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Free.Church.F f)
instance Data.Foldable1.Foldable1 f => Data.Foldable1.Foldable1 (Control.Monad.Free.Church.F f)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Free.Church.F f)
instance GHC.Internal.Base.Functor (Control.Monad.Free.Church.F f)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Church.F m)
instance GHC.Internal.Base.Monad (Control.Monad.Free.Church.F f)
instance GHC.Internal.Control.Monad.Fix.MonadFix (Control.Monad.Free.Church.F f)
instance GHC.Internal.Base.Functor f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Church.F f)
instance GHC.Internal.Base.MonadPlus f => GHC.Internal.Base.MonadPlus (Control.Monad.Free.Church.F f)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Church.F m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Church.F m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Church.F
instance Control.Monad.Writer.Class.MonadWriter w m => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Free.Church.F m)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Church.F f)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Free.Church.F f)


-- | Given an applicative, the free monad transformer.
module Control.Monad.Trans.Free.Ap

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

-- | The "free monad transformer" for an applicative <tt>f</tt>
newtype FreeT (f :: Type -> Type) (m :: Type -> Type) a
FreeT :: m (FreeF f a (FreeT f m a)) -> FreeT (f :: Type -> Type) (m :: Type -> Type) a
[runFreeT] :: FreeT (f :: Type -> Type) (m :: Type -> Type) a -> m (FreeF f a (FreeT f m a))

-- | The "free monad" for an applicative <tt>f</tt>.
type Free (f :: Type -> Type) = FreeT f Identity

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

-- | Evaluates the first layer out of a free monad value.
runFree :: forall (f :: Type -> Type) a. 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

-- | Given an applicative homomorphism from <tt>f (m a)</tt> to <tt>m
--   a</tt>, tear down a free monad transformer using iteration.
iterT :: (Applicative f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a

-- | Given an applicative homomorphism from <tt>f (t m a)</tt> to <tt>t m
--   a</tt>, tear down a free monad transformer using iteration over a
--   transformer.
iterTM :: forall f (m :: Type -> Type) t a. (Applicative 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>Functor</a> m, <a>Applicative</a> f) =&gt; (m ~&gt; n) -&gt; <a>FreeT</a> f m ~&gt; <a>FreeT</a> f n
--   </pre>
hoistFreeT :: forall m (f :: Type -> Type) n b. (Functor m, Applicative f) => (forall a. () => m a -> n a) -> FreeT f m b -> FreeT f n b

-- | Lift an applicative homomorphism 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 m</tt>
transFreeT :: forall (m :: Type -> Type) g f b. (Monad m, Applicative g) => (forall a. () => f a -> g a) -> FreeT f m b -> FreeT g m b

-- | Pull out and join <tt>m</tt> layers of <tt><a>FreeT</a> f m a</tt>.
joinFreeT :: forall m (f :: Type -> Type) a. (Monad m, Traversable f, Applicative f) => FreeT f m a -> m (Free f a)

-- | 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 :: forall (f :: Type -> Type) (m :: Type -> Type) a. (Applicative f, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a)

-- | <tt>partialIterT n phi m</tt> interprets first <tt>n</tt> layers of
--   <tt>m</tt> using <tt>phi</tt>. This is sort of the opposite for
--   <tt><a>cutoff</a></tt>.
--   
--   Some examples (<tt>n ≥ 0</tt>):
--   
--   <pre>
--   <a>partialIterT</a> 0 _ m              ≡ m
--   <a>partialIterT</a> (n+1) phi <a>.</a> <a>return</a> ≡ <a>return</a>
--   <a>partialIterT</a> (n+1) phi <a>.</a> <a>lift</a>   ≡ <a>lift</a>
--   <a>partialIterT</a> (n+1) phi <a>.</a> <a>wrap</a>   ≡ <a>join</a> . <a>lift</a> . phi
--   </pre>
partialIterT :: Monad m => Integer -> (forall a. () => f a -> m a) -> FreeT f m b -> FreeT f m b

-- | <tt>intersperseT f m</tt> inserts a layer <tt>f</tt> between every two
--   layers in <tt>m</tt>.
--   
--   <pre>
--   <a>intersperseT</a> f <a>.</a> <a>return</a> ≡ <a>return</a>
--   <a>intersperseT</a> f <a>.</a> <a>lift</a>   ≡ <a>lift</a>
--   <a>intersperseT</a> f <a>.</a> <a>wrap</a>   ≡ <a>wrap</a> <a>.</a> <a>fmap</a> (<a>iterTM</a> (<a>wrap</a> <a>.</a> (<a>&lt;$</a> f) <a>.</a> <a>wrap</a>))
--   </pre>
intersperseT :: forall (m :: Type -> Type) f a b. (Monad m, Applicative f) => f a -> FreeT f m b -> FreeT f m b

-- | <tt>intercalateT f m</tt> inserts a layer <tt>f</tt> between every two
--   layers in <tt>m</tt> and then retracts the result.
--   
--   <pre>
--   <a>intercalateT</a> f ≡ <a>retractT</a> . <a>intersperseT</a> f
--   </pre>
intercalateT :: forall (m :: Type -> Type) t a b. (Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b

-- | Tear down a free monad transformer using Monad instance for <tt>t
--   m</tt>.
retractT :: forall t (m :: Type -> Type) a. (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m 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

-- | Given an applicative homomorphism from <tt>f</tt> to <a>Identity</a>,
--   tear down a <a>Free</a> <a>Monad</a> using iteration.
iter :: Applicative f => (f a -> a) -> Free f a -> a

-- | Like <a>iter</a> for monadic values.
iterM :: (Applicative 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Base.MonadPlus m) => GHC.Internal.Base.Alternative (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Base.Applicative m) => GHC.Internal.Base.Applicative (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Bind.Class.Apply f, Data.Functor.Bind.Class.Apply m) => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.Ap.FreeT f m)
instance GHC.Internal.Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Monad.Trans.Free.Ap.FreeF f)
instance GHC.Internal.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Monad.Trans.Free.Ap.FreeF f)
instance (Data.Functor.Bind.Class.Apply f, Data.Functor.Bind.Class.Apply m, GHC.Internal.Base.Monad m) => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.Ap.FreeT f m)
instance GHC.Internal.Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Monad.Trans.Free.Ap.FreeF f)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Typeable.Internal.Typeable b, GHC.Internal.Data.Data.Data a, GHC.Internal.Data.Data.Data (f b)) => GHC.Internal.Data.Data.Data (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Typeable.Internal.Typeable m, GHC.Internal.Data.Data.Data (m (Control.Monad.Trans.Free.Ap.FreeF f a (Control.Monad.Trans.Free.Ap.FreeT f m a))), GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (f b)) => GHC.Classes.Eq (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (GHC.Internal.Data.Foldable.Foldable m, GHC.Internal.Data.Foldable.Foldable f) => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Trans.Free.Ap.FreeT f m)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Functor m) => GHC.Internal.Base.Functor (Control.Monad.Trans.Free.Ap.FreeT f m)
instance GHC.Internal.Generics.Generic1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance GHC.Internal.Generics.Generic (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (GHC.Internal.Base.Applicative f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Control.Monad.Fail.MonadFail m) => GHC.Internal.Control.Monad.Fail.MonadFail (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Base.Monad m) => GHC.Internal.Base.Monad (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Base.Monad m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Control.Monad.IO.Class.MonadIO m) => GHC.Internal.Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, GHC.Internal.Base.MonadPlus m) => GHC.Internal.Base.MonadPlus (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, Control.Monad.Reader.Class.MonadReader r m) => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (GHC.Internal.Base.Applicative f, Control.Monad.Catch.MonadThrow m) => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.Ap.FreeT f m)
instance GHC.Internal.Base.Applicative f => Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.Ap.FreeT f)
instance (GHC.Internal.Base.Applicative f, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.Ap.FreeT f m)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (f b)) => GHC.Classes.Ord (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (Data.Functor.Classes.Read1 f, GHC.Internal.Read.Read a) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m) => Data.Functor.Classes.Read1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (GHC.Internal.Read.Read a, GHC.Internal.Read.Read (f b)) => GHC.Internal.Read.Read (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (Data.Functor.Classes.Read1 f, Data.Functor.Classes.Read1 m, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance (Data.Functor.Classes.Show1 f, GHC.Internal.Show.Show a) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m) => Data.Functor.Classes.Show1 (Control.Monad.Trans.Free.Ap.FreeT f m)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show2 (Control.Monad.Trans.Free.Ap.FreeF f)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show (f b)) => GHC.Internal.Show.Show (Control.Monad.Trans.Free.Ap.FreeF f a b)
instance (Data.Functor.Classes.Show1 f, Data.Functor.Classes.Show1 m, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Monad.Trans.Free.Ap.FreeT f m a)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Trans.Free.Ap.FreeF f a)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Data.Traversable.Traversable m, GHC.Internal.Data.Traversable.Traversable f) => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Trans.Free.Ap.FreeT f m)


-- | "Applicative Effects in Free Monads"
--   
--   Often times, the <tt>(\&lt;*\&gt;)</tt> operator can be more efficient
--   than <tt>ap</tt>. Conventional free monads don't provide any means of
--   modeling this. The free monad can be modified to make use of an
--   underlying applicative. But it does require some laws, or else the
--   <tt>(\&lt;*\&gt;)</tt> = <tt>ap</tt> law is broken. When interpreting
--   this free monad with <a>foldFree</a>, the natural transformation must
--   be an applicative homomorphism. An applicative homomorphism <tt>hm ::
--   (Applicative f, Applicative g) =&gt; f x -&gt; g x</tt> will satisfy
--   these laws.
--   
--   <ul>
--   <li><pre>hm (pure a) = pure a</pre></li>
--   <li><pre>hm (f &lt;*&gt; a) = hm f &lt;*&gt; hm a</pre></li>
--   </ul>
--   
--   This is based on the "Applicative Effects in Free Monads" series of
--   articles by Will Fancher
--   
--   <ul>
--   <li><a>Applicative Effects in Free Monads</a></li>
--   <li><a>More on Applicative Effects in Free Monads</a></li>
--   </ul>
module Control.Monad.Free.Ap

-- | 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a

-- | A free monad given an applicative
data Free (f :: Type -> Type) a
Pure :: a -> Free (f :: Type -> Type) a
Free :: f (Free f a) -> Free (f :: Type -> Type) 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

-- | Given an applicative homomorphism from <tt>f</tt> to
--   <tt>Identity</tt>, tear down a <a>Free</a> <a>Monad</a> using
--   iteration.
iter :: Applicative f => (f a -> a) -> Free f a -> a

-- | Like <a>iter</a> for applicative values.
iterA :: (Applicative p, Applicative f) => (f (p a) -> p a) -> Free f a -> p a

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

-- | Lift an applicative homomorphism from <tt>f</tt> to <tt>g</tt> into a
--   monad homomorphism from <tt><a>Free</a> f</tt> to <tt><a>Free</a>
--   g</tt>.
hoistFree :: (Applicative f, Applicative g) => (forall a. () => f a -> g a) -> Free f b -> Free g b

-- | Given an applicative homomorphism, you get a monad homomorphism.
foldFree :: (Applicative f, Monad m) => (forall x. () => f x -> m x) -> Free f a -> m a

-- | Convert a <a>Free</a> monad from <a>Control.Monad.Free.Ap</a> to a
--   <a>FreeT</a> monad from <a>Control.Monad.Trans.Free.Ap</a>. WARNING:
--   This assumes that <a>liftF</a> is an applicative homomorphism.
toFreeT :: forall (f :: Type -> Type) (m :: Type -> Type) a. (Applicative 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 :: forall (f :: Type -> Type) a. Applicative f => Integer -> Free f a -> Free f (Maybe a)

-- | Unfold a free monad from a seed.
unfold :: Applicative f => (b -> Either a (f b)) -> b -> Free f a

-- | Unfold a free monad from a seed, monadically.
unfoldM :: (Applicative f, Traversable f, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f 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 :: forall (f :: Type -> Type) m a p. (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 :: forall f m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))
instance GHC.Internal.Base.Alternative v => GHC.Internal.Base.Alternative (Control.Monad.Free.Ap.Free v)
instance GHC.Internal.Base.Applicative f => GHC.Internal.Base.Applicative (Control.Monad.Free.Ap.Free f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Apply (Control.Monad.Free.Ap.Free f)
instance Data.Functor.Bind.Class.Apply f => Data.Functor.Bind.Class.Bind (Control.Monad.Free.Ap.Free f)
instance (GHC.Internal.Data.Typeable.Internal.Typeable f, GHC.Internal.Data.Data.Data a, GHC.Internal.Data.Data.Data (f (Control.Monad.Free.Ap.Free f a))) => GHC.Internal.Data.Data.Data (Control.Monad.Free.Ap.Free f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Eq1 f, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Free.Ap.Free f a)
instance Data.Foldable1.Foldable1 f => Data.Foldable1.Foldable1 (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Data.Foldable.Foldable f => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Base.Functor f => GHC.Internal.Generics.Generic1 (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Generics.Generic (Control.Monad.Free.Ap.Free f a)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Ap.Free m)
instance Control.Monad.Error.Class.MonadError e m => Control.Monad.Error.Class.MonadError e (Control.Monad.Free.Ap.Free m)
instance GHC.Internal.Base.Applicative f => GHC.Internal.Control.Monad.Fix.MonadFix (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Base.Applicative f => GHC.Internal.Base.Monad (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Base.Applicative f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Base.MonadPlus v => GHC.Internal.Base.MonadPlus (Control.Monad.Free.Ap.Free v)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Ap.Free m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Ap.Free m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Ap.Free
instance Control.Monad.Writer.Class.MonadWriter e m => Control.Monad.Writer.Class.MonadWriter e (Control.Monad.Free.Ap.Free m)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Ord1 f, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Free.Ap.Free f a)
instance Data.Functor.Classes.Read1 f => Data.Functor.Classes.Read1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Read1 f, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Monad.Free.Ap.Free f a)
instance Data.Functor.Classes.Show1 f => Data.Functor.Classes.Show1 (Control.Monad.Free.Ap.Free f)
instance (Data.Functor.Classes.Show1 f, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Monad.Free.Ap.Free f a)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Ap.Free f)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Free.Ap.Free 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 :: Type -> Type) (m :: Type -> Type) a
FT :: (forall r. () => (a -> m r) -> (forall x. () => (x -> m r) -> f x -> m r) -> m r) -> FT (f :: Type -> Type) (m :: Type -> Type) a
[runFT] :: FT (f :: Type -> Type) (m :: Type -> Type) a -> forall r. () => (a -> m r) -> (forall x. () => (x -> m r) -> f x -> m r) -> m r

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

-- | Wrap a Church-encoding of a "free monad" as the free monad for a
--   functor.
free :: (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

-- | Improve the asymptotic performance of code that builds a free monad
--   transformer with only binds and returns by using <a>FT</a> behind the
--   scenes.
--   
--   Similar to <a>improve</a>.
improveT :: forall (f :: Type -> Type) (m :: Type -> Type) a. (Functor f, Monad m) => (forall (t :: (Type -> Type) -> Type -> Type). MonadFree f (t m) => t m a) -> FreeT f m a

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

-- | Convert to a <a>FreeT</a> free monad representation.
fromFT :: forall (m :: Type -> Type) (f :: Type -> Type) a. (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 :: forall f (m :: Type -> Type) t a. (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 :: forall m n (f :: Type -> Type) b. (Monad m, Monad n) => (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 :: forall f g (m :: Type -> Type) b. (forall a. () => f a -> g a) -> FT f m b -> FT g m b

-- | Pull out and join <tt>m</tt> layers of <tt><a>FreeT</a> f m a</tt>.
joinFT :: forall m (f :: Type -> Type) a. (Monad m, Traversable f) => FT f m a -> m (F f 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 :: forall (f :: Type -> Type) (m :: Type -> Type) a. (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>https://ekmett.github.io/reader/2011/free-monads-for-less/</a>
--   <a>https://ekmett.github.io/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 :: forall (f :: Type -> Type) a. Functor f => (forall (m :: Type -> Type). MonadFree f m => m a) -> Free f a

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

-- | Generate a Church-encoded free monad from a <a>Free</a> monad.
toF :: forall (f :: Type -> Type) a. 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 :: Monad f => F f a -> f a

-- | Tear down a free monad transformer using iteration over a transformer.
retractT :: forall t (m :: Type -> Type) a. (MonadTrans t, Monad (t m), Monad m) => FT (t m) m a -> t m 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => 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 GHC.Internal.Base.Alternative m => GHC.Internal.Base.Alternative (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Internal.Base.Applicative (Control.Monad.Trans.Free.Church.FT f m)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.Church.FT f m)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m, Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m) => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m, Data.Functor.Classes.Eq1 f, Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.Church.FT f m a)
instance (GHC.Internal.Data.Foldable.Foldable f, GHC.Internal.Data.Foldable.Foldable m, GHC.Internal.Base.Monad m) => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Internal.Base.Functor (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Internal.Base.Functor f, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Internal.Base.Monad (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Internal.Control.Monad.Fail.MonadFail m => GHC.Internal.Control.Monad.Fail.MonadFail (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Internal.Control.Monad.IO.Class.MonadIO m => GHC.Internal.Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Internal.Base.MonadPlus m => GHC.Internal.Base.MonadPlus (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Reader.Class.MonadReader r m => Control.Monad.Reader.Class.MonadReader r (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Catch.MonadThrow m => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.Church.FT f)
instance (GHC.Internal.Base.Functor f, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m, Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m) => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m, Data.Functor.Classes.Ord1 f, Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.Church.FT f m a)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Data.Traversable.Traversable m, GHC.Internal.Data.Traversable.Traversable f) => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Trans.Free.Church.FT f 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 :: Type -> Type) a
IterT :: m (Either a (IterT m a)) -> IterT (m :: Type -> Type) a
[runIterT] :: IterT (m :: Type -> Type) 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 :: forall (f :: Type -> Type) m a. (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 :: forall (m :: Type -> Type) a. 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 :: forall (m :: Type -> Type) a. Monad m => Integer -> IterT m a -> IterT m (Maybe a)

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

-- | Repeatedly run a computation until it produces a <a>Just</a> value.
--   This can be useful when paired with a monad that has side effects.
--   
--   For example, we may have <tt>genId :: IO (Maybe Id)</tt> that uses a
--   random number generator to allocate ids, but fails if it finds a
--   collision. We can repeatedly run this with
--   
--   <pre>
--   <a>retract</a> (<a>untilJust</a> genId) :: IO Id
--   </pre>
untilJust :: Monad m => m (Maybe a) -> IterT 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 :: forall (m :: Type -> Type) a. 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_ :: forall (m :: Type -> Type) a. 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 :: Type -> Type) (m :: Type -> Type) | m -> f

-- | Add a layer.
--   
--   <pre>
--   wrap (fmap f x) ≡ wrap (fmap return x) &gt;&gt;= f
--   </pre>
wrap :: MonadFree f m => f (m a) -> m a
($dmwrap) :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Alternative (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Applicative (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Internal.Data.Typeable.Internal.Typeable m, GHC.Internal.Data.Data.Data (m (GHC.Internal.Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))), GHC.Internal.Data.Data.Data a) => GHC.Internal.Data.Data.Data (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Eq1 m => Data.Functor.Classes.Eq1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Eq1 m, GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Iter.IterT m a)
instance Data.Foldable1.Foldable1 m => Data.Foldable1.Foldable1 (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Data.Foldable.Foldable m => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Functor (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Catch.MonadCatch m => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Error.Class.MonadError e m => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Control.Monad.Fail.MonadFail (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Control.Monad.Fix.MonadFix m => GHC.Internal.Control.Monad.Fix.MonadFix (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => Control.Monad.Free.Class.MonadFree GHC.Internal.Data.Functor.Identity.Identity (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Control.Monad.IO.Class.MonadIO m => GHC.Internal.Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Monad (Control.Monad.Trans.Iter.IterT m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.MonadPlus (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Catch.MonadThrow m => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Trans.Iter.IterT
instance Control.Monad.Writer.Class.MonadWriter w m => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Base.Semigroup a, GHC.Internal.Base.Monoid a) => GHC.Internal.Base.Monoid (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Ord1 m => Data.Functor.Classes.Ord1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Ord1 m, GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Read1 m => Data.Functor.Classes.Read1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Read1 m, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Control.Monad.Trans.Iter.IterT m a)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Base.Semigroup a) => GHC.Internal.Base.Semigroup (Control.Monad.Trans.Iter.IterT m a)
instance Data.Functor.Classes.Show1 m => Data.Functor.Classes.Show1 (Control.Monad.Trans.Iter.IterT m)
instance (Data.Functor.Classes.Show1 m, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Control.Monad.Trans.Iter.IterT m a)
instance (GHC.Internal.Base.Monad m, Data.Semigroup.Traversable.Class.Traversable1 m) => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Data.Traversable.Traversable m) => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Trans.Iter.IterT m)
