Haskell: Possible fix: add (Eq a) to the context

Question

I'm kind of new to Haskell, and it's hard for me to understand what is wrong with my code here.

Here is what I have to do:
Consider the following definition of a binary tree

data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a) 

Consider a function that reflects what forms a mirror image of a binary tree, swapping left and right all the way down

 reflect :: BinaryTree a -> BinaryTree a reflect Empty = Empty reflect (Node xlr) = Node x (reflect r) (reflect l) 

Write a function areMirrorImages that determines whether two binary trees satisfy t and u t = reflect u. The function should not build new trees, therefore it should not cause reflection or Node; although it can use Node in templates.

Here is what I wrote:

 areMirrorImages :: BinaryTree a -> BinaryTree a -> Bool areMirrorImages Empty Empty = True areMirrorImages (Node _ _ _) Empty = False areMirrorImages Empty (Node _ _ _) = False areMirrorImages (Node xlr) (Node y ll rr) | x==y = ((areMirrorImages l rr) && (areMirrorImages r ll)) | otherwise = False 

When I try to start it, I get the following error on line 49:
Failed to infer (Eq a) from context () associated with using '=='
Possible fix: add (Eq a) to the type signature context for 'areMirrorImages'
In the expression: x == y

I am confused why I get this error, and I tried to find solutions on the Internet, but haven’t found anything yet. Thanks.

Answer 1

At the moment, your binary trees can contain any type - even types that cannot be compared using == . So, if you called areMirrorImages on a tree containing that type ... what should happen?

What you need to do is set a restriction on the areMirrorImages function areMirrorImages that it can only accept binary trees so that it can compare contents.

Something like the following:

 areMirrorImages :: Eq a => BinaryTree a -> BinaryTree a -> Bool 

Answer 2

As a small note: it is often useful to put all the “relevant” cases of the function on top, as this often simplifies the “inappropriate” ones:

 areMirrorImages :: Eq a => BinaryTree a -> BinaryTree a -> Bool areMirrorImages Empty Empty = True areMirrorImages (Node xlr) (Node y ll rr) = and [x==y, areMirrorImages l rr, areMirrorImages r ll] areMirrorImages _ _ = False