From parsing operators to methods

Updates:

11/19/20:

Stephen and I chatted about the reasoning behind the <%> symbol choice (instead of overloading the <*> operator like in the original invertible syntax descriptions paper).

It comes down to the authors using <*> in both a left- and right-associative manner, which isn’t possible in Swift and why swift-prelude split out its apply operators. Having a single operator with both associativities allows for the same expression to be used in printing and parsing (snippet from section 3.2).

A sign of personal growth I’ve used while learning functional programming over the years is noticing when I grok types — in this case, custom operators — that previously felt out of reach. And recently, Point-Free’s older parsing operators: <%>, <%, %>, and <|> clicked after the duo rewrote them as methods in episodes #120 and 123.

Let’s step through each:

<%>

<%>’s new name is Parser.take(_:). The shape hints at its meaning by having both less-than and greater-than signs indicating that the outputs of both operands are paired (further suggesting how <% and %> behave).

parserOfA <%> parserOfB returns a Parser<Input, (A, B)>.

Brandon and Stephen probably chose the percentage symbol since the operator used in the original paper on invertible syntax descriptions is <*>, which is often reserved for applicative sequential application.

<%

As you probably guessed, <% zips two parsers and discards the result of the righthand one. Or as methods, these two Parser.skip(_:) overloads (the latter is used to skip over the first parser in a zipped chain).

%>

Conversely, %> discards the left and keeps the righthand result. What’s wicked is that the combinator methods can express this without a new name and instead as an overload on take constrained to Parser.Output == Void.

extension Parser where Output == Void {
  func take<A>(_ p: Parser<Input, A>) -> Parser<Input, A> {
    zip(self, p).map { _, a in a }
  }
}

<|>

Last up is the cousin of the previous three, the analog to Parser.oneOf(_:).

Akin to how Boolean ORs (||) short-circuit once a true value is evaluated, the <|> shape signals that the combinator will run each operand in order and stop when one parses successfully.

The operator both mirrors the original form in the previously-linked paper and follows suit with the Alternative typeclass requirement¹ from Haskell’s Prelude.

Hopefully this note can serve as a reference for folks reading through the router behind pointfree.co until it’s updated with the method forms of these parser combinators.