u1ik on 08/28/09

## Who likes this?

1 person have marked this snippet as a favorite

# Compare Binary Search Trees (flawed)

/ Published in: Haskell   Similar to merging two sorted lists. UPT: Doesn't work.

`data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show) data Result a = Equal | NotEqual | Remains a deriving (Show, Eq) cmp Empty Empty = Equal cmp Empty t2    = NotEqual cmp t1 Empty    = Remains t1 cmp t1@(Node v1 l1 r1) t2@(Node v2 l2 r2)           | v1 == v2  = case (cmp l1 l2) of                        Equal -> (cmp r1 r2)                        _     -> NotEqual           | v1 < v2   = if l2 == Empty then NotEqual                        else case (cmp t1 l2) of                             Equal            -> NotEqual                             NotEqual         -> NotEqual                             Remains t1' -> cmp t1' (Node v2 Empty r2)           | otherwise = if l1 == Empty then NotEqual                        else case (cmp t2 l1) of                             Equal            -> NotEqual                             NotEqual         -> NotEqual                             Remains t2' -> cmp (Node v1 Empty r1) t2' instance (Ord a) => Eq (Tree a) where   t1 == t2 = (cmp t1 t2) == Equal` Subscribe to comments
Posted By: deepsoul on September 17, 2009

The source you posted compiles and works correctly for me. It is only deliberately obfuscated. The result of the second and third case at lines 16 to 26 is always `NotEqual`, because `Remains ..` can never result from line 17 resp. 23.

As for comparing two trees, the following will do nicely:

``````treeEq :: Eq a => Tree a -> Tree a -> Bool
treeEq Empty Empty = True
treeEq _ Empty = False
treeEq Empty _ = False
treeEq [email protected](Node a ta1 ta2) [email protected](Node b tb1 tb2) =
a == b && treeEq ta1 tb1 && treeEq ta2 tb2
instance (Ord a) => Eq (Tree a) where (==) = treeEq
``````