Mapping with parsers

⇐ Notes archive

(This is an entry in my technical diary. There will likely be typos, mistakes, or wider logical leaps — the intent here is to “[let] others look over my shoulder while I figure things out.”)

The first exercise from Point-Free episode #126 felt familiar. It asks the viewer to extend Parser with a placeholder-named method, f, which accepts another parser from Output to a possibly different output, NewOutput, to then return a parser of type Parser<Input, NewOutput>.

Behind the nominal garnish, a Parser is a function from (inout Input) -> Output?. So, it checks out that we can tee up parsers as long as their outputs and inputs match — the tricky bit is rolling back any modifications to the Input argument, if the first parsing succeeds and the second fails:

extension Parser {
  func f<NewOutput>(
    _ parser: Parser<Output, NewOutput>
  ) -> Parser<Input, NewOutput> {
    .init { input in
      let original = input

      guard var firstOutput = self.run(&input) else { return nil }
      guard let secondOutput = parser.run(&firstOutput) else {
        input = original
        return nil
      }

      return secondOutput
    }
  }
}

We’re lifting a Parser<Input, Output> to a Parser<Input, NewOutput> with the help of a Parser<Output, NewOutput>. Or in prose, we’re mapping a parser with a parser‽

Sans the inout rollback dance, this situation is almost the same as CasePath.appending(path:) (.. in operator form). CasePath.extract’s (Root) -> Value? shape is Parser.run’s immutable analog. Which hints that we can lift a case path into a parser.

import CasePaths

extension Parser {
  init(_ path: CasePath<Input, Output>) {
    self.init { path.extract(from: $0) }
  }
}

Parsing and case paths (prisms) appear linked in ways I have a feeling Jasdev-a-couple-of-years-from-now will better grok slash be too-hyped about and to get there, I’ll probably need to watch Fraser Tweedale’s ‌Unified Parsing and Printing with Prisms a few more times. It’s exciting that their approach seems to ease the partial isomorphism requirement proposed section 3.1 of the original Invertible Syntax Descriptions paper (e.g. a request parser doesn’t necessarily need to make a round trip when printing back the result of its parsing phase — a scenario that comes mind is an incoming request with unparsed query parameters getting nixed on the printing phase of the round trip).