Why does this Parsec parser enter an infinite loop?

Question

The following parser enters an infinite loop for any input.

data Ast
    = Number Int
    | Identifier String
    | Operation Ast BinOp Ast
    deriving (Show, Eq)

data BinOp = Plus | Minus
    deriving (Show, Eq, Enum)

number = Number <$> read <$> many1 digit

identifier = Identifier <$> many1 letter

operator = choice $ mkParser <$> [(Plus, '+'), (Minus, '-')]
  where mkParser (f, c) = f <$ char c

operation = Operation <$> ast <*> operator <*> ast

ast :: Parser Ast
ast = operation <|> number <|> identifier

The problem is somewhere in the operation parser. I assume it's related to the alternate parsing but I don't understand it.

Can you explain what the problem is?

Thanks!

Answer 1

Problem is really in infinite recursion. Your ast parser calls operation parser first. But then operation parser calls ast back again. And so on. <*> operator for parsing also runs parsers. Explanation of difference from <|> in very informal manner: <*> runs parsers in sequence one by one whether <|> runs first parser and only if it fails runs second.

operation = Operation <$> ast <*> operator <*> ast
ast       = operation <|> number <|> identifier

Basically, even with rearranging parsers your approach won't work. See this answer on similar question for explanation: Megaparsec: Not able to parse arithmetic string