CODEWITHSUNDEEP
haskelloperatorsevaluationoperator-precedence
Sniper
Sniper

Reputation: 418

Arithmetic expression evaluation in Haskell

Here i am trying to evaluate the expression in Haskell using defined values of Exp data type. The function type would be eval :: Exp -> Int and data type is this: 

data Exp = Num Int
       | Exp :+: Exp
       | Exp :-: Exp
       | Exp :*: Exp
       | Exp :/: Exp
       deriving (Show)

and values which i am trying to evaluate are these:

 4 + 5 * 6 , respecting correct precedences of the operators
 4 + 5 + 6 , respecting, that + binds left-associative
 (4 + 3) * (5 - 2)
 4 + (4 / (2 - 2))

So far this logic is working fine which is: 

eval :: Exp -> Int
eval (Num a) = a 
eval (a :+: b) = (eval a) + (eval b)
eval (a :-: b) = (eval a) - (eval b)
eval (a :*: b) = (eval a) * (eval b)
eval (a :/: b) = (eval a) `div` (eval b)

When i pass this i get 3 as output which is correct: 

eval (Num 2 :+: Num 2 :-: Num 1) 
output = 3

but i am confused how it evaluated the second part of the expression which :-: what i understood the only pattern matched in first iteration was eval (a :+: b) = (eval a) + (eval b) which returned 4 as output how it carries 4 to next iteration to perform the :-: operation?

before that i was trying something like this: 

eval :: Exp -> Int
eval (Num a) = a
eval (Num a :+: Num b) = eval (Num a) + eval (Num b)
eval (Num a :-: Num b) = eval (Num a) - eval (Num b)
eval (Num a :*: Num b) = eval (Num a) * eval (Num b)
eval (Num a :/: Num b) = eval (Num a) `div` eval (Num b)

it didn't give the desired results and then i just changed it to the first version. it worked fine but didn't get the proper semantics of it. Any help? Please don't hesitate to go into details. Thanks in advance.

Upvotes: 2

Views: 2007

Answers (3)

chepner
chepner

Reputation: 532093

As pointed out in other answers, the problem is that all your constructors have the same default precedence: they are left-associative with high (9) precedence. You can change that using the infixl directive.

data Exp = Num Int
       | Exp :+: Exp
       | Exp :-: Exp
       | Exp :*: Exp
       | Exp :/: Exp
       deriving (Show)

-- Using the same precedences as (+), (-), (*), and (/)
infixl 6 :+:, :-:
infixl 7 :*:, :/:

Now eval $ Num 4 :+: Num 2 :*: Num 3 will correctly return 10 instead of 18.

Upvotes: 5

Robin Zigmond
Robin Zigmond

Reputation: 18249

I think the easiest way to follow what's going on here is just to follow the evaluation through one step at a time. Since as @WillNess has explained the default order of operation is from left to right, your code is evaluated as follows (each individual step comes directly from one of the lines of your definitioni of eval):

eval ((Num 2 :+: Num 2) :-: Num 1)
eval (Num 2 :+: Num 2) - eval(Num 1)
(eval (Num 2 :+: Num 2)) - 1
(eval (Num 2) + eval (Num 2)) - 1
(2 + 2) - 1
4 - 1
3

I hope this makes it clear.

Upvotes: 1

Will Ness
Will Ness

Reputation: 71119

The default fixity for operators is infixl 9 (see 4.4.2 Fixity Declarations).

You have not declared the fixity for your :+: etc. operators.

This means that your expression gets parsed as

eval ((Num 2 :+: Num 2) :-: Num 1)  :: Exp

--     Num 2                        :: Exp 
--               Num 2              :: Exp 
--     Num 2 :+: Num 2              :: Exp 
--                          Num 1   :: Exp 
--    (Num 2 :+: Num 2) :-: Num 1   :: Exp

So the evaluation proceeded as

  eval ((Num 2 :+: Num 2) :-: Num 1)  -- match with:
  eval (a                 :-: b    ) = (eval a) - (eval b)
                                     =  ....

Upvotes: 6

Related Questions