The type Tree should be an instance of the typeclass Eq

Question

I have the following data structure and want it to be an instance of the typeclass Eq.

data Tree n l
  = Node n (Tree n l) (Tree n l)
  | Leaf l

I tried to do it the following way

instance Eq => (Tree n l) where
  (Node a b c) == (Node d e f) = a == d
  (Leaf a) == (Leaf b) = a == b

But there is an error message

‘==’ is not a (visible) method of class ‘Tree’

Answer 1

There are two problems here:

1. you did not specify to what type class you made Tree n l an instance; and
2. in order to check that with the given definition, both n and l need to be types that are instances of the Eq typeclass.

So you can implement this with:

instance (Eq n, Eq l) => Eq (Tree n l) where
  (Node a b c) == (Node d e f) = a == d
  (Leaf a) == (Leaf b) = a == b

Note that now it will compile but there is still a problem: it will raise an error if you check if a Node … … … is equal to a Leaf … and vice versa. You can add an extra rule for that:

instance (Eq n, Eq l) => Eq (Tree n l) where
  (Node a b c) == (Node d e f) = a == d
  (Leaf a) == (Leaf b) = a == b
  _ == _ = False

Here you will however consider two Node … … … the same, from the moment they wrap the same value. So you do not look to the subtrees. In order to fix this, you need to perform recursion. I leave that as an exericse.