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

-- | Free monads and monad transformers
--   
--   This package provides datatypes to construct Free monads, Free monad
--   transformers, and useful instances. In addition it provides the
--   constructs to avoid quadratic complexity of left associative bind, as
--   explained in:
--   
--   
--   
- Janis Voigtlander, Asymptotic Improvement of Computations over
--   Free Monads, MPC'08
--   
@package control-monad-free
@version 0.6.2

module Control.Monad.Free

-- | The Monad class defines the basic operations over a
--   monad, a concept from a branch of mathematics known as
--   category theory. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an abstract datatype
--   of actions. Haskell's do expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of Monad should satisfy the following:
--   
--   
--   
- Left identity return a >>= k = k
--   a
--   
- Right identity m >>= return =
--   m
--   
- Associativity m >>= (\x -> k x
--   >>= h) = (m >>= k) >>=
--   h
--   
--   
--   Furthermore, the Monad and Applicative operations should
--   relate as follows:
--   
--   
--   
- 
pure = return

--   
- 
m1 <*> m2 = m1 >>= (\x1 -> m2
--   >>= (\x2 -> return (x1 x2)))

--   
--   
--   The above laws imply:
--   
--   
--   
- 
fmap f xs = xs >>= return .
--   f

--   
- 
(>>) = (*>)

--   
--   
--   and that pure and (<*>) satisfy the applicative
--   functor laws.
--   
--   The instances of Monad for List, Maybe and
--   IO defined in the Prelude satisfy these laws.
class Applicative m => Monad (m :: Type -> Type)

-- | Sequentially compose two actions, passing any value produced by the
--   first as an argument to the second.
--   
--   'as >>= bs' can be understood as the do
--   expression
--   
--   
--   do a <- as
--      bs a
--   
--   
--   An alternative name for this function is 'bind', but some people may
--   refer to it as 'flatMap', which results from it being equivialent to
--   
--   
--   \x f -> join (fmap f x) :: Monad m => m a -> (a -> m b) -> m b
--   
--   
--   which can be seen as mapping a value with Monad m => m a ->
--   m (m b) and then 'flattening' m (m b) to m b
--   using join.
(>>=) :: Monad m => m a -> (a -> m b) -> m b

-- | Sequentially compose two actions, discarding any value produced by the
--   first, like sequencing operators (such as the semicolon) in imperative
--   languages.
--   
--   'as >> bs' can be understood as the do
--   expression
--   
--   
--   do as
--      bs
--   
--   
--   or in terms of (>>=) as
--   
--   
--   as >>= const bs
--   
(>>) :: Monad m => m a -> m b -> m b

-- | Inject a value into the monadic type. This function should not
--   be different from its default implementation as pure. The
--   justification for the existence of this function is merely historic.
return :: Monad m => a -> m a
infixl 1 >>=
infixl 1 >>

-- | A type f is a Functor if it provides a function fmap
--   which, given any types a and b lets you apply any
--   function from (a -> b) to turn an f a into an
--   f b, preserving the structure of f. Furthermore
--   f needs to adhere to the following:
--   
--   
--   
- Identity fmap id == id
--   
- Composition fmap (f . g) == fmap f .
--   fmap g
--   
--   
--   Note, that the second law follows from the free theorem of the type
--   fmap and the first law, so you need only check that the former
--   condition holds. See these articles by School of Haskell or
--   David Luposchainsky for an explanation.
class Functor (f :: Type -> Type)

-- | fmap is used to apply a function of type (a -> b)
--   to a value of type f a, where f is a functor, to produce a
--   value of type f b. Note that for any type constructor with
--   more than one parameter (e.g., Either), only the last type
--   parameter can be modified with fmap (e.g., b in
--   `Either a b`).
--   
--   Some type constructors with two parameters or more have a
--   Bifunctor instance that allows both the last and the
--   penultimate parameters to be mapped over.
--   
--   
Examples
--   
--   Convert from a Maybe Int to a Maybe String
--   using show:
--   
--   
--   >>> fmap show Nothing
--   Nothing
--   
--   >>> fmap show (Just 3)
--   Just "3"
--   
--   
--   Convert from an Either Int Int to an Either Int
--   String using show:
--   
--   
--   >>> fmap show (Left 17)
--   Left 17
--   
--   >>> fmap show (Right 17)
--   Right "17"
--   
--   
--   Double each element of a list:
--   
--   
--   >>> fmap (*2) [1,2,3]
--   [2,4,6]
--   
--   
--   Apply even to the second element of a pair:
--   
--   
--   >>> fmap even (2,2)
--   (2,True)
--   
--   
--   It may seem surprising that the function is only applied to the last
--   element of the tuple compared to the list example above which applies
--   it to every element in the list. To understand, remember that tuples
--   are type constructors with multiple type parameters: a tuple of 3
--   elements (a,b,c) can also be written (,,) a b c and
--   its Functor instance is defined for Functor ((,,) a
--   b) (i.e., only the third parameter is free to be mapped over with
--   fmap).
--   
--   It explains why fmap can be used with tuples containing
--   values of different types as in the following example:
--   
--   
--   >>> fmap even ("hello", 1.0, 4)
--   ("hello",1.0,True)
--   
fmap :: Functor f => (a -> b) -> f a -> f b

-- | Replace all locations in the input with the same value. The default
--   definition is fmap . const, but this may be
--   overridden with a more efficient version.
--   
--   
Examples
--   
--   Perform a computation with Maybe and replace the result with a
--   constant value if it is Just:
--   
--   
--   >>> 'a' <$ Just 2
--   Just 'a'
--   
--   >>> 'a' <$ Nothing
--   Nothing
--   
(<$) :: Functor f => a -> f b -> f a
infixl 4 <$

-- | Conditional failure of Alternative computations. Defined by
--   
--   
--   guard True  = pure ()
--   guard False = empty
--   
--   
--   
Examples
--   
--   Common uses of guard include conditionally signalling an error
--   in an error monad and conditionally rejecting the current choice in an
--   Alternative-based parser.
--   
--   As an example of signalling an error in the error monad Maybe,
--   consider a safe division function safeDiv x y that returns
--   Nothing when the denominator y is zero and
--   Just (x `div` y) otherwise. For example:
--   
--   
--   >>> safeDiv 4 0
--   Nothing
--   
--   
--   
--   >>> safeDiv 4 2
--   Just 2
--   
--   
--   A definition of safeDiv using guards, but not guard:
--   
--   
--   safeDiv :: Int -> Int -> Maybe Int
--   safeDiv x y | y /= 0    = Just (x `div` y)
--               | otherwise = Nothing
--   
--   
--   A definition of safeDiv using guard and Monad
--   do-notation:
--   
--   
--   safeDiv :: Int -> Int -> Maybe Int
--   safeDiv x y = do
--     guard (y /= 0)
--     return (x `div` y)
--   
guard :: Alternative f => Bool -> f ()

-- | The join function is the conventional monad join operator. It
--   is used to remove one level of monadic structure, projecting its bound
--   argument into the outer level.
--   
--   'join bss' can be understood as the do
--   expression
--   
--   
--   do bs <- bss
--      bs
--   
--   
--   
Examples
--   
--   
--   >>> join [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
--   [1,2,3,4,5,6,7,8,9]
--   
--   
--   
--   >>> join (Just (Just 3))
--   Just 3
--   
--   
--   A common use of join is to run an IO computation
--   returned from an STM transaction, since STM transactions
--   can't perform IO directly. Recall that
--   
--   
--   atomically :: STM a -> IO a
--   
--   
--   is used to run STM transactions atomically. So, by specializing
--   the types of atomically and join to
--   
--   
--   atomically :: STM (IO b) -> IO (IO b)
--   join       :: IO (IO b)  -> IO b
--   
--   
--   we can compose them as
--   
--   
--   join . atomically :: STM (IO b) -> IO b
--   
--   
--   to run an STM transaction and the IO action it returns.
join :: Monad m => m (m a) -> m a

-- | When a value is bound in do-notation, the pattern on the left
--   hand side of <- might not match. In this case, this class
--   provides a function to recover.
--   
--   A Monad without a MonadFail instance may only be used in
--   conjunction with pattern that always match, such as newtypes, tuples,
--   data types with only a single data constructor, and irrefutable
--   patterns (~pat).
--   
--   Instances of MonadFail should satisfy the following law:
--   fail s should be a left zero for >>=,
--   
--   
--   fail s >>= f  =  fail s
--   
--   
--   If your Monad is also MonadPlus, a popular definition is
--   
--   
--   fail _ = mzero
--   
--   
--   fail s should be an action that runs in the monad itself, not
--   an exception (except in instances of MonadIO). In particular,
--   fail should not be implemented in terms of error.
class Monad m => MonadFail (m :: Type -> Type)

-- | Monads that also support choice and failure.
class (Alternative m, Monad m) => MonadPlus (m :: Type -> Type)

-- | The identity of mplus. It should also satisfy the equations
--   
--   
--   mzero >>= f  =  mzero
--   v >> mzero   =  mzero
--   
--   
--   The default definition is
--   
--   
--   mzero = empty
--   
mzero :: MonadPlus m => m a

-- | An associative operation. The default definition is
--   
--   
--   mplus = (<|>)
--   
mplus :: MonadPlus m => m a -> m a -> m a

-- | Same as >>=, but with the arguments interchanged.
--   
--   
--   as >>= f == f =<< as
--   
(=<<) :: Monad m => (a -> m b) -> m a -> m b
infixr 1 =<<

-- | Conditional execution of Applicative expressions. For example,
--   
--   
Examples
--   
--   
--   when debug (putStrLn "Debugging")
--   
--   
--   will output the string Debugging if the Boolean value
--   debug is True, and otherwise do nothing.
--   
--   
--   >>> putStr "pi:" >> when False (print 3.14159)
--   pi:
--   
when :: Applicative f => Bool -> f () -> f ()

-- | Evaluate each monadic action in the structure from left to right, and
--   collect the results. For a version that ignores the results see
--   sequence_.
--   
--   
Examples
--   
--   Basic usage:
--   
--   The first two examples are instances where the input and and output of
--   sequence are isomorphic.
--   
--   
--   >>> sequence $ Right [1,2,3,4]
--   [Right 1,Right 2,Right 3,Right 4]
--   
--   
--   
--   >>> sequence $ [Right 1,Right 2,Right 3,Right 4]
--   Right [1,2,3,4]
--   
--   
--   The following examples demonstrate short circuit behavior for
--   sequence.
--   
--   
--   >>> sequence $ Left [1,2,3,4]
--   Left [1,2,3,4]
--   
--   
--   
--   >>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
--   Left 0
--   
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

-- | Map each element of a structure to a monadic action, evaluate these
--   actions from left to right, and collect the results. For a version
--   that ignores the results see mapM_.
--   
--   
Examples
--   
--   mapM is literally a traverse with a type signature
--   restricted to Monad. Its implementation may be more efficient
--   due to additional power of Monad.
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

-- | Promote a function to a monad. This is equivalent to fmap but
--   specialised to Monads.
liftM :: Monad m => (a1 -> r) -> m a1 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right.
--   
--   
Examples
--   
--   
--   >>> liftM2 (+) [0,1] [0,2]
--   [0,2,1,3]
--   
--   
--   
--   >>> liftM2 (+) (Just 1) Nothing
--   Nothing
--   
--   
--   
--   >>> liftM2 (+) (+ 3) (* 2) 5
--   18
--   
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. liftM2).
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. liftM2).
liftM4 :: Monad m => (a1 -> a2 -> a3 -> a4 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m r

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. liftM2).
liftM5 :: Monad m => (a1 -> a2 -> a3 -> a4 -> a5 -> r) -> m a1 -> m a2 -> m a3 -> m a4 -> m a5 -> m r

-- | In many situations, the liftM operations can be replaced by
--   uses of ap, which promotes function application.
--   
--   
--   return f `ap` x1 `ap` ... `ap` xn
--   
--   
--   is equivalent to
--   
--   
--   liftM<n> f x1 x2 ... xn
--   
--   
--   
Examples
--   
--   
--   >>> pure (\x y z -> x + y * z) `ap` Just 1 `ap` Just 5 `ap` Just 10
--   Just 51
--   
ap :: Monad m => m (a -> b) -> m a -> m b

-- | void value discards or ignores the result of
--   evaluation, such as the return value of an IO action.
--   
--   
Examples
--   
--   Replace the contents of a Maybe Int with unit:
--   
--   
--   >>> void Nothing
--   Nothing
--   
--   
--   
--   >>> void (Just 3)
--   Just ()
--   
--   
--   Replace the contents of an Either Int
--   Int with unit, resulting in an Either
--   Int ():
--   
--   
--   >>> void (Left 8675309)
--   Left 8675309
--   
--   
--   
--   >>> void (Right 8675309)
--   Right ()
--   
--   
--   Replace every element of a list with unit:
--   
--   
--   >>> void [1,2,3]
--   [(),(),()]
--   
--   
--   Replace the second element of a pair with unit:
--   
--   
--   >>> void (1,2)
--   (1,())
--   
--   
--   Discard the result of an IO action:
--   
--   
--   >>> mapM print [1,2]
--   1
--   2
--   [(),()]
--   
--   
--   
--   >>> void $ mapM print [1,2]
--   1
--   2
--   
void :: Functor f => f a -> f ()

-- | Map each element of a structure to a monadic action, evaluate these
--   actions from left to right, and ignore the results. For a version that
--   doesn't ignore the results see mapM.
--   
--   mapM_ is just like traverse_, but specialised to monadic
--   actions.
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()

-- | forM_ is mapM_ with its arguments flipped. For a version
--   that doesn't ignore the results see forM.
--   
--   forM_ is just like for_, but specialised to monadic
--   actions.
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()

-- | Evaluate each monadic action in the structure from left to right, and
--   ignore the results. For a version that doesn't ignore the results see
--   sequence.
--   
--   sequence_ is just like sequenceA_, but specialised to
--   monadic actions.
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()

-- | The sum of a collection of actions using (<|>),
--   generalizing concat.
--   
--   msum is just like asum, but specialised to
--   MonadPlus.
--   
--   
Examples
--   
--   Basic usage, using the MonadPlus instance for Maybe:
--   
--   
--   >>> msum [Just "Hello", Nothing, Just "World"]
--   Just "Hello"
--   
msum :: (Foldable t, MonadPlus m) => t (m a) -> m a

-- | forM is mapM with its arguments flipped. For a version
--   that ignores the results see forM_.
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)

-- | This generalizes the list-based filter function.
--   
--   
--   runIdentity (filterM (Identity . p) xs) == filter p xs
--   
--   
--   
Examples
--   
--   
--   >>> filterM (\x -> do
--         putStrLn ("Keep: " ++ show x ++ "?")
--         answer <- getLine
--         pure (answer == "y"))
--       [1, 2, 3]
--   Keep: 1?
--   y
--   Keep: 2?
--   n
--   Keep: 3?
--   y
--   [1,3]
--   
--   
--   
--   >>> filterM (\x -> do
--         putStr (show x)
--         x' <- readLn
--         pure (x == x'))
--       [1, 2, 3]
--   12
--   22
--   33
--   [2,3]
--   
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]

-- | Left-to-right composition of Kleisli arrows.
--   
--   '(bs >=> cs) a' can be understood as the
--   do expression
--   
--   
--   do b <- bs a
--      cs b
--   
--   
--   or in terms of (>>=) as
--   
--   
--   bs a >>= cs
--   
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
infixr 1 >=>

-- | Right-to-left composition of Kleisli arrows.
--   (>=>), with the arguments flipped.
--   
--   Note how this operator resembles function composition
--   (.):
--   
--   
--   (.)   ::            (b ->   c) -> (a ->   b) -> a ->   c
--   (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
--   
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
infixr 1 <=<

-- | Repeat an action indefinitely.
--   
--   
Examples
--   
--   A common use of forever is to process input from network
--   sockets, Handles, and channels (e.g. MVar and
--   Chan).
--   
--   For example, here is how we might implement an echo server,
--   using forever both to listen for client connections on a
--   network socket and to echo client input on client connection handles:
--   
--   
--   echoServer :: Socket -> IO ()
--   echoServer socket = forever $ do
--     client <- accept socket
--     forkFinally (echo client) (\_ -> hClose client)
--     where
--       echo :: Handle -> IO ()
--       echo client = forever $
--         hGetLine client >>= hPutStrLn client
--   
--   
--   Note that "forever" isn't necessarily non-terminating. If the action
--   is in a MonadPlus and short-circuits after some number
--   of iterations. then forever actually returns
--   mzero, effectively short-circuiting its caller.
forever :: Applicative f => f a -> f b

-- | The mapAndUnzipM function maps its first argument over a list,
--   returning the result as a pair of lists. This function is mainly used
--   with complicated data structures or a state monad.
mapAndUnzipM :: Applicative m => (a -> m (b, c)) -> [a] -> m ([b], [c])

-- | The zipWithM function generalizes zipWith to arbitrary
--   applicative functors.
zipWithM :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m [c]

-- | zipWithM_ is the extension of zipWithM which ignores the
--   final result.
zipWithM_ :: Applicative m => (a -> b -> m c) -> [a] -> [b] -> m ()

-- | The foldM function is analogous to foldl, except that
--   its result is encapsulated in a monad. Note that foldM works
--   from left-to-right over the list arguments. This could be an issue
--   where (>>) and the `folded function' are not
--   commutative.
--   
--   
--   foldM f a1 [x1, x2, ..., xm]
--   
--   ==
--   
--   do
--     a2 <- f a1 x1
--     a3 <- f a2 x2
--     ...
--     f am xm
--   
--   
--   If right-to-left evaluation is required, the input list should be
--   reversed.
--   
--   Note: foldM is the same as foldlM
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

-- | Like foldM, but discards the result.
foldM_ :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m ()

-- | replicateM n act performs the action act
--   n times, and then returns the list of results.
--   
--   
--   replicateM n (pure x) == replicate n x
--   
--   
--   
Examples
--   
--   
--   >>> replicateM 3 getLine
--   hi
--   heya
--   hiya
--   ["hi","heya","hiya"]
--   
--   
--   
--   >>> import Control.Monad.State
--   
--   >>> runState (replicateM 3 $ state $ \s -> (s, s + 1)) 1
--   ([1,2,3],4)
--   
replicateM :: Applicative m => Int -> m a -> m [a]

-- | Like replicateM, but discards the result.
--   
--   
Examples
--   
--   
--   >>> replicateM_ 3 (putStr "a")
--   aaa
--   
replicateM_ :: Applicative m => Int -> m a -> m ()

-- | The reverse of when.
--   
--   
Examples
--   
--   
--   >>> do x <- getLine
--          unless (x == "hi") (putStrLn "hi!")
--   comingupwithexamplesisdifficult
--   hi!
--   
--   
--   
--   >>> unless (pi > exp 1) Nothing
--   Just ()
--   
unless :: Applicative f => Bool -> f () -> f ()

-- | Strict version of <$>.
(<$!>) :: Monad m => (a -> b) -> m a -> m b
infixl 4 <$!>

-- | Direct MonadPlus equivalent of filter.
--   
--   
Examples
--   
--   The filter function is just mfilter specialized to the
--   list monad:
--   
--   
--   filter = ( mfilter :: (a -> Bool) -> [a] -> [a] )
--   
--   
--   An example using mfilter with the Maybe monad:
--   
--   
--   >>> mfilter odd (Just 1)
--   Just 1
--   
--   >>> mfilter odd (Just 2)
--   Nothing
--   
mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a

-- | This type class generalizes over encodings of Free Monads.
class (Functor f, Monad m) => MonadFree (f :: Type -> Type) (m :: Type -> Type)
free :: MonadFree f m => m a -> m (Either a (f (m a)))
wrap :: MonadFree f m => f (m a) -> m a
data Free (f :: Type -> Type) a
Impure :: f (Free f a) -> Free (f :: Type -> Type) a
Pure :: a -> Free (f :: Type -> Type) a
isPure :: forall (f :: Type -> Type) a. Free f a -> Bool
isImpure :: forall (f :: Type -> Type) a. Free f a -> Bool
foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
evalFree :: (a -> b) -> (f (Free f a) -> b) -> Free f a -> b
mapFree :: (Functor f, Functor g) => (f (Free g a) -> g (Free g a)) -> Free f a -> Free g a
mapFreeM :: (Traversable f, Functor g, Monad m) => (f (Free g a) -> m (g (Free g a))) -> Free f a -> m (Free g a)
mapFreeM' :: (Functor f, Traversable g, Monad m) => (forall a1. () => f a1 -> m (g a1)) -> Free f a -> m (Free g a)
foldFreeM :: (Traversable f, Monad m) => (a -> m b) -> (f b -> m b) -> Free f a -> m b
induce :: (Functor f, Monad m) => (forall a1. () => f a1 -> m a1) -> Free f a -> m a
newtype FreeT (f :: Type -> Type) (m :: Type -> Type) a
FreeT :: m (Either a (f (FreeT f m a))) -> FreeT (f :: Type -> Type) (m :: Type -> Type) a
[unFreeT] :: FreeT (f :: Type -> Type) (m :: Type -> Type) a -> m (Either a (f (FreeT f m a)))
foldFreeT :: (Traversable f, Monad m) => (a -> m b) -> (f b -> m b) -> FreeT f m a -> m b
foldFreeT' :: (Traversable f, Monad m) => (a -> b) -> (f b -> b) -> FreeT f m a -> m b
mapFreeT :: forall (f :: Type -> Type) m m' a. (Functor f, Functor m) => (forall a1. () => m a1 -> m' a1) -> FreeT f m a -> FreeT f m' a
foldFreeA :: (Traversable f, Applicative m) => (a -> m b) -> m (f b -> b) -> Free f a -> m b
mapFreeA :: (Traversable f, Functor g, Applicative m) => m (f (Free g a) -> g (Free g a)) -> Free f a -> m (Free g a)
trans :: forall (f :: Type -> Type) m a. MonadFree f m => Free f a -> m a
trans' :: forall (f :: Type -> Type) m a. (Functor f, Monad m) => m (Free f a) -> FreeT f m a
untrans :: forall (f :: Type -> Type) m a. (Traversable f, Monad m) => FreeT f m a -> m (Free f a)
liftFree :: forall (f :: Type -> Type) (m :: Type -> Type) a b. (Functor f, Monad m) => (a -> Free f b) -> a -> FreeT f m b
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Functor m, GHC.Internal.Base.Monad m, GHC.Internal.Base.MonadPlus m) => GHC.Internal.Base.Alternative (Control.Monad.Free.FreeT f m)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Applicative (Control.Monad.Free.Free f)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Functor a, GHC.Internal.Base.Monad a) => GHC.Internal.Base.Applicative (Control.Monad.Free.FreeT f a)
instance Data.Functor.Classes.Eq1 f => Data.Functor.Classes.Eq1 (Control.Monad.Free.Free f)
instance (GHC.Classes.Eq a, Data.Functor.Classes.Eq1 f) => GHC.Classes.Eq (Control.Monad.Free.Free f a)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Data.Foldable.Foldable f) => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Free.Free f)
instance (GHC.Internal.Data.Traversable.Traversable m, GHC.Internal.Data.Traversable.Traversable f) => GHC.Internal.Data.Foldable.Foldable (Control.Monad.Free.FreeT f m)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Functor (Control.Monad.Free.Free f)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Functor m) => GHC.Internal.Base.Functor (Control.Monad.Free.FreeT f m)
instance GHC.Internal.Generics.Generic (Control.Monad.Free.Free f a)
instance GHC.Internal.Base.Functor f => GHC.Internal.Base.Monad (Control.Monad.Free.Free f)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => GHC.Internal.Base.Monad (Control.Monad.Free.FreeT f m)
instance GHC.Internal.Base.Functor f => Control.Monad.Free.MonadFree f (Control.Monad.Free.Free f)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m) => Control.Monad.Free.MonadFree f (Control.Monad.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m, Control.Monad.IO.Class.MonadIO m) => Control.Monad.IO.Class.MonadIO (Control.Monad.Free.FreeT f m)
instance (GHC.Internal.Base.Functor f, GHC.Internal.Base.Monad m, GHC.Internal.Base.MonadPlus m) => GHC.Internal.Base.MonadPlus (Control.Monad.Free.FreeT f m)
instance GHC.Internal.Base.Functor f => Control.Monad.Trans.Class.MonadTrans (Control.Monad.Free.FreeT f)
instance Data.Functor.Classes.Ord1 f => Data.Functor.Classes.Ord1 (Control.Monad.Free.Free f)
instance (GHC.Classes.Ord a, Data.Functor.Classes.Ord1 f) => GHC.Classes.Ord (Control.Monad.Free.Free f a)
instance (GHC.Internal.Show.Show a, Data.Functor.Classes.Show1 f) => GHC.Internal.Show.Show (Control.Monad.Free.Free f a)
instance GHC.Internal.Data.Traversable.Traversable f => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Free.Free f)
instance (GHC.Internal.Data.Traversable.Traversable m, GHC.Internal.Data.Traversable.Traversable f) => GHC.Internal.Data.Traversable.Traversable (Control.Monad.Free.FreeT f m)

-- | Naive Free monads suffer from a quadratic complexity, as explained in
--   
--   
--   
- Janis Voigtlander, Asymptotic Improvement of Computations over
--   Free Monads, MPC'08
--   
--   
--   The solution is to redefine the Free datatype in CPS, similar to what
--   is done in difference lists to solve the problem on quadratic append
--   for lists.
module Control.Monad.Free.Improve
newtype C (mu :: Type -> Type) a
C :: (forall b. () => (a -> mu b) -> mu b) -> C (mu :: Type -> Type) a
rep :: Monad mu => mu a -> C mu a
improve :: Monad mu => C mu a -> mu a
instance GHC.Internal.Base.MonadPlus mu => GHC.Internal.Base.Alternative (Control.Monad.Free.Improve.C mu)
instance GHC.Internal.Base.Applicative (Control.Monad.Free.Improve.C mu)
instance GHC.Internal.Base.Functor (Control.Monad.Free.Improve.C mu)
instance GHC.Internal.Base.Monad (Control.Monad.Free.Improve.C mu)
instance GHC.Internal.Base.Functor f => Control.Monad.Free.MonadFree f (Control.Monad.Free.Improve.C (Control.Monad.Free.Free f))
instance (GHC.Internal.Base.Monad m, GHC.Internal.Base.Functor f) => Control.Monad.Free.MonadFree f (Control.Monad.Free.Improve.C (Control.Monad.Free.FreeT f m))
instance GHC.Internal.Base.MonadPlus mu => GHC.Internal.Base.MonadPlus (Control.Monad.Free.Improve.C mu)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Improve.C

module Control.Monad.Free.Zip
zipFree :: forall (f :: Type -> Type) m a b c. (Traversable f, Eq (f ()), MonadFail m) => (Free f a -> Free f b -> m (Free f c)) -> Free f a -> Free f b -> m (Free f c)
zipFree_ :: forall (f :: Type -> Type) m a b. (Traversable f, Eq (f ()), MonadFail m) => (Free f a -> Free f b -> m ()) -> Free f a -> Free f b -> m ()
