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.

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.