[Haskell-cafe] Parsec combinator like Prolog's cut operator?

Ivan Lazar Miljenovic ivan.miljenovic at gmail.com
Wed Jun 30 03:25:12 EDT 2010

Stephen Tetley <stephen.tetley at gmail.com> writes:

> Hi Erik
> Malcolm Wallace describes a commit combinator in the paper "Partial
> parsing: combining choice with commitment" which sounds like what you
> would want. It is implemented for Polyparse rather than Parsec though.
> From a quick scan of the paper and code, the implementation appears to
> be built into the Parser type, so it is a primitive rather than a
> definable combinator.

>From the Polyparse homepage (http://www.cs.york.ac.uk/fp/polyparse/):

| If you are familiar with the Parsec library, then the key insight for
| using PolyParse is that the two libraries' approach to backtracking
| are the duals of each another. In Parsec, you must explicitly add a
| try combinator at any location where backtracking might be
| necessary. Users often find this a bit of a black art. In PolyParse by
| contrast, all parsers are backtracking unless you explicitly add a
| commit (or one of its variations). It is easy to tell where to add a
| commit point, because you have already parsed enough of a data
| structure to know that only one outcome is possible. For instance, if
| you are parsing a Haskell value produced by 'show', then as soon as
| you have parsed the initial constructor, you know that no other
| constructor of that datatype is possible, so you can commit to
| returning it.

Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com

More information about the Haskell-Cafe mailing list