Grammar issues in haskell with data definitions

Question

I'm attempting to implement a grammar in haskell using the parsec library but I'm having issues with expected Vs. actual types as defined in the grammar, I know the answer to my question is no doubt simple/obvious but alas there is something I'm not understanding...

An excerpt of data declaration follows (should be sufficient to diagnose):

data Expr1 = SeqOfExpr1 [Expr1]
            | Lambda Expr8 Expr1
            | List Expr2 Expr1
            | If Expr2 Expr1 Expr1
            | Expr2
              deriving (Show)

data Expr2 =  SeqOfExpr3 [Expr3]
              deriving (Show)

data Expr3 =  SeqOfExpr4 [Expr4]
              deriving (Show)
 ----------------------------Redundant Code Omitted------------------------------
expr1 :: Parser Expr1   
expr1 = declaration
      <|> list
      <|> ifStmt
      <|> expr2

declaration :: Parser Expr1
declaration =
    do  reservedOp "\\"
        var <- name
        reservedOp "->"
        expr <- expr1
        return $ Lambda var expr

list :: Parser Expr1    
list =
    do exprA <- expr2
       reservedOp ":"
       exprB <- expr1
       return $ List exprA exprB

Now there are further data declarations for expressions down to Expr8 but they are much the same as expr2 -> expr3 the different between them is how they are delimited e.g. Expr3's are delimited by "||", Expr4's by "&&" etc.

One of issues I'm having (which if solved should provide me with the idea to fix the rest):

The List value constructor returns an Expr1 which causes a conflict:

Couldn't match expected type `Expr2' with actual type `Expr1'
In the first argument of `List', namely `exprA'
In the second argument of `($)', namely `List exprA exprB'
In a stmt of a 'do' block: return $ List exprA exprB

I think it's because I'm using Expr2 as a value declaration in Expr1 but I'm not sure how to correct the grammar to solve this issue.

Thanks in advance for any help!

Sean

Answer 1

In data Expr1, you have a nullary constructor Expr2. I suspect you meant that to be something like

data Expr1 =
           ...
           | Foo Expr2

to wrap an Expr2.

Anyway, as per

expr1 :: Parser Expr1   
expr1 = declaration
      <|> list
      <|> ifStmt
      <|> expr2

the compiler infers expr2 :: Parser Expr1, but when you try

list :: Parser Expr1    
list =
    do exprA <- expr2
       reservedOp ":"
       exprB <- expr1
       return $ List exprA exprB

the type of List means exprA must be an Expr2, but from expr2's type, the compiler knows exprA :: Expr1.

So you probably need to wrap expr2 in list,

list = ...
     <|> fmap Foo expr2

if you change the definition of Expr1 to include a Foo constructor to wrap an Expr2.