Luke pretty much nailed the summary of what you can parse using Applicative means. I tend to consider them "codata CFGs", because they can have infinite breadth and depth. However, a 'codata CFG' can handle a much larger class of languages than CFGs. To that end, it is interesting to consider that to maximize the ability to successfully parse such degenerate grammars you are well served to use a traversal that can handle both of those cases. Such a traversal can be built out of Luke's Omega monad or a logic monad with fair conjunction/disjunction and provides a straightforward if inefficient 'top-down' parser.<div>
<div><div><div><br></div><div><a href="http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html">http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html</a></div>
<div><br></div><div><a href="http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html"></a>On the other hand, I've had greater success by working with Applicatives to build a CFG with 'pure' nodes represented as epsilons, using evil StableName hackery to build bottom up parsers. Although, for that to work you basically need to give up the ability to encode arbitrary "codata CFGs" in order to let the grammar finish compiling. This limits my approach to handling true CFGs (or TIGs), with an extension that covers TAGs, but lets me build a much more efficient parser.<br>
<div><br></div><div>And yes, one of the major motivating ideas behind Arrows were the parsers of Swierstra and Duponcheel (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2446">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2446</a>).</div>
<div><br></div><div>There are also compromise approaches. For instance Swierstra's uu-parsinglib internally uses both a monadic and applicative parser and a by virtue of a special bind operation that can glue them together yields a monad that can at least optimize the last run of applicative computations. </div>
<div><br></div><div><a href="http://www.cs.uu.nl/wiki/bin/view/HUT/ParserCombinators">http://www.cs.uu.nl/wiki/bin/view/HUT/ParserCombinators</a></div><div><br></div><div>-Edward Kmett</div><div><br><div class="gmail_quote">
On Thu, Jan 28, 2010 at 6:22 PM, Sebastian Fischer <span dir="ltr"><<a href="mailto:sebf@informatik.uni-kiel.de">sebf@informatik.uni-kiel.de</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">
On Jan 28, 2010, at 9:31 PM, Luke Palmer wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I don't remember the name, but there is a technique where you compose<br>
the features you want and then take its fixed point to get your AST.</blockquote></div>
Did you think of "Data types à la carte" by Wouter Swierstra?<br>
<a href="http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf" target="_blank">http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf</a></blockquote><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
You can make a typeclass for each feature that uses it on any data<br>
structure in which it is present.<br>
</blockquote>
<br></div>
I don't fully understand this sentence but it reminds me of "Finally Tagless, Partially Evaluated" by Jacques Carette, Oleg Kiselyov and Chung-chieh Shan:<br>
<a href="http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf" target="_blank">http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf</a></blockquote><div><br></div><div>Actually, it is quite the opposite of the Kiselyov Carette and Shan trick. interpreting an ADT is an initial algebraic construction, while the "Finally Tagless" is a final coalgebraic construction.</div>
<div><br></div><div>-Edward Kmett</div></div></div></div></div></div></div>