Using chainl1 correctly with infix in Haskell-CodePudding

For the MVE code below it outputs [] rather than the expected Not (Oper Eq 2 2)) for the input parseString "2 2" which is supposed to call pOper. My guess is that pOper would expect three arguments for the anonymous function to work. That is 3 strings. However due to partial call of a function only one argument is passed. Is there a way to work around to preserve the type signature of pOper while dealing with the Not and at the same time not changing the type definitions?

import Data.Char
import Text.ParserCombinators.ReadP
import Control.Applicative ((<|>))

type Parser a = ReadP a 

data Value =
  IntVal Int
  deriving (Eq, Show, Read)

data Exp =
    Const Value
  | Oper Op Exp Exp
  | Not Exp
  deriving (Eq, Show, Read)

data Op = Plus | Minus | Eq
  deriving (Eq, Show, Read)

space :: Parser Char
space = satisfy isSpace

spaces :: Parser String 
spaces = many space

space1 :: Parser String
space1 = many1 space

symbol :: String -> Parser String
symbol = token . string

token :: Parser a -> Parser a
token combinator = (do spaces
                       combinator)

parseString input = readP_to_S (do
                        e <- pExpr 
                        token eof
                        return e) input

pExpr :: Parser Exp 
pExpr = chainl1 pTerm pOper 


pTerm :: Parser Exp 
pTerm =    
    (do         
        pv <- numConst 
        skipSpaces       
        return pv)      
   
numConst :: Parser Exp
numConst = 
        (do  
            skipSpaces
            y <- munch isDigit            
            return (Const (IntVal (read y)))
        )

-- Parser for an operator
pOper :: ReadP (Exp -> Exp -> Exp)
pOper = symbol " " >> return (Oper Plus)
   <|> (symbol "-" >> return (Oper Minus))
   <|> (symbol "=" >> return (Oper Eq))
   <|> (symbol "!=" >> return (\e1 e2 -> Not (Oper Eq e1 e2)))

CodePudding user response：

The best way I can think of to solve the problem is by creating these to modificatoins: 1) this alternative in the expression

pExpr :: Parser Exp 
pExpr = 
    (do pv <- chainl1 pTerm pOper             
        pv2 <- pOper2 pv
        return pv2)  
    <|> chainl1 pTerm pOper

And 2) this helper function to deal with infix patterns

pOper2 :: Exp -> Parser Exp
pOper2 e1 = (do 
                symbol "!="
                e2 <- numConst
                return (Not (Oper Eq e1 e2)))

This is the output, althought I don't know if there will be problems if other operations such as / and * which has different associativety are to be taken into account as well.

parseString "2 4 6"
[(Oper Plus (Oper Plus (Const (IntVal 2)) (Const (IntVal 4))) (Const (IntVal 6)),"")]
ghci> parseString "2 4 6 != 2"
[(Not (Oper Eq (Oper Plus (Oper Plus (Const (IntVal 2)) (Const (IntVal 4))) (Const (IntVal 6))) (Const (IntVal 2))),"")]
ghci> parseString "2 != 4"
[(Not (Oper Eq (Const (IntVal 2)) (Const (IntVal 4))),"")]

CodePudding user response：

There's nothing wrong with your parser for !=. Rather, your parser for operators in general is broken: it only parses the first operator correctly. A simpler version of your pOper would be

pOper = a >> b
  <|> (c >> d)

But because of precedence, this isn't the same as (a >> b) <|> (c >> d). Actually, it's a >> (b <|> (c >> d))! So the symbol your first alternative parses is accidentally mandatory. It would parse 2 !=2 instead.

So, you could fix this by just adding in the missing parentheses. But if, like me, you find it a little tacky to rely so much on operator precedence for semantic meaning, consider something that's more obviously safe, using the type system to separate the clauses from the delimiters:

pOper :: ReadP (Exp -> Exp -> Exp)
pOper = asum [ symbol " " >> return (Oper Plus)
             , symbol "-" >> return (Oper Minus)
             , symbol "=" >> return (Oper Eq)
             , symbol "!=" >> return (\e1 e2 -> Not (Oper Eq e1 e2))
             ]

This way, you have a list of independent parsers, not a single parser built with alternation. asum (from Control.Applicative) does the work of combining that list into alternatives. It means the same thing, of course, but it means you don't have to learn any operator precedence tables, because , can only be a list item separator.