Admittedly, my non-termination case basically kicks in when the pure function returns bottom and might be resolved by being less strict at the risk of space leaks in the parser. The asymptotic issues arise from much more defensible use cases ala your enhanced sharing example, since I can share leaf level recognizers regardless of the pure annotation, if I don't care about the value that results.
As a parenthetical aside, by special casing 'many' and 'sepEndBy' I can implement all of the other parsec style combinators that make sense in an Applicative setting without any other form of recursion allowed in the GADT I construct from the grammar. You still need arbitrary recursion for user defined grammars, but the common grammar combinators can all be implemented by biting off those two cases, or just the latter if you want to be minimalist about it.
-Edward Kmett
On Tue, Jun 30, 2009 at 11:58 AM, Ross Paterson
<ross@soi.city.ac.uk> wrote:
On Tue, Jun 30, 2009 at 11:45:50AM -0400, Edward Kmett wrote:
> I've been burned by this myself as well. I also have a set of parser
> combinators that I've been working on that could currently greatly
> benefit from these asymptotically in some places and in the case of a
> bottom up monoidal parser I've been working with, the availability of
> these makes the difference between termination and non-termination
> in some cases.
Ah, but that's changing the meaning, which isn't what these are supposed
to be for.