Declaring an instance of Eq (Tree a) where two trees are equal if they have the same elements

user_10848949 0
Viewed 491

I'm trying to create an instance of Eq (Tree a) for my tree datatype in Haskell, so that two trees are equal if they have the same elements. So I have a method that turns my tree into a list (flatten), and then I compare the sorted lists. But I'm getting errors like there is no instance for (Ord a) when I sort my list, or (Eq a) when I == my two lists.

import Data.List as L    
data Tree a = EmptyTree | Node (Tree a) a (Tree a)

instance Eq (Tree a) where     
 (==) t1 t2 = L.sort(flatten t1) == L.sort(flatten t2)

flatten :: Tree a -> [a]    
flatten EmptyTree = []    
faltten (Node x1 y x2) = [y] ++ (flatten x1) ++ (flatten x2)

I don't know why this refuses to compile. I used a method I have that makes a tree from a list and flattening that tree returns the original list, so I know flatten is working properly. I'm assuming it's complaining about not knowing if the contents of the list are Ord or Eq, but I don't know how to fix this. Adding 

 (Ord a, Eq a) =>

to the flatten signature didn't do it.

tree haskell types
1 Answers

The problem is not with flatten: flatten does not need the elements to be orderable, it just produces a list of the elements.

The problem is that you use sort :: Ord a => [a] -> [a] in your implementation of (==), and sort thus needs the elements in the list to be of a type that is an instance of the Ord typeclass.

The type of the elements also needs to be a member of the Eq typeclass, since you then call (==) on the lists. But since Ord implies Eq, that is not really a problem here.

We thus need to add these type constraints to the instance declaration:

instance Ord a => Eq (Tree a) where     
 (==) t1 t2 = L.sort(flatten t1) == L.sort(flatten t2)

So here we can only check if two trees are equal, given the trees contain elements of a type that is an instance of the Ord typeclass.

user_675790
Related