Notably, you hardly ever need Monadic parser combinators. Applicative parser combinators work fine in almost all cases.

FastParse lets you use parser combinators monadically, but that's only necessary in uncommon cases. The three I've come across are length + data-of-length constructs (more common in binary parsing than text), having your parser validate matched XML tags/closing-tags, and indentation-delimited-block parser (e.g. when parsing Python).

For the vast majority of programming-language-like things, Applicative parser combinators are enough, including languages with complex syntax such as Scala.

Hm? I don't see why these would have to be monadic. A simple

    type Parser t = Input -> Maybe (t, Input)

or similar would be enough? Simple function composition gets you the rest of the way. (I grant you, it might be a bit tedious to write parsers this way, and monadic notation certainly makes it more pleasant in most cases.)

For anyone following along at home: think function which takes input + current position and may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input".

(Obviously it'd have to be expanded to support errors properly, etc.)

EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?

Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.

It's only a monad if you define it to be. It's also "just" an applicative if you like. The monadic part arises when people actually _use_ bind and then you lose some information that might be nice for optimizations.

> In slightly fancy language the type you just wrote is just StateT Input Maybe.

Except the newtype -- which was kind of my point :).

I realize I misread parent comment functions:

  always<A>(x: A): Parser<A>
  thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<(A, B)>

as:

  always<A>(x: A): Parser<A>
  thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<B>

which would make a monad provided the monad laws are satisfied.

Of course you don't have to write parser combinators that way, but I found it pretty practical compared to dealing with nested tuples for the sequence parser. Check out Hutton and Meijer's article for more details.

The problem with monadic parsers is that they are too powerful. If you have two options

    string "foo" <|> string "for"

It would be nice to automatically rewrite this as

    string "fo" >> (char 'o' <|> char 'r')

But if we try to analyze monadic parsers like that we run into the halting problem.

Applicative parsers are less powerful so we can left factor them automatically. There were some attempts to combine applicative and monadic parsers which resulted in arrow syntax but that kind of feels like the worst of both worlds for many cases.