[Haskell-cafe] Higher-order algorithms

[Serguey Zefirov]

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

PS
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=10.1.1.47.6425
PPS
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.