No instance for (Eq a) arising from a use of ‘==’

Question

I'm trying to write an Eq instance for this data type:

data Tree a b = Leaf b | Node a (Tree a b) (Tree a b)
deriving (Show)

I wrote the trivial code I thought that would work:

instance Eq (Tree a b) where
  (Leaf x) == (Leaf y) =  x == y
  (Node val1 l1 r1) == (Node val2 l2 r2)  =  (val1 == val2) && (l1==l2) && (r1==r2)
  _  == _  = False

But then I get the error:

• No instance for (Eq a) arising from a use of ‘==’
  Possible fix: add (Eq a) to the context of the instance declaration
• In the first argument of ‘(&&)’, namely ‘(val1 == val2)’
  In the expression: (val1 == val2) && (l1 == l2) && (r1 == r2)
  In an equation for ‘==’:
     (Node val1 l1 r1) == (Node val2 l2 r2)
     = (val1 == val2) && (l1 == l2) && (r1 == r2)

I've tried adding Eq a => ... but then I get the same error for type b. And I can't seem to add Eq b as well.

Any help will be appreciated, 10x!

Answer 1

As you have written, you have to put type constraints Eq a and Eq b. You just have to put the constraints in parentheses and separate them with comma.

instance (Eq a, Eq b) => Eq (Tree a b) where
  (Leaf x) == (Leaf y) =  x == y
  (Node val1 l1 r1) == (Node val2 l2 r2)  =  (val1 == val2) && (l1==l2) && (r1==r2)
  _  == _  = False

Answer 2

You write an instance where you call the (==) function on instances of a and b:

instance Eq (Tree a b) where
  (Leaf x) == (Leaf y) = x == y
  (Node val1 l1 r1) == (Node val2 l2 r2) = (val1 == val2) && (l1==l2) && (r1==r2)
  _  == _  = False

But x and y in your first clause are instances of a, and val1 and val2 in your second clause are instances of b. It is not said that you can compare those. For example you can not check equality of two functions (it is fundamentally impossible in computer science to check if two functions are equal in general). As a result in that case we can never derive whether the two trees are equal.

Anyway, Haskell notices that you use the function (==) :: Eq c => c -> c -> Bool with as operands x and y (in the first clause), and hence Eq a, is required. The same reasoning holds for the second clause: we see that you call (==), with two b instances, so Eq b is required. We need to add those type constraints to the instance declaration:

instance (Eq a, Eq b) => Eq (Tree a b) where
  (Leaf x) == (Leaf y) = x == y
  (Node val1 l1 r1) == (Node val2 l2 r2) = (val1 == val2) && (l1==l2) && (r1==r2)
  _  == _  = False

As a consequence, you can only check equality of two trees, given the a and b of the tree are types that are an instance of the Eq typeclass. But that is logical, since if you can for instance not compare the values of the Leafs, then how can you say whether a tree is equal or not?