A parser for a thing
Is a function from a string
To a list of pairs
Of strings and things. A parser for a thing
Is a function from a string
To a list of pairs
Of strings and things.If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
The question is capabilities. Either gives you an error result that might be useful. List gives you backtracking and, depending on your grammar, multiple parses. Maybe is like a weaker Either. Other monads might do other interesting things, but from the perspective of accepting strings satisfying a grammar, List is the choice that supports non-determinism.
(Laziness strongly recommended.)
The poem is not mine, I believe it is Conor McBride’s.
[1] https://myotherpants.com/tag/test-first/
[2] https://www.amazon.com/Programming-Haskell-Graham-Hutton/dp/...
But parser combinators build your final parser out of little bits, and sometimes those little bits might be something potentially ambiguous, like "any number of leading zeros followed by a number" which needs to parse "0" as no leading zeros and the number 0, but "00" as one leading zero and the number 0.
Non-deterministic parsers can easily blow out with backtracking much like careless recursive descent parsers, though.