Search code examples
haskellparsec

Problems with Applicative-style Parsec


I have the following ADT:

type Program = [Expr]
data Expr =
    Num Int
    | Bool Bool
    | Binding String Expr
    deriving (Show)

Here's a parser for variable-binding expressions, of the form lhs is rhs.

binding :: Parser Expr
binding = do
    lhs <- word
    spaces
    string "is"
    spaces
    rhs <- expr
    return $ Binding lhs rhs

It works fine, but when I try to convert it into applicative style, it gives the wrong result.

binding :: Parser Expr
binding = Binding <$> word <* (spaces *> string "is" *> spaces) *> expr

Replacing *> with >> in the parenthesised portion didn't work either. What's the difference between these two implementations? Is there a combinator for composing two parsers and ignoring the result of both?

Trying to debug with Debug.trace didn't work either... Nothing was printed.

binding :: Parser Expr
binding = (\x y -> trace (show (x, y)) (Binding x y)) <$> word <* (spaces *> string "is" *> spaces) *> expr

The rest of the parser, for context:

word :: Parser String
word = many1 letter

expr :: Parser Expr
expr = binding <|> atom

program :: Parser Program
program = do
    spaces
    result <- many (expr <* spaces)
    return result

Solution

  • Your problem is that <$> and <*> etc. are left associative. This means that your line:

    binding = Binding <$> word <* (spaces *> string "is" *> spaces) *> expr
    

    will be interpreted as

    binding = (Binding <$> word <* (spaces *> string "is" *> spaces)) *> expr
    

    This means that it will parse and then ignore everything before the last expr. As @icktoofay said, you can write the intended version as:

    binding = Binding <$> word <* spaces <* string "is" <* spaces <*> expr
    

    and not need any parenthesis at all, because of the left associativity.