title: Parsing to Free Monads
body: <p>Say I have the following free monad:</p>
  
  <pre><code>data ExampleF a
    = Foo Int a
    | Bar String (Int -&gt; a)
    deriving Functor
  
  type Example = Free ExampleF  -- this is the free monad want to discuss
  </code></pre>
  
  <p>I know how I  can work with this monad, eg. I could write some nice helpers:</p>
  
  <pre><code>foo :: Int -&gt; Example ()
  foo i = liftF $ Foo i ()
  
  bar :: String -&gt; Example Int
  bar s = liftF $ Bar s id
  </code></pre>
  
  <p>So I can write programs in haskell like:</p>
  
  <pre><code>fooThenBar :: Example Int
  fooThenBar =
    do
      foo 10
      bar "nice"
  </code></pre>
  
  <p>I know how to print it, interpret it, etc. But what about parsing it?</p>
  
  <p>Would it be possible to write a parser that could parse arbitrary
  programs like:</p>
  
  <pre><code>foo 12
  bar nice
  foo 11
  foo 42
  </code></pre>
  
  <p>So I can store them, serialize them, use them in cli programs etc.</p>
  
  <p>The problem I keep running into is that the type of the program depends on which program is being parsed. If the program ends with a <code>foo</code> it's of
  type <code>Example ()</code> if it ends with a <code>bar</code> it's of type <code>Example Int</code>.</p>
  
  <p>I do not feel like writing parsers for every possible permutation (it's simple here because there are only two possibilities, but imagine we add
  <code>Baz Int (String -&gt; a)</code>, <code>Doo (Int -&gt; a)</code>, <code>Moz Int a</code>, <code>Foz String a</code>, .... This get's tedious and error-prone).</p>
  
  <p>Perhaps I'm solving the wrong problem?</p>
  
  <h3>Boilerplate</h3>
  
  <p>To run the above examples, you need to add this to the beginning of the file:</p>
  
  <pre><code>{-# LANGUAGE DeriveFunctor #-}
  
  import Control.Monad.Free
  import Text.ParserCombinators.Parsec
  </code></pre>
  
  <p><em>Note: I put up <a href="https://gist.github.com/4402caeedad10ff56e90" rel="nofollow">a gist containing this code</a>.</em></p>