Next FP Syd: Wednesday, 26 June, 2024
Jost Berthold
Mark Hopkins — Parsing permutation phrases
Records in Haskell, as in many other languages, allow fields to be specified in any order, as long as they don't appear more than once; a field may also be omitted. Is there a principled way to add a corresponding feature to a parser combinator library? We'd want a combinator that took parsers for each field and returned a parser for the whole record. It's important too that the resultant parser be reasonably efficient. We could use such a combinator also for XML, JSON, YAML, URL query parameters, and so on.
I'll walk us through the implementation from the paper and the modified versions existing in the Haskell ecosystem. These rely on lazy evaluation; I'll show how the technique can be adapted for languages with strict evaluation.