Arithmetic expression evaluation in Haskell

Question

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.

Answer 1

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)
                                     =  ....