If you use an Either instead of a List, then you can write an or combinator, which accepts two parsers and tries the second if the first fails. It branches on the Left/Right of the Either.
replyIf it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
You’re going to write a monad and alternative instance for whatever structure you use. A list is a Cartesian product, but that’s just the join of parser B over each remaining input of parser A, it’s still a one-liner.
replyThe 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.