Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

I'm kind of new to Haskell and I'm having a hard time understanding what is wrong with my code here.

Here is what I'm supposed to do:
Consider the following definition of a binary tree

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

Consider the function reflect that forms the mirror image of a binary tree by exchanging left and right all the way down

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

Write a function areMirrorImages that determines whether two binary trees t and u satisfy t = reflect u. The function should not build new trees, so it should not call reflect or Node; although it may use Node in patterns.

Here is what I've written:

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

When I try running it I get the following error on line 49:
Could not deduce (Eq a) from the context () arising from a use of '=='
Possible fix: add (Eq a) to the context of the type signature for 'areMirrorImages'
In the expression: x==y

I am confused as to why I'm getting this error and I tried finding solutions online but I have found nothing so far. Thanks.

like image 911
Gus Avatar asked Feb 16 '11 03:02

Gus


2 Answers

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

What you need to do is place a constraint on the areMirrorImages function, so that it can only accept binary trees that it can compare the contents of.

Something like the following:

areMirrorImages :: Eq a => BinaryTree a -> BinaryTree a -> Bool
like image 94
Anon. Avatar answered Oct 19 '22 09:10

Anon.


Just as a little side note: It's often a good idea to put all "matching" cases of a function at the top, as this often simplifies the "non-matching" ones:

areMirrorImages :: Eq a => BinaryTree a -> BinaryTree a -> Bool
areMirrorImages Empty Empty = True  
areMirrorImages (Node x l r) (Node y ll rr) = 
    and [x==y, areMirrorImages l rr, areMirrorImages r ll]  
areMirrorImages _ _ = False  
like image 44
Landei Avatar answered Oct 19 '22 10:10

Landei