[Haskell-cafe] Higher-order algorithms

Serguey Zefirov sergueyz at gmail.com
Mon Aug 23 09:39:53 EDT 2010

2010/8/23 Eugene Kirpichov <ekirpichov at gmail.com>:
> For example, parser combinators are not so interesting: they are a
> bunch of relatively orthogonal (by their purpose) combinators, each of
> which is by itself quite trivial, plus not-quite-higher-order
> backtracking at the core.

This is only if you're not quite considering generalizing parser
combinators to non-backtracking algorithms.

The CYK algorithm [1] does not backtrack, it merges partial parsing results.

When I thought about it I figured that parser combinators became even
more restricted that they in arrow parsers.

[1] http://en.wikipedia.org/wiki/CYK_algorithm

CYK is interesting because it provides parallel parsing opportunities,
it can parse many parts of text in parallel and then merge bags of
successful parsings into another successful parsings. As CYK does not
care about start of sequence it was used to parse grammars on
hypergraphs: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
I didn't thought fully about CYK parser combinators yet. But I think
that CYK could be an example of something unusual in the accustomed
field of parsing.

More information about the Haskell-Cafe mailing list