-- 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:
--   
--   <ul>
--   <li>Janis Voigtlander, <i>Asymptotic Improvement of Computations over
--   Free Monads, MPC'08</i></li>
--   </ul>
@package control-monad-free
@version 0.6.2

module Control.Monad.Free

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

-- | The <a>join</a> 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.
--   
--   <h4><b>Examples</b></h4>
--   
--   A common use of <a>join</a> is to run an <a>IO</a> computation
--   returned from an <a>STM</a> transaction, since <a>STM</a> transactions
--   can't perform <a>IO</a> directly. Recall that
--   
--   <pre>
--   <a>atomically</a> :: STM a -&gt; IO a
--   </pre>
--   
--   is used to run <a>STM</a> transactions atomically. So, by specializing
--   the types of <a>atomically</a> and <a>join</a> to
--   
--   <pre>
--   <a>atomically</a> :: STM (IO b) -&gt; IO (IO b)
--   <a>join</a>       :: IO (IO b)  -&gt; IO b
--   </pre>
--   
--   we can compose them as
--   
--   <pre>
--   <a>join</a> . <a>atomically</a> :: STM (IO b) -&gt; IO b
--   </pre>
--   
--   to run an <a>STM</a> transaction and the <a>IO</a> action it returns.
join :: Monad m => m (m a) -> m a

-- | The <a>Monad</a> class defines the basic operations over a
--   <i>monad</i>, a concept from a branch of mathematics known as
--   <i>category theory</i>. From the perspective of a Haskell programmer,
--   however, it is best to think of a monad as an <i>abstract datatype</i>
--   of actions. Haskell's <tt>do</tt> expressions provide a convenient
--   syntax for writing monadic expressions.
--   
--   Instances of <a>Monad</a> should satisfy the following laws:
--   
--   <ul>
--   <li><pre><a>return</a> a <a>&gt;&gt;=</a> k = k a</pre></li>
--   <li><pre>m <a>&gt;&gt;=</a> <a>return</a> = m</pre></li>
--   <li><pre>m <a>&gt;&gt;=</a> (\x -&gt; k x <a>&gt;&gt;=</a> h) = (m
--   <a>&gt;&gt;=</a> k) <a>&gt;&gt;=</a> h</pre></li>
--   </ul>
--   
--   Furthermore, the <a>Monad</a> and <a>Applicative</a> operations should
--   relate as follows:
--   
--   <ul>
--   <li><pre><a>pure</a> = <a>return</a></pre></li>
--   <li><pre>(<a>&lt;*&gt;</a>) = <a>ap</a></pre></li>
--   </ul>
--   
--   The above laws imply:
--   
--   <ul>
--   <li><pre><a>fmap</a> f xs = xs <a>&gt;&gt;=</a> <a>return</a> .
--   f</pre></li>
--   <li><pre>(<a>&gt;&gt;</a>) = (<a>*&gt;</a>)</pre></li>
--   </ul>
--   
--   and that <a>pure</a> and (<a>&lt;*&gt;</a>) satisfy the applicative
--   functor laws.
--   
--   The instances of <a>Monad</a> for lists, <a>Maybe</a> and <a>IO</a>
--   defined in the <a>Prelude</a> 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.
(>>=) :: 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.
(>>) :: Monad m => m a -> m b -> m b

-- | Inject a value into the monadic type.
return :: Monad m => a -> m a
infixl 1 >>=
infixl 1 >>

-- | The <a>Functor</a> class is used for types that can be mapped over.
--   Instances of <a>Functor</a> should satisfy the following laws:
--   
--   <pre>
--   fmap id  ==  id
--   fmap (f . g)  ==  fmap f . fmap g
--   </pre>
--   
--   The instances of <a>Functor</a> for lists, <a>Maybe</a> and <a>IO</a>
--   satisfy these laws.
class Functor (f :: Type -> Type)
fmap :: Functor f => (a -> b) -> f a -> f b

-- | 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 <a>mapM_</a>.
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

-- | Evaluate each monadic action in the structure from left to right, and
--   collect the results. For a version that ignores the results see
--   <a>sequence_</a>.
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

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

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

-- | The reverse of <a>when</a>.
unless :: Applicative f => Bool -> f () -> f ()

-- | Like <a>replicateM</a>, but discards the result.
replicateM_ :: Applicative m => Int -> m a -> m ()

-- | <tt><a>replicateM</a> n act</tt> performs the action <tt>n</tt> times,
--   gathering the results.
replicateM :: Applicative m => Int -> m a -> m [a]

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

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

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

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

-- | The <a>mapAndUnzipM</a> 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-transforming monad.
mapAndUnzipM :: Applicative m => (a -> m (b, c)) -> [a] -> m ([b], [c])

-- | Repeat an action indefinitely.
--   
--   <h4><b>Examples</b></h4>
--   
--   A common use of <a>forever</a> is to process input from network
--   sockets, <a>Handle</a>s, and channels (e.g. <a>MVar</a> and
--   <a>Chan</a>).
--   
--   For example, here is how we might implement an <a>echo server</a>,
--   using <a>forever</a> both to listen for client connections on a
--   network socket and to echo client input on client connection handles:
--   
--   <pre>
--   echoServer :: Socket -&gt; IO ()
--   echoServer socket = <a>forever</a> $ do
--     client &lt;- accept socket
--     <a>forkFinally</a> (echo client) (\_ -&gt; hClose client)
--     where
--       echo :: Handle -&gt; IO ()
--       echo client = <a>forever</a> $
--         hGetLine client &gt;&gt;= hPutStrLn client
--   </pre>
forever :: Applicative f => f a -> f b

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

-- | Left-to-right composition of Kleisli arrows.
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
infixr 1 >=>

-- | This generalizes the list-based <tt>filter</tt> function.
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]

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

-- | The sum of a collection of actions, generalizing <a>concat</a>. As of
--   base 4.8.0.0, <a>msum</a> is just <a>asum</a>, specialized to
--   <a>MonadPlus</a>.
msum :: (Foldable t, MonadPlus m) => t (m a) -> m a

-- | 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
--   <a>sequence</a>.
--   
--   As of base 4.8.0.0, <a>sequence_</a> is just <a>sequenceA_</a>,
--   specialized to <a>Monad</a>.
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()

-- | <a>forM_</a> is <a>mapM_</a> with its arguments flipped. For a version
--   that doesn't ignore the results see <a>forM</a>.
--   
--   As of base 4.8.0.0, <a>forM_</a> is just <a>for_</a>, specialized to
--   <a>Monad</a>.
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()

-- | 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 <a>mapM</a>.
--   
--   As of base 4.8.0.0, <a>mapM_</a> is just <a>traverse_</a>, specialized
--   to <a>Monad</a>.
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()

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

-- | In many situations, the <a>liftM</a> operations can be replaced by
--   uses of <a>ap</a>, which promotes function application.
--   
--   <pre>
--   return f `ap` x1 `ap` ... `ap` xn
--   </pre>
--   
--   is equivalent to
--   
--   <pre>
--   liftMn f x1 x2 ... xn
--   </pre>
ap :: Monad m => m (a -> b) -> m a -> m b

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

-- | Promote a function to a monad, scanning the monadic arguments from
--   left to right (cf. <a>liftM2</a>).
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. <a>liftM2</a>).
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. For example,
--   
--   <pre>
--   liftM2 (+) [0,1] [0,2] = [0,2,1,3]
--   liftM2 (+) (Just 1) Nothing = Nothing
--   </pre>
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r

-- | Promote a function to a monad.
liftM :: Monad m => (a1 -> r) -> m a1 -> m r

-- | Conditional execution of <a>Applicative</a> expressions. For example,
--   
--   <pre>
--   when debug (putStrLn "Debugging")
--   </pre>
--   
--   will output the string <tt>Debugging</tt> if the Boolean value
--   <tt>debug</tt> is <a>True</a>, and otherwise do nothing.
when :: Applicative f => Bool -> f () -> f ()

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

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

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

-- | An associative operation. The default definition is
--   
--   <pre>
--   mplus = (<a>&lt;|&gt;</a>)
--   </pre>
mplus :: MonadPlus m => m a -> m a -> m a

-- | This type class generalizes over encodings of Free Monads.
class (Functor f, Monad m) => MonadFree f m
free :: MonadFree f m => m a -> m (Either a (f (m a)))
wrap :: MonadFree f m => f (m a) -> m a
data Free f a
Impure :: f (Free f a) -> Free f a
Pure :: a -> Free f a
isPure :: Free f a -> Bool
isImpure :: 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 a. f a -> m (g a)) -> 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 a. f a -> m a) -> Free f a -> m a
newtype FreeT f m a
FreeT :: m (Either a (f (FreeT f m a))) -> FreeT f m a
[unFreeT] :: FreeT f m 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 :: (Functor f, Functor m) => (forall a. m a -> m' a) -> 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 :: MonadFree f m => Free f a -> m a
trans' :: (Functor f, Monad m) => m (Free f a) -> FreeT f m a
untrans :: (Traversable f, Monad m) => FreeT f m a -> m (Free f a)
liftFree :: (Functor f, Monad m) => (a -> Free f b) -> a -> FreeT f m b
instance GHC.Generics.Generic (Control.Monad.Free.Free f a)
instance (Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Foldable.Foldable (Control.Monad.Free.FreeT f m)
instance (Data.Traversable.Traversable m, Data.Traversable.Traversable f) => Data.Traversable.Traversable (Control.Monad.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Functor m) => GHC.Base.Functor (Control.Monad.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Functor a, GHC.Base.Monad a) => GHC.Base.Applicative (Control.Monad.Free.FreeT f a)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => GHC.Base.Monad (Control.Monad.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m) => Control.Monad.Free.MonadFree f (Control.Monad.Free.FreeT f m)
instance GHC.Base.Functor f => Control.Monad.Trans.Class.MonadTrans (Control.Monad.Free.FreeT f)
instance (GHC.Base.Functor f, GHC.Base.Monad m, Control.Monad.IO.Class.MonadIO m) => Control.Monad.IO.Class.MonadIO (Control.Monad.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Monad m, GHC.Base.MonadPlus m) => GHC.Base.MonadPlus (Control.Monad.Free.FreeT f m)
instance (GHC.Base.Functor f, GHC.Base.Functor m, GHC.Base.Monad m, GHC.Base.MonadPlus m) => GHC.Base.Alternative (Control.Monad.Free.FreeT f m)
instance GHC.Base.Functor f => Control.Monad.Free.MonadFree f (Control.Monad.Free.Free f)
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 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.Show.Show a, Data.Functor.Classes.Show1 f) => GHC.Show.Show (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.Foldable.Foldable f) => Data.Foldable.Foldable (Control.Monad.Free.Free f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => GHC.Base.Monad (Control.Monad.Free.Free f)
instance GHC.Base.Functor f => GHC.Base.Applicative (Control.Monad.Free.Free f)


-- | Naive Free monads suffer from a quadratic complexity, as explained in
--   
--   <ul>
--   <li>Janis Voigtlander, <i>Asymptotic Improvement of Computations over
--   Free Monads, MPC'08</i></li>
--   </ul>
--   
--   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 a
C :: (forall b. (a -> mu b) -> mu b) -> C mu a
rep :: Monad mu => mu a -> C mu a
improve :: Monad mu => C mu a -> mu a
instance GHC.Base.Functor (Control.Monad.Free.Improve.C mu)
instance GHC.Base.Monad (Control.Monad.Free.Improve.C mu)
instance GHC.Base.Applicative (Control.Monad.Free.Improve.C mu)
instance GHC.Base.Functor f => Control.Monad.Free.MonadFree f (Control.Monad.Free.Improve.C (Control.Monad.Free.Free f))
instance (GHC.Base.Monad m, GHC.Base.Functor f) => Control.Monad.Free.MonadFree f (Control.Monad.Free.Improve.C (Control.Monad.Free.FreeT f m))
instance GHC.Base.MonadPlus mu => GHC.Base.MonadPlus (Control.Monad.Free.Improve.C mu)
instance GHC.Base.MonadPlus mu => GHC.Base.Alternative (Control.Monad.Free.Improve.C mu)
instance Control.Monad.Trans.Class.MonadTrans Control.Monad.Free.Improve.C

module Control.Monad.Free.Zip
zipFree :: (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_ :: (Traversable f, Eq (f ()), MonadFail m) => (Free f a -> Free f b -> m ()) -> Free f a -> Free f b -> m ()
