search

reazen / relude-parse

Monadic parsing with Relude
MIT License
36 stars 6 forks source link

Make list-producing parsers tail recursive #21

Open mlms13 opened 5 years ago

mlms13 commented 5 years ago

I know there's a comment in the code, but I figured I'd open a more official ticket since this will probably become an issue in Relude CSV (since parsing an 8000 line CSV file doesn't seem completely out of the question).

I was looking at the MonadRec stuff in PureScript, and I think it's very similar to the trampoline technique that I was porting from Scala to Reason. I may try to do something in Relude proper, which hopefully relude-parse will be able to benefit from.

andywhite37 commented 5 years ago

Yeah, exactly - I left all that stuff kind of unimplemented, b/c it looked like if we had MonadRec, we'd be able to more easily re-work all this stuff to be tail recursive.

Once we get there, we should check all the recursive functions in relude-parse and attempt to make them all tail-recursive.

andywhite37 commented 5 years ago

See relude issue reazen/relude#166 for MonadRec.

The key thing we need for relude-parse is the List.manyRec function, like here: https://github.com/purescript-contrib/purescript-string-parsers/blob/master/src/Text/Parsing/StringParser/Combinators.purs#L52-L53

List.manyRec: https://pursuit.purescript.org/packages/purescript-lists/4.0.1/docs/Data.List#v:manyRec