Compare Binary Search Trees (flawed)


/ Published in: Haskell
Save to your folder(s)

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


Copy this code and paste it in your HTML
  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

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

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.