Stream: ideas

Topic: applicative parsing

Qqwy / Marten (Jul 07 2022 at 18:06):

Related to this: While writing the JSON parser, I've felt myself wanting to have something to use backpassing for a function of the signature Parser a -> Parser (a -> b) -> Parser b. (This would be 'apply' or <*> in Haskell)

The main reason this would be nice, is because it would allow idioms like e.g.:

betweenBraces : Parser a -> Parser a
betweenBraces = \parser ->
  _   <- apply char '['
  res <- apply parser
  _   <- apply char ']'
  res

Qqwy / Marten (Jul 07 2022 at 18:07):

It is possible up to a point to model this using andThen, (e.g. 'bind' or >>=), but it is needlessly powerful and will lead to code that is less flexible and that cannot be optimized as much: You can only get at the later parsers by running the earlier parsers using andThen.

Qqwy / Marten (Jul 07 2022 at 18:10):

There is one other alternative to do this, namely to use a pipeline instead of backpassing. This is what Elm uses (e.g. https://github.com/NoRedInk/elm-json-decode-pipeline ). However, it relies on partial application, which Roc does not have.

Brendan Hansknecht (Jul 07 2022 at 18:12):

why is the between braces examples not valid currently?

Brendan Hansknecht (Jul 07 2022 at 18:12):

What would you have to write today?

Qqwy / Marten (Jul 07 2022 at 18:14):

Because the syntax of apply has to be Parser a -> Parser (a -> b) -> Parser b, and backpassing currently only works with F x -> (a -> G b) -> G b.

Qqwy / Marten (Jul 07 2022 at 18:14):

so in this example Parser a -> (a -> Parser b) -> Parser b

Brendan Hansknecht (Jul 07 2022 at 18:17):

I definitely don't understand. Parser (a -> b) doesn't make sense to me. Feels like it should be: Parser a -> (a -> b) -> Parser b

Brendan Hansknecht (Jul 07 2022 at 18:17):

Anyway, probably shouldn't derail this chat with explanations of that. We can pull it to another chat if you want to explain.

Qqwy / Marten (Jul 07 2022 at 18:34):

Today, one would have to write:

betweenBraces : Parser a -> Parser a
betweenBraces = \parser ->
  char '['
  |> apply (parser |> map (\res -> \_ -> res))
  |> apply (char ']' |> map (\_ -> \res -> res))

Qqwy / Marten (Jul 07 2022 at 18:46):

Or I guess, using a version that has the arguments reversed:

betweenBraces2 : Parser a -> Parser a
betweenBraces2 = \parser ->
  const (\_ -> \val -> \_ -> val)
  |> applyRev (scalar '[')
  |> applyRev parser
  |> applyRev (scalar ']')

(Note the required explicit currying)

Richard Feldman (Jul 07 2022 at 19:56):

You can only get at the later parsers by running the earlier parsers using andThen.

I think this is true of parsers anyway, yeah? Like the result of the later parsing steps depend on knowing how much the previous steps consumed, so they're blocked on it regardless

Richard Feldman (Jul 07 2022 at 20:01):

an API I think would be nice for general parsing would be something similar to elm/parser but with drop and keep functions instead of infix operators:

betweenBraces : Parser a -> Parser a
betweenBraces = \parser ->
    _ <- Parser.drop (Parser.char '[')
    x <- Parser.keep parser
    _ <- Parser.drop (Parser.char ']')

    Parser.succeed x

drop : Parser *, ({} -> Parser b) -> Parser b

keep : Parser a, (a -> Parser b) -> Parser b

Qqwy / Marten (Jul 07 2022 at 20:14):

Richard Feldman said:

You can only get at the later parsers by running the earlier parsers using andThen.

I think this is true of parsers anyway, yeah? Like the result of the later parsing steps depend on knowing how much the previous steps consumed, so they're blocked on it regardless

The parse results of later parsers depend on how much earlier parsers consumed. But the parsers themselves do not.

Having access to them without running them has many benefits.
Three immediately come to mind:

• Better error messages
• Being able to print the grammar a parser recognizes.
• Possibly re-use parsers as pretty-printers (c.f. https://www.informatik.uni-marburg.de/~rendel/unparse/)

Richard Feldman (Jul 07 2022 at 20:42):

Better error messages

interesting - do you mean the parser itself could produce better error messages if it fails to parse something?

Richard Feldman (Jul 07 2022 at 20:45):

separately, I'm not sure what an equivalent of Haskell's applicative do would look like as syntax sugar (e.g. without involving higher-kinded types, the way a chain keyword could) :big_smile:

Qqwy / Marten (Jul 07 2022 at 20:52):

Richard Feldman said:

Better error messages

interesting - do you mean the parser itself could produce better error messages if it fails to parse something?

Exactly!

Qqwy / Marten (Jul 07 2022 at 20:53):

Richard Feldman said:

separately, I'm not sure what an equivalent of Haskell's applicative do would look like as syntax sugar (e.g. without involving higher-kinded types, the way a chain keyword could) :big_smile:

Yeah... I do not have a clear idea at this time either! :sweat_smile:
But I'll definitely think about it, because it seems very worthwhile.

Last updated: Jun 16 2026 at 16:19 UTC