1. 13
  1. 4

    And, just like you have types of parser combinators for composite or primitive data types, you can also have a type of parser combinators for … parser combinators. You’ll find a nice exposition of this idea in:

    “Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?” in JFP ’98 by Chris Okasaki

    On the pragmatic side of things, that type of parser combinator is also the key approach behind coarsely and generically parsing many kinds of language syntax in comby (disclaimer: I’m the author of said tool).

    1. 1

      That’s definitely an interesting idea! Just thinking about functions of that sort of order is a mental workout. I haven’t read it carefully yet so maybe I don’t fully understand the consequences of using success and failure continuations, but wouldn’t using a mutable lazy type like OCaml’s Lazy.t be a bit more pragmatic? I never thought about using it for backtracking but I’ve implemented a lazy list to use as input for a streaming XML parser, maybe something similar could be used for backtracking too.

      Edit: I’ve heard about comby before but never ended up looking into it, it looks very nice! I’ll try using it for refactoring some code at work.

    2. 1

      and Meijer’s paper](https://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf) about parser combinators also mentions that we might want to return more than one result in cases where it makes sense, but but let’s keep things simple here.

      You’ve got a broken link/markdown there in the last paragraph.

      1. 1

        Whoops, thank you. Thought I was putting a footnote there but it turns out this markdown library doesn’t support them.

      2. 1

        Usually this involves consuming less-structured input and producing more-structured output. This is called parsing…

        Per this definition, how is e.g. the object indexing example parsing?

        >> const getNestedItem = (o) => o?.a?.b?.c;
        >> getNestedItem({ a: { b: { c: 1 } } })
        <- 1
        >> getNestedItem({})
        <- undefined

        What does “less structured” and “more structured” mean in this context?

        1. 2

          What I meant by that is more like “turning unknown data into known”, and IMO that example fits the definition because the nested item may or may not be there, depending on the object. In general though that’s more of a building block for constructing more useful parsers, and when you’re using some parser combinators along with it you could also decide to transform the data that it returns, or if it fails you could switch to parsing a different field or a different kind of object.