Thoughts on monadic parsing

[chris-martin]

We keep track of advancement, fallibility, and atomicity in the types, resulting in seven different parser types. One thing I hadn't realized upfront when I started this is that traditional applicative/monadic style goes right out the window, for a few reasons:

• I suspect you'd be constantly casting up to get two parsers to be the same type to be able to <*> or >>= them (like the experience of lifting monad transformers, but worse)
• Move and AtomicMove are not Applicative, because they don't support pure.
• To make Atom be Applicative, the sequencing operations would have to implicitly add backtracking, and I'm not sure that's a great idea.

To get back the convenience of monadic parsing, I defined my own >>=, <*>, etc. operators that make use of the KindJoin type family.

type family KindJoin (k1 :: ActionKind) (k2 :: ActionKind) :: ActionKind

type a :> b = KindJoin a b -- its infix alias is convenient sometimes

The parser API then has a handful of functions like this that replace the standard Applicative and Monad ones:

(>>=) ::
    Monad m => IsAction k1 => IsAction k2 => IsAction k3 => ActionJoin k1 k2 => k1 :> k2 ~ k3 =>
    Parser text k1 m a -> (a -> Parser text k2 m b) -> Parser text k3 m b

This isn't so bad if we make use of the QualifiedDo extension introduced in GHC 9.0, which allows the built-in do syntax to use our custom (>>=) et al. operators instead of the standard functions.

One thing we lose is the ability to use all the standard Monad combinators (and Alternative ones too, though I haven't gotten to working on alternative choice yet). My suspicion is that this will not really be much of a loss, as it seems like many parsing libraries offer replacements for some of them anyway.