title: Making attoparsec parsers recursive
body: <p>I've been coding up an attoparsec parser and have been hitting a pattern where I want to turn parsers into recursive parsers (recursively combining them with the monad bind >>= operator).</p>
  
  <p>So I created a function to turn a parser into a recursive parser as follows:</p>
  
  <pre><code>recursiveParser :: (a -&gt; A.Parser a) -&gt; a -&gt; A.Parser a
  recursiveParser parser a = (parser a &gt;&gt;= recursiveParser parser) &lt;|&gt; return a
  </code></pre>
  
  <p>Which is useful if you have a recursive data type like</p>
  
  <pre><code>data Expression = ConsExpr Expression Expression | EmptyExpr
  
  parseRHS :: Expression -&gt; Parser Expression
  parseRHS e = ConsExpr e &lt;$&gt; parseFoo
  
  parseExpression :: Parser Expression
  parseExpression = parseLHS &gt;&gt;= recursiveParser parseRHS
    where parseLHS = parseRHS EmptyExpr
  </code></pre>
  
  <p>Is there a more idiomatic solution? It almost seems like <code>recursiveParser</code> should be some kind of fold...  I also saw <code>sepBy</code> in the docs, but this method seems to suit me better for my application.</p>
  
  <p><strong>EDIT:</strong> Oh, actually now that I think about it should actually be something similar to <code>fix</code>... Don't know how I forgot about that.</p>
  
  <p><strong>EDIT2:</strong> Rotsor makes a good point with his alternative for my example, but I'm afraid my AST is actually a bit more complicated than that. It actually looks something more like this (although this is still simplified)</p>
  
  <pre><code>data Segment = Choice1 Expression
               | Choice2 Expression
  data Expression = ConsExpr Segment Expression 
                  | Token String
                  | EmptyExpr
  </code></pre>
  
  <p>where the string <code>a -> b</code> brackets to the right and <code>c:d</code> brackets to the left, with <code>:</code> binding more tightly than <code>-></code>.</p>
  
  <p>I.e. <code>a -> b</code> evaluates to </p>
  
  <pre><code>(ConsExpr (Choice1 (Token "a")) (Token "b"))
  </code></pre>
  
  <p>and <code>c:d</code> evaluates to</p>
  
  <pre><code>(ConsExpr (Choice2 (Token "d")) (Token "c"))
  </code></pre>
  
  <p>I suppose I could use <code>foldl</code> for the one and <code>foldr</code> for the other but there's still more complexity in there. Note that it's recursive in a slightly strange way, so <code>"a:b:c -> e:f -> :g:h ->"</code> is actually a valid string, but <code>"-> a"</code> and <code>"b:"</code> are not. In the end <code>fix</code> seemed simpler to me. I've renamed the recursive method like so:</p>
  
  <pre><code>fixParser :: (a -&gt; A.Parser a) -&gt; a -&gt; A.Parser a
  fixParser parser a = (parser a &gt;&gt;= fixParser parser) &lt;|&gt; pure a
  </code></pre>
  
  <p>Thanks.</p>