Programming Associativity in haskell

Question

So this is my assignment here in which i have to program the associativity of some expressions, I worked on this a few hours and I'm just missing something obvious. Here are my final two ideas that both somewhat work yet cannot evaluate truly equal expressions properly (The first one gives a parse error) I cannot understand what is wrong. Help :(

    data Expr = Const Int | Add Expr Expr deriving Show
    instance Num Expr where
        fromInteger = Const . fromInteger
        (+) = Add
   -- I have to write here
    instance Eq Expr where 
(Const i) == (Const j) = i == j
(Add i j) == (Add a b) = i == a && j == b || i ==b && j == a
(==) (Add e3 (Add e1 e2)) (Add (Add e4 e5) e6) = 
    (Add(Add e1 e2) e3)==(Add e1 (Add e2 e3)) 
    _ == _ = False

Answer 1

You might want to replace:

 (==) (Add e3 (Add e1 e2)) (Add (Add e4 e5) e6) = (Add(Add e1 e2) e3)==(Add e1 (Add e2 e3)) 

by

(==) (Add e1 (Add e2 e3)) e = (Add(Add e1 e2) e3) == e
(==) e (Add e1 (Add e2 e3)) = e == (Add(Add e1 e2) e3)

Each equation simply rebalances one expression tree to obtain a left recursion, without trying to check if the expressions are actually equals, so you need a third equation:

   (==) (Add e1 e2 ) (Add e3 e4) = (e1 == e3) && (e2 == e4)

Then I define a function which explicitely takes Expr as parameters to test (==):

testexpr :: Expr -> Expr -> Bool
testexpr a b = a == b

and testexpr (1 + (2 +3)) ((1 + 2) + 3) yields True.

Since it is an assignment, integrating that change in your code, and reorganizing it to make it work is left as an exercise.