Boolean Expression evaluation . Couldn't match expected type

Question

I am trying to write an evaluator for a Boolean expression . Here type of evalAExp :: AExp-> Maybe Int (i.e. Arithmetic expression evaluator). Arithmetic evaluator is working for me.

In Boolean Evaluator I want the type to be :: BExp -> Bool. While compiling I get an error like Couldn't match expected type ``Bool' with actual type ``BExp' In the pattern: Eq a1 a2 In an equation for ``evalBExp': evalBExp (Eq a1 a2) = evalAExp (a1) == evalAExp (a2)

The end types of a BExp should be Bool.

How should I be declaring my BExp in this case. Is there a better way of going about it.

data BExp = Eq AExp AExp | Lt AExp AExp | Gt AExp AExp | ELt AExp AExp| EGt AExp AExp | And BExp BExp | Or BExp BExp | Bool

evalBExp True = True
evalBExp False = False
evalBExp (Eq a1 a2) = evalAExp (a1) == evalAExp (a2)

Here in evalBExp (Eq a1 a2) = evalAExp (a1) == evalAExp (a2) I am comparing Just Int == Just Int and the resultant is a Bool. What should I be doing? I think there is a problem in the data BExp declaration itself for me.

Any Help

EDIT :

I changed my code to something like this.

data BExp = Eq AExp AExp | Lt AExp AExp | Gt AExp AExp | ELt AExp AExp| EGt AExp AExp | And BExp BExp | Or BExp BExp |Boolean Bool

evalBExp (Boolean True) = True
evalBExp (Boolean False) = False
evalBExp (Eq a1 a2) = (evalAExp (a1)) == (evalAExp (a2))

So I changed the type to Boolean Bool. Is this a better way of declaring a type . Why not simply Bool as earlier. Is there a better way to do this.

Entire Code

import qualified Data.Map as M
import Data.List
data AExp = Var Char | Value Int | Add AExp AExp | Mul AExp AExp | Sub AExp AExp
data BExp = Eq AExp AExp | Lt AExp AExp | Gt AExp AExp | ELt AExp AExp| EGt AExp AExp | And BExp BExp | Or BExp BExp |Boolean Bool
data AssignExp = AExp Char |  BExp Char
data Statement = AssignExp | While BExp Statement
type Env   = M.Map Char Int

env = M.fromList[('A',1),('B',2),('C',3)]

evalAExp :: AExp -> Maybe Int
evalAExp (Value x) = (Just x)
evalAExp (Var x) = M.lookup x env
evalAExp (Add a1 a2) =do
  v2<-evalAExp a2;v1<-evalAExp a1
  return (v1+v2)
evalAExp (Sub a1 a2) =do
  v2<-evalAExp a2;v1<-evalAExp a1
  return (v1-v2)
evalAExp (Mul a1 a2) = do
  v1 <-evalAExp a1;v2 <- evalAExp a2
  return (v1*v2)

evalBExp (Boolean True) = True
evalBExp (Boolean False) = False
evalBExp (Eq a1 a2) = (evalAExp (a1)) == (evalAExp (a2))

Probably you should put all of your relevant code here ? How is AExp and evalAExp defined ? — Sibi
Sorry about that . I couldn't find a way to point to the problem I had while explaining, so I added that part. I am a bit bad at expressing myself. — Akshay Hazari

pigworker pigworker · Accepted Answer · 2015-03-29T12:26:29

Your suspicion, "I think there is a problem in the data BExp declaration itself", is correct. What you've written doesn't mean what I suspect you hope it does. The error is at the far right end (as errors often are) so I had to scroll to find it. Using more vertical space, let's see.

data BExp
  = Eq AExp AExp
  | Lt AExp AExp
  | Gt AExp AExp
  | ELt AExp AExp
  | EGt AExp AExp
  | And BExp BExp
  | Or BExp BExp
  | Bool

And it's the last that is the big problem. It's harder to spot because although you tell us, "I want the type to be :: BExp -> Bool", you do not tell the compiler. If you had done the decent thing and communicated your intention by writing an explicit type signature, the error report might have been more helpful. Your program begins

evalBExp True = True

and that is enough to convince the typechecker that the intended type is

evalBExp :: Bool -> Bool

because True :: Bool. When line 3 shows up with

evalBExp (Eq a1 a2) = evalAExp (a1) == evalAExp (a2)

suddenly it wonders why you're giving evalBExp a BExp instead of a Bool.

Now, I suspect that you have the impression that your final clause in BExp

| Bool

makes True :: BExp and False :: BExp, but that's not what it does at all. Instead, you will discover that you have a nullary data constructor Bool :: BExp whose name is coincident with the datatype Bool but lives in an entirely separate namespace. I believe your intention is to embed the values of Bool into BExp silently, but Haskell does not allow such subtle subtyping. To achieve the intended effect, you will need a constructor which explicitly packs up a Bool, so try

data BExp
  = ...
  | BVal Bool

and

evalBExp :: BExp -> Bool
evalBExp (BVal b) = b
...

to get closer to your plan.

You are, of course, free to use the name Bool for the BVal constructor, and so write

data BExp
  = ...
  | Bool Bool

where the first Bool is a data constructor and the second is a type constructor, but I would find that choice confusing.

Boolean Expression evaluation . Couldn't match expected type

1 Answers