I am kinda stuck on implementing an Eq instance for binary search trees. I want to check if the values in the two trees are the same, but I don't really know how to do that correctly. Because of the possibly different structures of two binary search trees I can't just compare the nodes directly. My idea was to convert them into a list, sort the lists and compare them but that seems pretty complicated and I wondered if there is another way to do that. Here is what I got so far:
data BB a = L | K a (BB a) (BB a) deriving (Show)
instance Eq BB where
not (isBinarySearchTree t1 && isBinarySearchTree t2) = False
inOrder t1 == inOrder t2 = True
The accepted answer looks wrong to me, since you say you want to compare based on the conceptual contents of the trees, not their exact structure. That is, you want the following to be true:
K 1 L (K 2 L L) == K 2 (K 1 L L) L
Two BSTs with the same two elements, ordered correctly but structured differently. Comparing them structurally, as in severij's answer, yields False, but you want it to be True.
So, how to compare by contents instead of by structure? Well, any two BSTs with the same set of items will have the same in-order traversal. So, you can do exactly as you said in your question: convert them to lists, and compare the lists. But you don't have to sort them: because they are BSTs you are guaranteed that you can traverse them in the same order. And it's not terribly expensive to convert them to lists, so don't worry about that: laziness and stream fusion make it cost about the same as writing the traversals by hand.
It will be much easier if you have a Foldable instance for your tree type, which is a good thing for a tree to have anyway. To define Foldable, you need only define foldr, which is easy enough:
import Prelude hiding (foldr)
import Data.Foldable (Foldable, foldr, toList)
instance Foldable BB where
foldr f init L = init
foldr f init (K x left right) = foldr f (f x (foldr f init right)) left
And then you can define Eq in terms of toList:
instance Eq (BB a) where
x == y = toList x == toList y
After which you have, as desired,
*Main> (K 1 L (K 2 L L)) == (K 2 (K 1 L L) L)
True
But this was rather a lot of work, wasn't it? And I got the definition of foldr wrong several times while writing this answer. It turns out, there is a way to avoid having to write it yourself: the DeriveFoldable language extension lets GHC derive Foldable for you as easily as it derives Show. But since it folds up fields in your data type in order, you will have to change it a bit so that the left subtree appears before the root node:
{-# LANGUAGE DeriveFoldable #-}
import Prelude hiding (foldr)
import Data.Foldable (Foldable, foldr, toList)
data BB a = L | K (BB a) a (BB a) deriving (Show, Foldable)
instance Eq (BB a) where
x == y = toList x == toList y
And indeed, we still have the desired equality property (though we must write the nodes differently because we changed field order):
*Main> (K L 1 (K L 2 L)) == (K (K L 1 L) 2 L)
True
There remains one final improvement to be made: the Eq definition can be simpler too, if you import Data.Function.on. Rather than spelling it all out by hand, with on you can simply say "to compare two trees for equality, convert each to a list and compare those lists for equality". Leaving the tree definitions and other imports intact, we at last at last obtain a quite succinct definition of the desired features, with all the real work done by already-written library functions:
{-# LANGUAGE DeriveFoldable #-}
import Prelude hiding (foldr)
import Data.Foldable (Foldable, foldr, toList)
import Data.Function (on)
data BB a = L | K (BB a) a (BB a) deriving (Show, Foldable)
instance Eq a => Eq (BB a) where
(==) = (==) `on` toList