title: Arithmetic expression evaluation in Haskell
body: <p>Here i am trying to evaluate the expression in Haskell using defined values of <code>Exp</code> data type. The function type would be <code>eval :: Exp -&gt; Int</code> and data type is this: </p>
  
  <pre><code>data Exp = Num Int
         | Exp :+: Exp
         | Exp :-: Exp
         | Exp :*: Exp
         | Exp :/: Exp
         deriving (Show)
  </code></pre>
  
  <p>and values which i am trying to evaluate are these:</p>
  
  <pre><code> 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))
  </code></pre>
  
  <p>So far this logic is working fine which is: </p>
  
  <pre><code>eval :: Exp -&gt; 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)
  </code></pre>
  
  <p>When i pass this i get <code>3</code> as output which is correct: </p>
  
  <pre><code>eval (Num 2 :+: Num 2 :-: Num 1) 
  output = 3 
  </code></pre>
  
  <p>but i am confused how it evaluated the second part of the expression which <code>:-:</code> what i understood the only pattern matched in first iteration was <code>eval (a :+: b) = (eval a) + (eval b)</code> which returned <code>4</code> as output how it carries <code>4</code> to next iteration to perform the <code>:-:</code> operation?</p>
  
  <p>before that i was trying something like this: </p>
  
  <pre><code>eval :: Exp -> Int
  eval (Num a) = a
  eval (<b>Num</b> a :+: <b>Num</b> b) = eval (<b>Num</b> a) + eval (<b>Num</b> b)
  eval (<b>Num</b> a :-: <b>Num</b> b) = eval (<b>Num</b> a) - eval (<b>Num</b> b)
  eval (<b>Num</b> a :*: <b>Num</b> b) = eval (<b>Num</b> a) * eval (<b>Num</b> b)
  eval (<b>Num</b> a :/: <b>Num</b> b) = eval (<b>Num</b> a) `div` eval (<b>Num</b> b)</code></pre>
  
  <p>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. </p>