proposal #3335: make some Applicative functions into methods, and split off Data.Functor

Edward Kmett ekmett at
Tue Jun 30 16:01:07 EDT 2009

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 at> 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.
>  _______________________________________________
> Libraries mailing list
> Libraries at
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Libraries mailing list