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.
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
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With