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

-- | Monads for free
--   
--   Free monads are useful for many tree-like structures and domain
--   specific languages.
--   
--   If f is a Functor then the free Monad on
--   f is the type of trees whose nodes are labeled with the
--   constructors of f. The word "free" is used in the sense of
--   "unrestricted" rather than "zero-cost": Free f makes no
--   constraining assumptions beyond those given by f and the
--   definition of Monad. 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 Functor that controls its branching factor.
--   
--   More information on free monads, including examples, can be found in
--   the following blog posts:
--   http://comonad.com/reader/2008/monads-for-free/
--   http://comonad.com/reader/2011/free-monads-for-less/
@package free
@version 4.12.4

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

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

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

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

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

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

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

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: MonadFree f m => f (m a) -> m a

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: (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.
--   
--   Note: that this is the default implementation for wrap
--   for MonadFree f (t m).
wrapT :: (Functor f, MonadFree f m, MonadTrans t, Monad (t m)) => f (t m a) -> t m a
instance (GHC.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.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.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.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.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Writer.Lazy.WriterT w m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Writer.Strict.WriterT w m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.RWS.Strict.RWST r w s m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, GHC.Base.Monoid w) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.RWS.Lazy.RWST r w s m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Maybe.MaybeT m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Identity.IdentityT m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.List.ListT m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m, Control.Monad.Trans.Error.Error e) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Error.ErrorT e m)
instance (GHC.Base.Functor f, Control.Monad.Free.Class.MonadFree f m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Except.ExceptT e m)

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

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

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

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

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

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

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

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

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

-- | Lift a monad homomorphism from m to n into a monad
--   homomorphism from FreeT f m to FreeT f
--   n
--   
--   
--   hoistFreeT :: (Monad m, Functor f) => (m ~> n) -> FreeT f m ~> FreeT f n
--   
hoistFreeT :: (Monad m, Functor f) => (forall a. m a -> n a) -> FreeT f m b -> FreeT f n b

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

-- | Pull out and join m layers of FreeT f m a.
joinFreeT :: (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
--   0 or less, no computation nor monadic effects will take
--   place.
--   
--   Some examples (n ≥ 0):
--   
--   
--   cutoff 0     _        ≡ return Nothing
--   cutoff (n+1) . return ≡ return . Just
--   cutoff (n+1) . lift   ≡ lift . liftM Just
--   cutoff (n+1) . wrap   ≡ wrap . fmap (cutoff n)
--   
--   
--   Calling retract . cutoff n is always
--   terminating, provided each of the steps in the iteration is
--   terminating.
cutoff :: (Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m (Maybe a)

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

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

-- | intercalateT f m inserts a layer f between every two
--   layers in m and then retracts the result.
--   
--   
--   intercalateT f ≡ retractT . intersperseT f
--   
intercalateT :: (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 t
--   m.
retractT :: (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m a

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

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

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

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

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: MonadFree f m => f (m a) -> m a

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance (GHC.Read.Read (f b), GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Show.Show (f b), GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Classes.Ord (f b), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Trans.Free.FreeF f a b)
instance (GHC.Classes.Eq (f b), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Trans.Free.FreeF f a b)
instance GHC.Classes.Eq (m (Control.Monad.Trans.Free.FreeF f a (Control.Monad.Trans.Free.FreeT f m a))) => GHC.Classes.Eq (Control.Monad.Trans.Free.FreeT f m a)
instance GHC.Classes.Ord (m (Control.Monad.Trans.Free.FreeF f a (Control.Monad.Trans.Free.FreeT f m a))) => GHC.Classes.Ord (Control.Monad.Trans.Free.FreeT f m a)
instance Prelude.Extras.Show1 f => Prelude.Extras.Show2 (Control.Monad.Trans.Free.FreeF f)
instance (Prelude.Extras.Show1 f, GHC.Show.Show a) => Prelude.Extras.Show1 (Control.Monad.Trans.Free.FreeF f a)
instance Prelude.Extras.Read1 f => Prelude.Extras.Read2 (Control.Monad.Trans.Free.FreeF f)
instance (Prelude.Extras.Read1 f, GHC.Read.Read a) => Prelude.Extras.Read1 (Control.Monad.Trans.Free.FreeF f a)
instance Prelude.Extras.Eq1 f => Prelude.Extras.Eq2 (Control.Monad.Trans.Free.FreeF f)
instance (Prelude.Extras.Eq1 f, GHC.Classes.Eq a) => Prelude.Extras.Eq1 (Control.Monad.Trans.Free.FreeF f a)
instance Prelude.Extras.Ord1 f => Prelude.Extras.Ord2 (Control.Monad.Trans.Free.FreeF f)
instance (Prelude.Extras.Ord1 f, GHC.Classes.Ord a) => Prelude.Extras.Ord1 (Control.Monad.Trans.Free.FreeF f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Monad.Trans.Free.FreeF f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Trans.Free.FreeF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Trans.Free.FreeF f a)
instance GHC.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Monad.Trans.Free.FreeF f)
instance Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Monad.Trans.Free.FreeF f)
instance Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Monad.Trans.Free.FreeF f)
instance (GHC.Base.Functor f, Prelude.Extras.Eq1 f, GHC.Base.Functor m, Prelude.Extras.Eq1 m) => Prelude.Extras.Eq1 (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Prelude.Extras.Ord1 f, GHC.Base.Functor m, Prelude.Extras.Ord1 m) => Prelude.Extras.Ord1 (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Prelude.Extras.Show1 f, GHC.Base.Functor m, Prelude.Extras.Show1 m) => Prelude.Extras.Show1 (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Show.Show (m (Control.Monad.Trans.Free.FreeF f a (Control.Monad.Trans.Free.FreeT f m a))) => GHC.Show.Show (Control.Monad.Trans.Free.FreeT f m a)
instance (GHC.Base.Functor f, Prelude.Extras.Read1 f, GHC.Base.Functor m, Prelude.Extras.Read1 m) => Prelude.Extras.Read1 (Control.Monad.Trans.Free.FreeT f m)
instance GHC.Read.Read (m (Control.Monad.Trans.Free.FreeF f a (Control.Monad.Trans.Free.FreeT f m a))) => GHC.Read.Read (Control.Monad.Trans.Free.FreeT f m a)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Functor (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Applicative (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Monad (Control.Monad.Trans.Free.FreeT f m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.FreeT f)
instance (GHC.Base.Functor f, Control.Monad.IO.Class.MonadIO m) => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.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.Base.Functor f, Control.Monad.Writer.Class.MonadWriter w m) => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.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.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.Base.Functor f, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.MonadPlus m) => GHC.Base.Alternative (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.MonadPlus m) => GHC.Base.MonadPlus (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Catch.MonadThrow m) => Control.Monad.Catch.MonadThrow (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Functor f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.FreeT f m)
instance (Data.Foldable.Foldable m, Data.Foldable.Foldable f) => Data.Foldable.Foldable (Control.Monad.Trans.Free.FreeT f m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Traversable.Traversable (Control.Monad.Trans.Free.FreeT f m)

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

-- | The "free monad transformer" for a functor f
newtype FT f m a
FT :: (forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r) -> FT f m a
[runFT] :: FT f m a -> forall r. (a -> m r) -> (forall x. (x -> m r) -> f x -> m r) -> m r

-- | The "free monad" for a functor f.
type F f = 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 Free 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 FT behind the
--   scenes.
--   
--   Similar to improve.
improveT :: (Functor f, Monad m) => (forall t. MonadFree f (t m) => t m a) -> FreeT f m a

-- | Generate a Church-encoded free monad transformer from a FreeT
--   monad transformer.
toFT :: Monad m => FreeT f m a -> FT f m a

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

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

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

-- | Lift a monad homomorphism from m to n into a monad
--   homomorphism from FT f m to FT f n
--   
--   
--   hoistFT :: (Monad m, Monad n, Functor f) => (m ~> n) -> FT f m ~> FT f n
--   
hoistFT :: (Monad m, Monad n) => (forall a. m a -> n a) -> FT f m b -> FT f n b

-- | Lift a natural transformation from f to g into a
--   monad homomorphism from FT f m to FT g
--   n
transFT :: (forall a. f a -> g a) -> FT f m b -> FT g m b

-- | Pull out and join m layers of FreeT f m a.
joinFT :: (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):
--   
--   
--   cutoff 0     _        == return Nothing
--   
--   
--   
--   cutoff (n+1) . return == return . Just
--   
--   
--   
--   cutoff (n+1) . lift   ==   lift . liftM Just
--   
--   
--   
--   cutoff (n+1) . wrap   ==  wrap . fmap (cutoff n)
--   
--   
--   Calling 'retract . cutoff n' is always terminating, provided each of
--   the steps in the iteration is terminating.
cutoff :: (Functor f, Monad m) => Integer -> FT f m a -> FT f m (Maybe a)

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

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

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

-- | retract is the left inverse of liftF
--   
--   
--   retract . liftF = id
--   
retract :: Monad f => F f a -> f a

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

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

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

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

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: MonadFree f m => f (m a) -> m a

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: (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.Base.Functor f, GHC.Base.Monad m, GHC.Classes.Eq (Control.Monad.Trans.Free.FreeT f m a)) => GHC.Classes.Eq (Control.Monad.Trans.Free.Church.FT f m a)
instance (GHC.Base.Functor f, GHC.Base.Monad m, GHC.Classes.Ord (Control.Monad.Trans.Free.FreeT f m a)) => GHC.Classes.Ord (Control.Monad.Trans.Free.Church.FT f m a)
instance GHC.Base.Functor (Control.Monad.Trans.Free.Church.FT f m)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Base.Applicative (Control.Monad.Trans.Free.Church.FT f m)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Base.Monad (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Free.Class.MonadFree f (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.Trans.Class.MonadTrans (Control.Monad.Trans.Free.Church.FT f)
instance GHC.Base.Alternative m => GHC.Base.Alternative (Control.Monad.Trans.Free.Church.FT f m)
instance GHC.Base.MonadPlus m => GHC.Base.MonadPlus (Control.Monad.Trans.Free.Church.FT f m)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable m, GHC.Base.Monad m) => Data.Foldable.Foldable (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Traversable.Traversable (Control.Monad.Trans.Free.Church.FT f m)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Control.Monad.Trans.Free.Church.FT f m)
instance (GHC.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 Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (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 (GHC.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 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 (GHC.Base.Functor f, Control.Monad.Catch.MonadCatch m) => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Free.Church.FT f m)

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

-- | The monad supporting iteration based over a base monad m.
--   
--   
--   IterT ~ FreeT Identity
--   
newtype IterT m a
IterT :: m (Either a (IterT m a)) -> IterT m a
[runIterT] :: IterT m a -> m (Either a (IterT m a))

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

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

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

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

-- | Lift a monad homomorphism from m to n into a Monad
--   homomorphism from IterT m to IterT n.
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.
--   liftIter is a Monad homomorphism.
liftIter :: (Monad m) => Iter a -> IterT m a

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

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

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

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

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

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

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

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: MonadFree f m => f (m a) -> m a

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a
instance (GHC.Base.Functor m, Prelude.Extras.Eq1 m) => Prelude.Extras.Eq1 (Control.Monad.Trans.Iter.IterT m)
instance GHC.Classes.Eq (m (Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))) => GHC.Classes.Eq (Control.Monad.Trans.Iter.IterT m a)
instance (GHC.Base.Functor m, Prelude.Extras.Ord1 m) => Prelude.Extras.Ord1 (Control.Monad.Trans.Iter.IterT m)
instance GHC.Classes.Ord (m (Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))) => GHC.Classes.Ord (Control.Monad.Trans.Iter.IterT m a)
instance (GHC.Base.Functor m, Prelude.Extras.Show1 m) => Prelude.Extras.Show1 (Control.Monad.Trans.Iter.IterT m)
instance GHC.Show.Show (m (Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))) => GHC.Show.Show (Control.Monad.Trans.Iter.IterT m a)
instance (GHC.Base.Functor m, Prelude.Extras.Read1 m) => Prelude.Extras.Read1 (Control.Monad.Trans.Iter.IterT m)
instance GHC.Read.Read (m (Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))) => GHC.Read.Read (Control.Monad.Trans.Iter.IterT m a)
instance GHC.Base.Monad m => GHC.Base.Functor (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.Monad (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => Data.Functor.Bind.Class.Apply (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => Data.Functor.Bind.Class.Bind (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Fix.MonadFix m => Control.Monad.Fix.MonadFix (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.Alternative (Control.Monad.Trans.Iter.IterT m)
instance GHC.Base.Monad m => GHC.Base.MonadPlus (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Trans.Iter.IterT
instance Data.Foldable.Foldable m => Data.Foldable.Foldable (Control.Monad.Trans.Iter.IterT m)
instance Data.Semigroup.Foldable.Class.Foldable1 m => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Base.Monad m, Data.Traversable.Traversable m) => Data.Traversable.Traversable (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Base.Monad m, Data.Semigroup.Traversable.Class.Traversable1 m) => Data.Semigroup.Traversable.Class.Traversable1 (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.Writer.Class.MonadWriter w m => Control.Monad.Writer.Class.MonadWriter w (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.Error.Class.MonadError e m => Control.Monad.Error.Class.MonadError e (Control.Monad.Trans.Iter.IterT m)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (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 GHC.Base.Monad m => Control.Monad.Free.Class.MonadFree Data.Functor.Identity.Identity (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.Catch.MonadCatch m => Control.Monad.Catch.MonadCatch (Control.Monad.Trans.Iter.IterT m)
instance (GHC.Base.Monad m, GHC.Base.Monoid a) => GHC.Base.Monoid (Control.Monad.Trans.Iter.IterT m a)
instance (Data.Typeable.Internal.Typeable m, Data.Typeable.Internal.Typeable a, Data.Data.Data (m (Data.Either.Either a (Control.Monad.Trans.Iter.IterT m a))), Data.Data.Data a) => Data.Data.Data (Control.Monad.Trans.Iter.IterT m a)

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

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

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: MonadFree f m => f (m a) -> m a

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: (MonadFree f m, m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a

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

-- | retract is the left inverse of lift and liftF
--   
--   
--   retract . lift = id
--   retract . liftF = id
--   
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 Free Monad using iteration.
iter :: Functor f => (f a -> a) -> Free f a -> a

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

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

-- | Lift a natural transformation from f to g into a
--   natural transformation from FreeT f to
--   FreeT g.
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 Free monad from Control.Monad.Free to a
--   FreeT monad from Control.Monad.Trans.Free.
toFreeT :: (Functor f, Monad m) => Free f a -> FreeT f m a

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

-- | 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, Applicative m, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f a)

-- | This is Prism' (Free f a) a in disguise
--   
--   
--   >>> preview _Pure (Pure 3)
--   Just 3
--   
--   
--   
--   >>> review _Pure 3 :: Free Maybe Int
--   Pure 3
--   
_Pure :: forall f m a p. (Choice p, Applicative m) => p a (m a) -> p (Free f a) (m (Free f a))

-- | This is Prism' (Free f a) (f (Free f a)) in disguise
--   
--   
--   >>> preview _Free (review _Free (Just (Pure 3)))
--   Just (Just (Pure 3))
--   
--   
--   
--   >>> review _Free (Just (Pure 3))
--   Free (Just (Pure 3))
--   
_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.Base.Functor f, Prelude.Extras.Eq1 f) => Prelude.Extras.Eq1 (Control.Monad.Free.Free f)
instance (GHC.Classes.Eq (f (Control.Monad.Free.Free f a)), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Monad.Free.Free f a)
instance (GHC.Base.Functor f, Prelude.Extras.Ord1 f) => Prelude.Extras.Ord1 (Control.Monad.Free.Free f)
instance (GHC.Classes.Ord (f (Control.Monad.Free.Free f a)), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Monad.Free.Free f a)
instance (GHC.Base.Functor f, Prelude.Extras.Show1 f) => Prelude.Extras.Show1 (Control.Monad.Free.Free f)
instance (GHC.Show.Show (f (Control.Monad.Free.Free f a)), GHC.Show.Show a) => GHC.Show.Show (Control.Monad.Free.Free f a)
instance (GHC.Base.Functor f, Prelude.Extras.Read1 f) => Prelude.Extras.Read1 (Control.Monad.Free.Free f)
instance (GHC.Read.Read (f (Control.Monad.Free.Free f a)), GHC.Read.Read a) => GHC.Read.Read (Control.Monad.Free.Free f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => Data.Functor.Bind.Class.Apply (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => GHC.Base.Applicative (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => Data.Functor.Bind.Class.Bind (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => GHC.Base.Monad (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => Control.Monad.Fix.MonadFix (Control.Monad.Free.Free f)
instance GHC.Base.Alternative v => GHC.Base.Alternative (Control.Monad.Free.Free v)
instance (GHC.Base.Functor v, GHC.Base.MonadPlus v) => GHC.Base.MonadPlus (Control.Monad.Free.Free v)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Free
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Free.Free f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Monad.Free.Free f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Free.Free f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Monad.Free.Free f)
instance (GHC.Base.Functor m, Control.Monad.Writer.Class.MonadWriter e m) => Control.Monad.Writer.Class.MonadWriter e (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.Reader.Class.MonadReader e m) => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.State.Class.MonadState s m) => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.Error.Class.MonadError e m) => Control.Monad.Error.Class.MonadError e (Control.Monad.Free.Free m)
instance (GHC.Base.Functor m, Control.Monad.Cont.Class.MonadCont m) => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Free m)
instance GHC.Base.Functor f => Control.Monad.Free.Class.MonadFree f (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 Functor over subtrees.
--   
--   For each time that the fmap or >>= 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:
--   
--   
--   
- All uses of fmap are collapsed into a single one, so that
--   the values on the _leaves_ are transformed in one pass.
--   
--   
--   
--   fmap f . fmap g == fmap (f . g)
--   
--   
--   
--   
- All uses of >>= are right associated, so that every
--   new subtree created is final.
--   
--   
--   
--   (m >>= f) >>= g == m >>= (\x -> f x >>= g)
--   
--   
--   Asymptotically, the Church encoding supports the monadic operations
--   more efficiently than the naïve Free.
--   
--   This is based on the "Free Monads for Less" series of articles by
--   Edward Kmett:
--   
--   
--   
- Free monads for less — Part 1
--   
- Free monads for less — Part 2
--   
module Control.Monad.Free.Church

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

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

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

-- | Tear down a Free Monad 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 Free monad.
toF :: Functor f => Free f a -> F f a

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

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

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: MonadFree f m => f (m a) -> m a

-- | Add a layer.
--   
--   
--   wrap (fmap f x) ≡ wrap (fmap return x) >>= f
--   
wrap :: (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 (n ≥ 0):
--   
--   
--   cutoff 0     _        == return Nothing
--   
--   
--   
--   cutoff (n+1) . return == return . Just
--   
--   
--   
--   cutoff (n+1) . lift   == lift . liftM Just
--   
--   
--   
--   cutoff (n+1) . wrap   == wrap . fmap (cutoff n)
--   
--   
--   Calling retract . cutoff n is always
--   terminating, provided each of the steps in the iteration is
--   terminating.
cutoff :: (Functor f) => Integer -> F f a -> F f (Maybe a)
instance GHC.Base.Functor (Control.Monad.Free.Church.F f)
instance Data.Functor.Bind.Class.Apply (Control.Monad.Free.Church.F f)
instance GHC.Base.Applicative (Control.Monad.Free.Church.F f)
instance GHC.Base.Alternative f => GHC.Base.Alternative (Control.Monad.Free.Church.F f)
instance Data.Functor.Bind.Class.Bind (Control.Monad.Free.Church.F f)
instance GHC.Base.Monad (Control.Monad.Free.Church.F f)
instance Control.Monad.Fix.MonadFix (Control.Monad.Free.Church.F f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Monad.Free.Church.F f)
instance GHC.Base.MonadPlus f => GHC.Base.MonadPlus (Control.Monad.Free.Church.F f)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Church.F
instance GHC.Base.Functor f => Control.Monad.Free.Class.MonadFree f (Control.Monad.Free.Church.F f)
instance Control.Monad.State.Class.MonadState s m => Control.Monad.State.Class.MonadState s (Control.Monad.Free.Church.F m)
instance Control.Monad.Reader.Class.MonadReader e m => Control.Monad.Reader.Class.MonadReader e (Control.Monad.Free.Church.F m)
instance Control.Monad.Writer.Class.MonadWriter w m => Control.Monad.Writer.Class.MonadWriter w (Control.Monad.Free.Church.F m)
instance Control.Monad.Cont.Class.MonadCont m => Control.Monad.Cont.Class.MonadCont (Control.Monad.Free.Church.F m)

module Control.Comonad.Cofree.Class

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

-- | Remove a layer.
unwrap :: ComonadCofree f w => w a -> f (w a)
instance Control.Comonad.Cofree.Class.ComonadCofree GHC.Base.Maybe Data.List.NonEmpty.NonEmpty
instance Control.Comonad.Cofree.Class.ComonadCofree [] Data.Tree.Tree
instance Control.Comonad.Cofree.Class.ComonadCofree (Data.Functor.Const.Const b) ((,) b)
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.Env.EnvT e 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.Base.Monoid m) => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Traced.TracedT m w)

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

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

-- | The cofree Comonad of a functor f.
type Cofree f = CofreeT f Identity

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

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

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

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

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

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

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

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

-- | Unfold a CofreeT 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.Read.Read (f b), GHC.Read.Read a) => GHC.Read.Read (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Show.Show (f b), GHC.Show.Show a) => GHC.Show.Show (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Classes.Ord (f b), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (GHC.Classes.Eq (f b), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Comonad.Trans.Cofree.CofreeF f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Comonad.Trans.Cofree.CofreeF f a)
instance GHC.Base.Functor f => Data.Bifunctor.Bifunctor (Control.Comonad.Trans.Cofree.CofreeF f)
instance Data.Foldable.Foldable f => Data.Bifoldable.Bifoldable (Control.Comonad.Trans.Cofree.CofreeF f)
instance Data.Traversable.Traversable f => Data.Bitraversable.Bitraversable (Control.Comonad.Trans.Cofree.CofreeF f)
instance (GHC.Base.Functor f, GHC.Base.Functor w) => GHC.Base.Functor (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Base.Functor f, Control.Comonad.Comonad w) => Control.Comonad.Comonad (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable w) => Data.Foldable.Foldable (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (Data.Traversable.Traversable f, Data.Traversable.Traversable w) => Data.Traversable.Traversable (Control.Comonad.Trans.Cofree.CofreeT f w)
instance Control.Comonad.Trans.Class.ComonadTrans (Control.Comonad.Trans.Cofree.CofreeT f)
instance (GHC.Base.Functor f, Control.Comonad.Comonad w) => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.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.Base.Functor f => Control.Comonad.Hoist.Class.ComonadHoist (Control.Comonad.Trans.Cofree.CofreeT f)
instance GHC.Show.Show (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Show.Show (Control.Comonad.Trans.Cofree.CofreeT f w a)
instance GHC.Read.Read (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))) => GHC.Read.Read (Control.Comonad.Trans.Cofree.CofreeT f w a)
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.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 (GHC.Base.Alternative f, GHC.Base.Monad w) => GHC.Base.Monad (Control.Comonad.Trans.Cofree.CofreeT f w)
instance (GHC.Base.Alternative f, GHC.Base.Applicative w) => GHC.Base.Applicative (Control.Comonad.Trans.Cofree.CofreeT f w)
instance GHC.Base.Alternative f => Control.Monad.Trans.Class.MonadTrans (Control.Comonad.Trans.Cofree.CofreeT f)
instance (GHC.Base.Alternative f, Control.Monad.Zip.MonadZip f, Control.Monad.Zip.MonadZip m) => Control.Monad.Zip.MonadZip (Control.Comonad.Trans.Cofree.CofreeT f m)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable b, Data.Data.Data a, Data.Data.Data (f b), Data.Data.Data b) => Data.Data.Data (Control.Comonad.Trans.Cofree.CofreeF f a b)
instance (Data.Typeable.Internal.Typeable f, Data.Typeable.Internal.Typeable w, Data.Typeable.Internal.Typeable a, Data.Data.Data (w (Control.Comonad.Trans.Cofree.CofreeF f a (Control.Comonad.Trans.Cofree.CofreeT f w a))), Data.Data.Data a) => Data.Data.Data (Control.Comonad.Trans.Cofree.CofreeT f w a)

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

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

-- | The coiterative comonad
type Coiter = CoiterT Identity

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

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

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

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

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

-- | Cofree comonads
module Control.Comonad.Cofree

-- | The Cofree Comonad of a functor f.
--   
--   Formally
--   
--   A Comonad v is a cofree Comonad for f
--   if every comonad homomorphism from another comonad w to
--   v is equivalent to a natural transformation from w
--   to f.
--   
--   A cofree 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
--   extract and duplicate, leaving you with only a
--   Functor.
--   
--   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,
--   
--   
--   
- Cofree Maybe forms the a comonad for a
--   non-empty list.
--   
- Cofree (Const b) is a product.
--   
- Cofree Identity forms an infinite
--   stream.
--   
- Cofree ((->) b)' describes a Moore machine with
--   states labeled with values of type a, and transitions on edges of type
--   b.
--   
--   
--   Furthermore, if the functor f forms a monoid (for example, by
--   being an instance of Alternative), the resulting Comonad
--   is also a Monad. See Monadic Augment and Generalised
--   Shortcut Fusion by Neil Ghani et al., Section 4.3 for more
--   details.
--   
--   In particular, if f a ≡ [a], the resulting data structure is
--   a Rose tree. For a practical application, check Higher
--   Dimensional Trees, Algebraically by Neil Ghani et al.
data Cofree f a
(:<) :: a -> f (Cofree f a) -> Cofree f a

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

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

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

-- | Use coiteration to generate a cofree comonad from a seed.
--   
--   
--   coiter f = unfold (id &&& f)
--   
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
--   extract.
--   
--   Using (^.) from the lens package:
--   
--   
--   foo ^. _extract == extract foo
--   
--   
--   For more on lenses see the lens package on hackage
--   
--   
--   _extract :: Lens' (Cofree g a) a
--   
_extract :: Functor f => (a -> f a) -> Cofree g a -> f (Cofree g a)

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

-- | Construct an Lens into a Cofree g given a
--   list of lenses into the base functor. When the input list is empty,
--   this is equivalent to _extract. When the input list is
--   non-empty, this composes the input lenses with _unwrap to walk
--   through the Cofree g before using _extract to
--   get the element at the final location.
--   
--   For more on lenses see the lens package on hackage.
--   
--   
--   telescoped :: [Lens' (g (Cofree g a)) (Cofree g a)]      -> Lens' (Cofree g a) a
--   
--   
--   
--   telescoped :: [Traversal' (g (Cofree g a)) (Cofree g a)] -> Traversal' (Cofree g a) a
--   
--   
--   
--   telescoped :: [Getter (g (Cofree g a)) (Cofree g a)]     -> Getter (Cofree g a) a
--   
--   
--   
--   telescoped :: [Fold (g (Cofree g a)) (Cofree g a)]       -> Fold (Cofree g a) a
--   
--   
--   
--   telescoped :: [Setter' (g (Cofree g a)) (Cofree g a)]    -> Setter' (Cofree g a) a
--   
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)
instance GHC.Base.Functor f => Control.Comonad.Cofree.Class.ComonadCofree f (Control.Comonad.Cofree.Cofree f)
instance Data.Distributive.Distributive f => Data.Distributive.Distributive (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Functor f => Data.Functor.Extend.Extend (Control.Comonad.Cofree.Cofree f)
instance GHC.Base.Functor f => Control.Comonad.Comonad (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.Trans.Class.ComonadTrans Control.Comonad.Cofree.Cofree
instance GHC.Base.Alternative f => GHC.Base.Monad (Control.Comonad.Cofree.Cofree f)
instance (GHC.Base.Alternative f, Control.Monad.Zip.MonadZip f) => Control.Monad.Zip.MonadZip (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.Base.Alternative f => GHC.Base.Applicative (Control.Comonad.Cofree.Cofree f)
instance (GHC.Base.Functor f, Prelude.Extras.Show1 f) => Prelude.Extras.Show1 (Control.Comonad.Cofree.Cofree f)
instance (GHC.Show.Show (f (Control.Comonad.Cofree.Cofree f a)), GHC.Show.Show a) => GHC.Show.Show (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Base.Functor f, Prelude.Extras.Read1 f) => Prelude.Extras.Read1 (Control.Comonad.Cofree.Cofree f)
instance (GHC.Read.Read (f (Control.Comonad.Cofree.Cofree f a)), GHC.Read.Read a) => GHC.Read.Read (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Classes.Eq (f (Control.Comonad.Cofree.Cofree f a)), GHC.Classes.Eq a) => GHC.Classes.Eq (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Base.Functor f, Prelude.Extras.Eq1 f) => Prelude.Extras.Eq1 (Control.Comonad.Cofree.Cofree f)
instance (GHC.Classes.Ord (f (Control.Comonad.Cofree.Cofree f a)), GHC.Classes.Ord a) => GHC.Classes.Ord (Control.Comonad.Cofree.Cofree f a)
instance (GHC.Base.Functor f, Prelude.Extras.Ord1 f) => Prelude.Extras.Ord1 (Control.Comonad.Cofree.Cofree f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Control.Comonad.Cofree.Cofree f)
instance Data.Semigroup.Foldable.Class.Foldable1 f => Data.Semigroup.Foldable.Class.Foldable1 (Control.Comonad.Cofree.Cofree f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Comonad.Cofree.Cofree f)
instance Data.Semigroup.Traversable.Class.Traversable1 f => Data.Semigroup.Traversable.Class.Traversable1 (Control.Comonad.Cofree.Cofree f)
instance Control.Comonad.Hoist.Class.ComonadHoist Control.Comonad.Cofree.Cofree
instance Control.Comonad.Env.Class.ComonadEnv e w => Control.Comonad.Env.Class.ComonadEnv e (Control.Comonad.Cofree.Cofree w)
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)

-- | Applicative functor transformers for free
module Control.Applicative.Trans.Free

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

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

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

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

-- | Given natural transformations f ~> h and g . h ~>
--   h this gives a natural transformation ApT f g ~> h.
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 f ~> h and g . h ~>
--   h this gives a natural transformation ApF f g ~> h.
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 ApT f g b value.
--   
--   Examples:
--   
--   
--   height :: (Functor g, Foldable g) => ApT f g a -> Int
--   height = getSum . runApT_ (_ -> Sum 1) maximum
--   
--   
--   
--   size :: (Functor g, Foldable g) => ApT f g a -> Int
--   size = getSum . runApT_ (_ -> Sum 1) fold
--   
runApT_ :: (Functor g, Monoid m) => (forall a. f a -> m) -> (g m -> m) -> ApT f g b -> m

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

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

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

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

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

-- | The free Applicative for a Functor f.
type Ap f = ApT f Identity

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

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

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

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

-- | Given a natural transformation from f to g, this
--   gives a canonical monoidal natural transformation from Alt
--   f to g.
runAlt :: (Alternative g, Foldable t) => (forall x. f x -> g x) -> ApT f t a -> g a
instance GHC.Base.Functor g => GHC.Base.Functor (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Base.Functor g => GHC.Base.Functor (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Base.Applicative g => GHC.Base.Applicative (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Base.Applicative g => GHC.Base.Applicative (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Base.Applicative g => Data.Functor.Bind.Class.Apply (Control.Applicative.Trans.Free.ApF f g)
instance GHC.Base.Applicative g => Data.Functor.Bind.Class.Apply (Control.Applicative.Trans.Free.ApT f g)
instance GHC.Base.Alternative g => GHC.Base.Alternative (Control.Applicative.Trans.Free.ApT f g)

-- | Final encoding of free Applicative functors.
module Control.Applicative.Free.Final

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

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

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

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

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

-- | Interprets the free applicative functor over f using the semantics for
--   pure and <*> given by the Applicative instance for
--   f.
--   
--   
--   retractApp == runAp id
--   
retractAp :: Applicative f => Ap f a -> f a
instance GHC.Base.Functor (Control.Applicative.Free.Final.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Final.Ap f)
instance GHC.Base.Applicative (Control.Applicative.Free.Final.Ap f)

-- | Applicative functors for free
module Control.Applicative.Free

-- | The free Applicative for a Functor f.
data Ap f a
[Pure] :: a -> Ap f a
[Ap] :: f a -> Ap f (a -> b) -> Ap f b

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

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

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

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

-- | Interprets the free applicative functor over f using the semantics for
--   pure and <*> given by the Applicative instance for
--   f.
--   
--   
--   retractApp == runAp id
--   
retractAp :: Applicative f => Ap f a -> f a
instance GHC.Base.Functor (Control.Applicative.Free.Ap f)
instance Data.Functor.Bind.Class.Apply (Control.Applicative.Free.Ap f)
instance GHC.Base.Applicative (Control.Applicative.Free.Ap f)

-- | Final encoding of free Alternative functors.
module Control.Alternative.Free.Final

-- | The free Alternative for a Functor f.
newtype Alt f a
Alt :: (forall g. Alternative g => (forall x. f x -> g x) -> g a) -> Alt f a
[_runAlt] :: Alt f a -> forall g. Alternative g => (forall x. f x -> g x) -> g a

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

-- | A version of lift that can be used with f.
liftAlt :: f a -> Alt f a

-- | Given a natural transformation from f to g this
--   gives a monoidal natural transformation from Alt f to Alt
--   g.
hoistAlt :: (forall a. f a -> g a) -> Alt f b -> Alt g b
instance GHC.Base.Functor (Control.Alternative.Free.Final.Alt f)
instance Data.Functor.Bind.Class.Apply (Control.Alternative.Free.Final.Alt f)
instance GHC.Base.Applicative (Control.Alternative.Free.Final.Alt f)
instance Data.Functor.Alt.Alt (Control.Alternative.Free.Final.Alt f)
instance GHC.Base.Alternative (Control.Alternative.Free.Final.Alt f)
instance Data.Semigroup.Semigroup (Control.Alternative.Free.Final.Alt f a)
instance GHC.Base.Monoid (Control.Alternative.Free.Final.Alt f a)

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

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

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

-- | Given a natural transformation from f to g this
--   gives a monoidal natural transformation from Alt f to Alt
--   g.
hoistAlt :: (forall a. f a -> g a) -> Alt f b -> Alt g b
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Alternative.Free.AltF f)
instance GHC.Base.Functor f => GHC.Base.Functor (Control.Alternative.Free.Alt f)
instance GHC.Base.Functor f => GHC.Base.Applicative (Control.Alternative.Free.AltF f)
instance GHC.Base.Functor f => GHC.Base.Applicative (Control.Alternative.Free.Alt f)
instance GHC.Base.Functor f => Data.Functor.Bind.Class.Apply (Control.Alternative.Free.Alt f)
instance GHC.Base.Functor f => Data.Functor.Alt.Alt (Control.Alternative.Free.Alt f)
instance GHC.Base.Functor f => GHC.Base.Alternative (Control.Alternative.Free.Alt f)
instance GHC.Base.Functor f => Data.Semigroup.Semigroup (Control.Alternative.Free.Alt f a)
instance GHC.Base.Functor f => GHC.Base.Monoid (Control.Alternative.Free.Alt f a)
