/usr/share/doc/libghc-free-doc/html/Control-Monad-Trans-Iter.html is in libghc-free-doc 4.12.1-2build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Control.Monad.Trans.Iter</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Control-Monad-Trans-Iter.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Control-Monad-Trans-Iter.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">free-4.12.1: Monads for free</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>(C) 2013 Edward Kmett</td></tr><tr><th>License</th><td>BSD-style (see the file LICENSE)</td></tr><tr><th>Maintainer</th><td>Edward Kmett <ekmett@gmail.com></td></tr><tr><th>Stability</th><td>provisional</td></tr><tr><th>Portability</th><td>MPTCs, fundeps</td></tr><tr><th>Safe Haskell</th><td>Safe</td></tr><tr><th>Language</th><td>Haskell2010</td></tr></table><p class="caption">Control.Monad.Trans.Iter</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">The iterative monad transformer</a></li><li><a href="#g:2">Capretta's iterative monad</a></li><li><a href="#g:3">Combinators</a></li><li><a href="#g:4">Consuming iterative monads</a></li><li><a href="#g:5">IterT ~ FreeT Identity</a></li><li><a href="#g:6">Examples</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Based on <a href="http://www.ioc.ee/~tarmo/tday-veskisilla/uustalu-slides.pdf">Capretta's Iterative Monad Transformer</a></p><p>Unlike <code>Free</code>, this is a true monad transformer.</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">newtype</span> <a href="#t:IterT">IterT</a> m a = <a href="#v:IterT">IterT</a> {<ul class="subs"><li><a href="#v:runIterT">runIterT</a> :: m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))</li></ul>}</li><li class="src short"><span class="keyword">type</span> <a href="#t:Iter">Iter</a> = <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor-Identity.html#t:Identity">Identity</a></li><li class="src short"><a href="#v:iter">iter</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a) -> <a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a</li><li class="src short"><a href="#v:runIter">runIter</a> :: <a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a)</li><li class="src short"><a href="#v:delay">delay</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => m a -> m a</li><li class="src short"><a href="#v:hoistIterT">hoistIterT</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> n => (<span class="keyword">forall</span> a. m a -> n a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m b -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> n b</li><li class="src short"><a href="#v:liftIter">liftIter</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a</li><li class="src short"><a href="#v:cutoff">cutoff</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Prelude.html#t:Integer">Integer</a> -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#t:Maybe">Maybe</a> a)</li><li class="src short"><a href="#v:never">never</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => m a</li><li class="src short"><a href="#v:untilJust">untilJust</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a</li><li class="src short"><a href="#v:interleave">interleave</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => [<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a] -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m [a]</li><li class="src short"><a href="#v:interleave_">interleave_</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => [<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a] -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m ()</li><li class="src short"><a href="#v:retract">retract</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> m a</li><li class="src short"><a href="#v:fold">fold</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => (m a -> a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> a</li><li class="src short"><a href="#v:foldM">foldM</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> n) => (m (n a) -> n a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> n a</li><li class="src short"><span class="keyword">class</span> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="#t:MonadFree">MonadFree</a> f m | m -> f <span class="keyword">where</span><ul class="subs"><li><a href="#v:wrap">wrap</a> :: f (m a) -> m a</li></ul></li></ul></div><div id="interface"><h1>Documentation</h1><div class="doc"><p>Functions in Haskell are meant to be pure. For example, if an expression
has type Int, there should exist a value of the type such that the expression
can be replaced by that value in any context without changing the meaning
of the program.</p><p>Some computations may perform side effects (<code>unsafePerformIO</code>), throw an
exception (using <code>error</code>); or not terminate
(<code>let infinity = 1 + infinity in infinity</code>).</p><p>While the <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/System-IO.html#t:IO">IO</a></code> monad encapsulates side-effects, and the <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a></code>
monad encapsulates errors, the <code><a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a></code> monad encapsulates
non-termination. The <code><a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a></code> transformer generalizes non-termination to any monadic
computation.</p><p>Computations in <code><a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a></code> (or <code><a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a></code>) can be composed in two ways:</p><ul><li><em>Sequential:</em> Using the <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> instance, the result of a computation
can be fed into the next.</li><li><em>Parallel:</em> Using the <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:MonadPlus">MonadPlus</a></code> instance, several computations can be
executed concurrently, and the first to finish will prevail.
See also the <a href="examples/Cabbage.lhs">cabbage example</a>.</li></ul></div><h1 id="g:1">The iterative monad transformer</h1><div class="top"><p class="src"><span class="keyword">newtype</span> <a name="t:IterT" class="def">IterT</a> m a <a href="src/Control-Monad-Trans-Iter.html#IterT" class="link">Source</a></p><div class="doc"><p>The monad supporting iteration based over a base monad <code>m</code>.</p><pre><code><a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a></code> ~ <code>FreeT</code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor-Identity.html#t:Identity">Identity</a></code>
</pre></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:IterT" class="def">IterT</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div class="subs fields"><p class="caption">Fields</p><dl><dt class="src"><a name="v:runIterT" class="def">runIterT</a> :: m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))</dt><dd class="doc empty"> </dd></dl><div class="clear"></div></div></td></tr></table></div><div class="subs instances"><p id="control.i:IterT" class="caption collapser" onclick="toggleSection('i:IterT')">Instances</p><div id="section.i:IterT" class="show"><table><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-Trans-Class.html#t:MonadTrans">MonadTrans</a> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a></span> <a href="src/Control-Monad-Trans-Iter.html#line-209" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Error-Class.html#t:MonadError">MonadError</a> e m => <a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Error-Class.html#t:MonadError">MonadError</a> e (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-265" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Reader-Class.html#t:MonadReader">MonadReader</a> e m => <a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Reader-Class.html#t:MonadReader">MonadReader</a> e (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-231" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-State-Class.html#t:MonadState">MonadState</a> s m => <a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-State-Class.html#t:MonadState">MonadState</a> s (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-255" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Writer-Class.html#t:MonadWriter">MonadWriter</a> w m => <a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Writer-Class.html#t:MonadWriter">MonadWriter</a> w (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-237" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor-Identity.html#t:Identity">Identity</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-276" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-174" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-164" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-Fix.html#t:MonadFix">MonadFix</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-Fix.html#t:MonadFix">MonadFix</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-190" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Applicative.html#t:Applicative">Applicative</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-168" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Foldable.html#t:Foldable">Foldable</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Foldable.html#t:Foldable">Foldable</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-213" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Traversable.html#t:Traversable">Traversable</a> m) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Traversable.html#t:Traversable">Traversable</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-221" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Applicative.html#t:Alternative">Alternative</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-194" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:MonadPlus">MonadPlus</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-201" class="link">Source</a></td><td class="doc"><p>Capretta's <code>race</code> combinator. Satisfies left catch.</p></td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-exceptions-doc/html/Control-Monad-Catch.html#t:MonadThrow">MonadThrow</a> m => <a href="file:///usr/share/doc/libghc-exceptions-doc/html/Control-Monad-Catch.html#t:MonadThrow">MonadThrow</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-280" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-exceptions-doc/html/Control-Monad-Catch.html#t:MonadCatch">MonadCatch</a> m => <a href="file:///usr/share/doc/libghc-exceptions-doc/html/Control-Monad-Catch.html#t:MonadCatch">MonadCatch</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-284" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-IO-Class.html#t:MonadIO">MonadIO</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-IO-Class.html#t:MonadIO">MonadIO</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-270" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Cont-Class.html#t:MonadCont">MonadCont</a> m => <a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Cont-Class.html#t:MonadCont">MonadCont</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-273" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> m, <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Eq1">Eq1</a> m) => <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Eq1">Eq1</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-136" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> m, <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Ord1">Ord1</a> m) => <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Ord1">Ord1</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-142" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> m, <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Show1">Show1</a> m) => <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Show1">Show1</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-148" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> m, <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Read1">Read1</a> m) => <a href="file:///usr/share/doc/libghc-prelude-extras-doc/html/Prelude-Extras.html#t:Read1">Read1</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-156" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m, <a href="file:///usr/share/doc/libghc-semigroupoids-doc/html/Data-Semigroup-Traversable-Class.html#t:Traversable1">Traversable1</a> m) => <a href="file:///usr/share/doc/libghc-semigroupoids-doc/html/Data-Semigroup-Traversable-Class.html#t:Traversable1">Traversable1</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-225" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/libghc-semigroupoids-doc/html/Data-Functor-Apply.html#t:Apply">Apply</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-182" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/libghc-semigroupoids-doc/html/Data-Functor-Bind.html#t:Bind">Bind</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-186" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/libghc-semigroupoids-doc/html/Data-Semigroup-Foldable-Class.html#t:Foldable1">Foldable1</a> m => <a href="file:///usr/share/doc/libghc-semigroupoids-doc/html/Data-Semigroup-Foldable-Class.html#t:Foldable1">Foldable1</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Trans-Iter.html#line-217" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> (m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a)</span> <a href="src/Control-Monad-Trans-Iter.html#line-139" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Typeable-Internal.html#t:Typeable">Typeable</a> (* -> *) m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Typeable-Internal.html#t:Typeable">Typeable</a> * a, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Data.html#t:Data">Data</a> (m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))), <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Data.html#t:Data">Data</a> a) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Data.html#t:Data">Data</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a)</span> <a href="src/Control-Monad-Trans-Iter.html#line-440" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Ord.html#t:Ord">Ord</a> (m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a)</span> <a href="src/Control-Monad-Trans-Iter.html#line-145" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Text-Read.html#t:Read">Read</a> (m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Text-Read.html#t:Read">Read</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a)</span> <a href="src/Control-Monad-Trans-Iter.html#line-160" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Text-Show.html#t:Show">Show</a> (m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a))) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Text-Show.html#t:Show">Show</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a)</span> <a href="src/Control-Monad-Trans-Iter.html#line-152" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Monoid.html#t:Monoid">Monoid</a> a) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a)</span> <a href="src/Control-Monad-Trans-Iter.html#line-391" class="link">Source</a></td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:2">Capretta's iterative monad</h1><div class="top"><p class="src"><span class="keyword">type</span> <a name="t:Iter" class="def">Iter</a> = <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor-Identity.html#t:Identity">Identity</a> <a href="src/Control-Monad-Trans-Iter.html#Iter" class="link">Source</a></p><div class="doc"><p>Plain iterative computations.</p></div></div><div class="top"><p class="src"><a name="v:iter" class="def">iter</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a) -> <a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a <a href="src/Control-Monad-Trans-Iter.html#iter" class="link">Source</a></p><div class="doc"><p>Builds an iterative computation from one first step.</p><pre>runIter . iter == id</pre></div></div><div class="top"><p class="src"><a name="v:runIter" class="def">runIter</a> :: <a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Either.html#t:Either">Either</a> a (<a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a) <a href="src/Control-Monad-Trans-Iter.html#runIter" class="link">Source</a></p><div class="doc"><p>Executes the first step of an iterative computation</p><pre>iter . runIter == id</pre></div></div><h1 id="g:3">Combinators</h1><div class="top"><p class="src"><a name="v:delay" class="def">delay</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => m a -> m a <a href="src/Control-Monad-Trans-Iter.html#delay" class="link">Source</a></p><div class="doc"><p>Adds an extra layer to a free monad value.</p><p>In particular, for the iterative monad <code><a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a></code>, this makes the
computation require one more step, without changing its final
result.</p><pre>runIter (delay ma) == Right ma</pre></div></div><div class="top"><p class="src"><a name="v:hoistIterT" class="def">hoistIterT</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> n => (<span class="keyword">forall</span> a. m a -> n a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m b -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> n b <a href="src/Control-Monad-Trans-Iter.html#hoistIterT" class="link">Source</a></p><div class="doc"><p>Lift a monad homomorphism from <code>m</code> to <code>n</code> into a Monad homomorphism from <code><code><a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a></code> m</code> to <code><code><a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a></code> n</code>.</p></div></div><div class="top"><p class="src"><a name="v:liftIter" class="def">liftIter</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="Control-Monad-Trans-Iter.html#t:Iter">Iter</a> a -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a <a href="src/Control-Monad-Trans-Iter.html#liftIter" class="link">Source</a></p><div class="doc"><p>Lifts a plain, non-terminating computation into a richer environment.
<code><a href="Control-Monad-Trans-Iter.html#v:liftIter">liftIter</a></code> is a <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> homomorphism.</p></div></div><div class="top"><p class="src"><a name="v:cutoff" class="def">cutoff</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Prelude.html#t:Integer">Integer</a> -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#t:Maybe">Maybe</a> a) <a href="src/Control-Monad-Trans-Iter.html#cutoff" class="link">Source</a></p><div class="doc"><p>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.</p><p>The step where the final value is produced also counts towards the limit.</p><p>Some examples (<code>n ≥ 0</code>):</p><pre><code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> 0 _ ≡ <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:return">return</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#v:Nothing">Nothing</a></code>
<code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> (n+1) <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:return">return</a></code> ≡ <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:return">return</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#v:Just">Just</a></code>
<code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> (n+1) <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-Trans-Class.html#v:lift">lift</a></code> ≡ <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-Trans-Class.html#v:lift">lift</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:liftM">liftM</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#v:Just">Just</a></code>
<code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> (n+1) <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="Control-Monad-Trans-Iter.html#v:delay">delay</a></code> ≡ <code><a href="Control-Monad-Trans-Iter.html#v:delay">delay</a></code> . <code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> n
<code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> n <code><a href="Control-Monad-Trans-Iter.html#v:never">never</a></code> ≡ <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/GHC-OldList.html#v:iterate">iterate</a></code> <code><a href="Control-Monad-Trans-Iter.html#v:delay">delay</a></code> (<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:return">return</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#v:Nothing">Nothing</a></code>) <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/GHC-OldList.html#v:-33--33-">!!</a></code> n
</pre><p>Calling <code><code><a href="Control-Monad-Trans-Iter.html#v:retract">retract</a></code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="Control-Monad-Trans-Iter.html#v:cutoff">cutoff</a></code> n</code> is always terminating, provided each of the
steps in the iteration is terminating.</p></div></div><div class="top"><p class="src"><a name="v:never" class="def">never</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => m a <a href="src/Control-Monad-Trans-Iter.html#never" class="link">Source</a></p><div class="doc"><p>A computation that never terminates</p></div></div><div class="top"><p class="src"><a name="v:untilJust" class="def">untilJust</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => m (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a <a href="src/Control-Monad-Trans-Iter.html#untilJust" class="link">Source</a></p><div class="doc"><p>Repeatedly run a computation until it produces a <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#v:Just">Just</a></code> value.
This can be useful when paired with a monad that has side effects.</p><p>For example, we may have <code>genId :: IO (Maybe Id)</code> that uses a random
number generator to allocate ids, but fails if it finds a collision.
We can repeatedly run this with</p><pre><code><a href="Control-Monad-Trans-Iter.html#v:retract">retract</a></code> (<code><a href="Control-Monad-Trans-Iter.html#v:untilJust">untilJust</a></code> genId) :: IO Id
</pre></div></div><div class="top"><p class="src"><a name="v:interleave" class="def">interleave</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => [<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a] -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m [a] <a href="src/Control-Monad-Trans-Iter.html#interleave" class="link">Source</a></p><div class="doc"><p>Interleaves the steps of a finite list of iterative computations, and
collects their results.</p><p>The resulting computation has as many steps as the longest computation
in the list.</p></div></div><div class="top"><p class="src"><a name="v:interleave_" class="def">interleave_</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => [<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a] -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m () <a href="src/Control-Monad-Trans-Iter.html#interleave_" class="link">Source</a></p><div class="doc"><p>Interleaves the steps of a finite list of computations, and discards their
results.</p><p>The resulting computation has as many steps as the longest computation
in the list.</p><p>Equivalent to <code><code>void</code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:.">.</a></code> <code><a href="Control-Monad-Trans-Iter.html#v:interleave">interleave</a></code></code>.</p></div></div><h1 id="g:4">Consuming iterative monads</h1><div class="top"><p class="src"><a name="v:retract" class="def">retract</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> m a <a href="src/Control-Monad-Trans-Iter.html#retract" class="link">Source</a></p><div class="doc"><p><code><a href="Control-Monad-Trans-Iter.html#v:retract">retract</a></code> is the left inverse of <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-Trans-Class.html#v:lift">lift</a></code></p><pre><code><a href="Control-Monad-Trans-Iter.html#v:retract">retract</a></code> . <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-Trans-Class.html#v:lift">lift</a></code> = <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Function.html#v:id">id</a></code>
</pre></div></div><div class="top"><p class="src"><a name="v:fold" class="def">fold</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => (m a -> a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> a <a href="src/Control-Monad-Trans-Iter.html#fold" class="link">Source</a></p><div class="doc"><p>Tear down a <code>Free</code> <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> using iteration.</p></div></div><div class="top"><p class="src"><a name="v:foldM" class="def">foldM</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> n) => (m (n a) -> n a) -> <a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m a -> n a <a href="src/Control-Monad-Trans-Iter.html#foldM" class="link">Source</a></p><div class="doc"><p>Like <code><a href="Control-Monad-Trans-Iter.html#v:fold">fold</a></code> with monadic result.</p></div></div><h1 id="g:5">IterT ~ FreeT Identity</h1><div class="top"><p class="src"><span class="keyword">class</span> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a name="t:MonadFree" class="def">MonadFree</a> f m | m -> f <span class="keyword">where</span> <a href="src/Control-Monad-Free-Class.html#MonadFree" class="link">Source</a></p><div class="doc"><p>Monads provide substitution (<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#v:fmap">fmap</a></code>) and renormalization (<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:join">join</a></code>):</p><pre>m <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:-62--62--61-">>>=</a></code> f = <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:join">join</a></code> (<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#v:fmap">fmap</a></code> f m)</pre><p>A free <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> is one that does no work during the normalization step beyond simply grafting the two monadic values together.</p><p><code>[]</code> is not a free <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> (in this sense) because <code><code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:join">join</a></code> [[a]]</code> smashes the lists flat.</p><p>On the other hand, consider:</p><pre>data Tree a = Bin (Tree a) (Tree a) | Tip a
</pre><pre>instance <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> Tree where
<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:return">return</a></code> = Tip
Tip a <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:-62--62--61-">>>=</a></code> f = f a
Bin l r <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:-62--62--61-">>>=</a></code> f = Bin (l <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:-62--62--61-">>>=</a></code> f) (r <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:-62--62--61-">>>=</a></code> f)
</pre><p>This <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> is the free <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> of Pair:</p><pre>data Pair a = Pair a a
</pre><p>And we could make an instance of <code><a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a></code> for it directly:</p><pre>instance <code><a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a></code> Pair Tree where
<code><a href="Control-Monad-Trans-Iter.html#v:wrap">wrap</a></code> (Pair l r) = Bin l r
</pre><p>Or we could choose to program with <code><code><a href="Control-Monad-Free.html#v:Free">Free</a></code> Pair</code> instead of <code>Tree</code>
and thereby avoid having to define our own <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code> instance.</p><p>Moreover, <a href="Control-Monad-Free-Church.html">Control.Monad.Free.Church</a> provides a <code><a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a></code>
instance that can improve the <em>asymptotic</em> complexity of code that
constructs free monads by effectively reassociating the use of
(<code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#v:-62--62--61-">>>=</a></code>). You may also want to take a look at the <code>kan-extensions</code>
package (<a href="http://hackage.haskell.org/package/kan-extensions">http://hackage.haskell.org/package/kan-extensions</a>).</p><p>See <code><a href="Control-Monad-Free.html#v:Free">Free</a></code> for a more formal definition of the free <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a></code>
for a <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a></code>.</p></div><div class="subs minimal"><p class="caption">Minimal complete definition</p><p class="src">Nothing</p></div><div class="subs methods"><p class="caption">Methods</p><p class="src"><a name="v:wrap" class="def">wrap</a> :: f (m a) -> m a <a href="src/Control-Monad-Free-Class.html#wrap" class="link">Source</a></p><div class="doc"><p>Add a layer.</p><pre>wrap (fmap f x) ≡ wrap (fmap return x) >>= f
</pre></div></div><div class="subs instances"><p id="control.i:MonadFree" class="caption collapser" onclick="toggleSection('i:MonadFree')">Instances</p><div id="section.i:MonadFree" class="show"><table><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-List.html#t:ListT">ListT</a> m)</span> <a href="src/Control-Monad-Free-Class.html#line-141" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-comonad-doc/html/Control-Comonad-Trans-Identity.html#t:IdentityT">IdentityT</a> m)</span> <a href="src/Control-Monad-Free-Class.html#line-138" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/ghc-doc/html/libraries/transformers-0.4.2.0/Control-Monad-Trans-Maybe.html#t:MaybeT">MaybeT</a> m)</span> <a href="src/Control-Monad-Free-Class.html#line-135" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="Control-Monad-Free.html#t:Free">Free</a> f)</span> <a href="src/Control-Monad-Free-Class.html#line-286" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="Control-Monad-Free-Church.html#t:F">F</a> f)</span> <a href="src/Control-Monad-Free-Class.html#line-138" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor-Identity.html#t:Identity">Identity</a> (<a href="Control-Monad-Trans-Iter.html#t:IterT">IterT</a> m)</span> <a href="src/Control-Monad-Free-Class.html#line-276" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m, <a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Error-Class.html#t:Error">Error</a> e) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Error.html#t:ErrorT">ErrorT</a> e m)</span> <a href="src/Control-Monad-Free-Class.html#line-144" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Monoid.html#t:Monoid">Monoid</a> w) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Writer-Strict.html#t:WriterT">WriterT</a> w m)</span> <a href="src/Control-Monad-Free-Class.html#line-126" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Monoid.html#t:Monoid">Monoid</a> w) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Writer-Lazy.html#t:WriterT">WriterT</a> w m)</span> <a href="src/Control-Monad-Free-Class.html#line-123" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Cont.html#t:ContT">ContT</a> r m)</span> <a href="src/Control-Monad-Free-Class.html#line-120" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-State-Strict.html#t:StateT">StateT</a> s m)</span> <a href="src/Control-Monad-Free-Class.html#line-117" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-State-Lazy.html#t:StateT">StateT</a> s m)</span> <a href="src/Control-Monad-Free-Class.html#line-114" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-Reader.html#t:ReaderT">ReaderT</a> e m)</span> <a href="src/Control-Monad-Free-Class.html#line-111" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad.html#t:Monad">Monad</a> m) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="Control-Monad-Trans-Free.html#t:FreeT">FreeT</a> f m)</span> <a href="src/Control-Monad-Free-Class.html#line-294" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="Control-Monad-Trans-Free-Church.html#t:FT">FT</a> f m)</span> <a href="src/Control-Monad-Free-Class.html#line-106" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Monoid.html#t:Monoid">Monoid</a> w) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-RWS-Lazy.html#t:RWST">RWST</a> r w s m)</span> <a href="src/Control-Monad-Free-Class.html#line-132" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left">(<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Functor.html#t:Functor">Functor</a> f, <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f m, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Monoid.html#t:Monoid">Monoid</a> w) => <a href="Control-Monad-Trans-Iter.html#t:MonadFree">MonadFree</a> f (<a href="file:///usr/share/doc/libghc-mtl-doc/html/Control-Monad-RWS-Strict.html#t:RWST">RWST</a> r w s m)</span> <a href="src/Control-Monad-Free-Class.html#line-129" class="link">Source</a></td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:6">Examples</h1><div class="doc"><ul><li><a href="examples/MandelbrotIter.lhs">Rendering the Mandelbrot set</a></li><li><a href="examples/Cabbage.lhs">The wolf, the sheep and the cabbage</a></li></ul></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.16.1</p></div></body></html>
|