Not stack safe

[nwolverson]

A simple parser like many (string "a") will fail on an input of size 3000.

Due to lack of general TCO - not sure if it's inherent in the continuation based design of the Parser type or just the mutual recursion of things like many/many1 and similar.

[paf31]

Hmm, I'm not sure if it's possible to get TCO given the CPS approach, as you say. I used CPS to be able to exit early in case of failure, but perhaps it's not worth it, and we should measure the performance difference.

[nwolverson]

Do you have an idea what would be a good example where "early exit" should work well? I've put together a version using a basic Parser a = PosString -> Either Failure (Success a), for a tail recursive many success and failure cost the same (with purescript-parsing version much slower)


didn't really see a difference on a non-tailrec case

...backtracking with try?

[paf31]

Thanks for the analysis! Yes, I think the CPS approach shines when there is a lot of backtracking, since you don't have to pay for a bunch of unnecessary binds, but of course, you lose the tail recursive property 😢

[paf31]

The latest version uses your Parser a = PosString -> Either Failure (Success a) model. Would you be interested in implementing many etc. in terms of the new MonadRec instance? (I think it should be possible)

[nwolverson]

Sure, I'll have a look