search

mrkkrp / parser-combinators

Lightweight package providing commonly useful parser combinators
Other
52 stars 15 forks source link

Control.Applicative.Permutations doesn't work with Applicative-only parsers #33

Closed chowells79 closed 3 years ago

chowells79 commented 3 years ago

Control.Applicative.Permutations.runPermutation requires that the parser type be a Monad for performance. This is highly surprising when Control.Applicative.Combinators, in contrast, is willing to make some performance sacrifices in order to stay compatible with parsers with no Monad instance.

This isn't a purely theoretical concern. Unless I really need context-sensitivity, I like the Earley package because I don't need to work around the expressiveness limits in the parsec family of libraries. Because the Earley algorithm is restricted to context-free grammars, it doesn't provide a Monad instance for its Prod type. (It provides a Grammar type with a Monad instance, but don't let that distract. That type doesn't have an Alternative instance, as it's not actually a parsing type. It's only there as a tool for observable sharing.)

The original paper the module documentation links to provides an algorithm that doesn't need a Monad instance. It would be consistent with the way the other Applicative/Monad modules split if this module didn't require the Monad instance either. And it would make Control.Applicative.Permutations work with Earley.

mrkkrp commented 3 years ago

cc @recursion-ninja

recursion-ninja commented 3 years ago

@chowells79 , you are correct that reworking the interface to only require an Applicative instance would be both a technical and theoretical improvement. Originally, I had some trouble not using a monadic operator at one point (I don't remember where) and I was under some time pressure to just get it done. Unfortunately, over that intervening two years I never took the time to review and remunerate the technical debt. This is a good call to action.

Redefining the interface of the Permutations module to only require an Applicative interface shouldn't be too difficult; just requiring a bit of time for research, implementation, and testing. I hope to be able to make time this week to look into this interface issue. However, I do have many other commitments in my life right now that superseding this work. If I haven't opened a pull request referencing this issue in 2 weeks time, please ping this issue to remind me so it doesn't fall through the cracks again for two more years.