advanced code snippet search

Posted By

u1ik on 08/28/09


Tagged

merge compare bsp flawed


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

keigoi


Compare Binary Search Trees (flawed)

 / Published in: Haskell
 

URL: http://antilamer.livejournal.com/289527.html

Similar to merging two sorted lists. UPT: Doesn't work.

Expand | Embed | Plain Text 
  1. data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
  2.  
  3. data Result a = Equal | NotEqual | Remains a deriving (Show, Eq)
  4.  
  5. cmp Empty Empty = Equal
  6.  
  7. cmp Empty t2    = NotEqual
  8.  
  9. cmp t1 Empty    = Remains t1
  10.  
  11. cmp t1@(Node v1 l1 r1) t2@(Node v2 l2 r2) 
  12.           | v1 == v2  = case (cmp l1 l2) of
  13.                         Equal -> (cmp r1 r2)
  14.                         _     -> NotEqual
  15.  
  16.           | v1 < v2   = if l2 == Empty then NotEqual
  17.                         else case (cmp t1 l2) of
  18.                              Equal            -> NotEqual
  19.                              NotEqual         -> NotEqual
  20.                              Remains t1' -> cmp t1' (Node v2 Empty r2)
  21.  
  22.           | otherwise = if l1 == Empty then NotEqual
  23.                         else case (cmp t2 l1) of
  24.                              Equal            -> NotEqual
  25.                              NotEqual         -> NotEqual
  26.                              Remains t2' -> cmp (Node v1 Empty r1) t2'
  27.  
  28. instance (Ord a) => Eq (Tree a) where
  29.    t1 == t2 = (cmp t1 t2) == Equal

Report this snippet  

Comments

RSS Icon 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 ta@(Node a ta1 ta2) tb@(Node b tb1 tb2) =
                              a == b && treeEq ta1 tb1 && treeEq ta2 tb2
instance (Ord a) => Eq (Tree a) where (==) = treeEq

You need to login to post a comment.