Can't parse function application with megaparsec

Learn
#1

Hello. I am having issues with my parser combinators in this code: Haskell Playground
(You can change the input binding to test out the parser)
The issue is that I am unable to parse function application:

ghci> parseTest (recexpr 0 <* eof) "let x = \\x -> x + 1 in x 1"
1:26:
  |
1 | let x = \x -> x + 1 in x 1
  |                          ^
unexpected '1'
expecting end of input, symbol, or white space

I believe the issue here is that appP's left <- absP always expects an abstraction as the LHS of an application, while in this situation, it is a Var.
I have tried to replace it with left <- parens absP <|> varP, but it errors in a different place here:

ghci> parseTest (recexpr 0 <* eof) "let x = \\x -> x + 1 in x 1"
1:17:
  |
1 | let x = \x -> x + 1 in x 1
  |                 ^^^^^
unexpected "+ 1 i"
expecting "false", "let", "true", '"', '(', '\', alphanumeric character, integer, or white space

Seemingly because it parses x + 1 as an application, and it doesn’t let the pratt parsing recexpr do it’s job of parsing operators?
So I had the thought process of “maybe, if I make valP do ... <|> try appP <|> ... instead of ... <|> appP <|> ... so that it backtracks, recexpr would get to the binary operators before appP,” and I tried to change the code for that, but I think that’s a dead end.

#2

You should expect the “function” to be an arbitrary expression. Here are some examples:

(f x) y — the function is all of (f x), itself yet another app. Furthermore, we take function application to be left-associative, so you would also need to support:

f x y — the function is all of f x. At this point you may as well just use chainl1 because you’re parsing a left-associative operator even though it looks empty.

(f . g) y — the function is (f . g), when one day you support a function composition operator.

(f + g) y — In some mathy languages, you need to support this too. Even if not, type checking is not part of parsing, you must support arbitrary expressions for what’s at the function position.

(if foo then (\x → x + 1) else (\x → x - 1)) y — one day you will support if-then-else and nothing says I can’t do this.

#3

Thanks for the advice. I think the change here would be

appP :: Parser Expr
appP = do
  left <- parens (recexpr 0) <|> varP
  rightOpt <- lexeme (recexpr 0)
  pure $ App left rightOpt

but that still errors. Any clue how to fix the problem that I outlined in the original post?

I plan to make many improvements about the semantics and how everything is handled, and I do appreciate the advice, but as of right now I’m just trying to get a minimum viable project working.

#4

The trouble with Megaparsec (and the original Parsec) is that it won’t backtrack automatically. This can be useful for better error messages, if you know what you’re doing, but it can also confuse beginners. In your case, the problem is that appP can fail after consuming the LHS. That means you need to demand backtracking: <|> try appP.

Another problem with Megaparsec is that it doesn’t support left recursion. Your idea left <- parens (recexpr 0) <|> varP above won’t cover all possible applications like a b c. You can instead use the chainl operator.