Posted By

u1ik on 08/29/09


Tagged

merge compare bsp


Versions (?)

Who likes this?

2 people have marked this snippet as a favorite

keigoi
deepsoul


Compare Binary Search Trees


 / Published in: Haskell
 

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

  1. data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
  2.  
  3. data Result a = Equal | NotEqual | RemainsLeft a | RemainsRight a deriving (Show, Eq)
  4.  
  5. cmp Empty Empty = Equal
  6.  
  7. cmp Empty t2 = RemainsRight t2
  8.  
  9. cmp t1 Empty = RemainsLeft 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 -> RemainsRight (Node v2 Empty r2)
  19. NotEqual -> NotEqual
  20. RemainsLeft t1' -> cmp t1' (Node v2 Empty r2)
  21. RemainsRight l2' -> RemainsRight (Node v2 l2' r2)
  22.  
  23. | otherwise = if l1 == Empty then NotEqual
  24. else case (cmp l1 t2) of
  25. Equal -> RemainsLeft (Node v1 Empty r1)
  26. NotEqual -> NotEqual
  27. RemainsLeft l1' -> RemainsLeft (Node v1 l1' r1)
  28. RemainsRight t2' -> cmp (Node v1 Empty r1) t2'
  29.  
  30. instance (Ord a) => Eq (Tree a) where
  31. t1 == t2 = (cmp t1 t2) == Equal
  32.  
  33. test1 =
  34. let t213 = Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty) in
  35. let t657 = Node 6 (Node 5 Empty Empty) (Node 7 Empty Empty) in
  36. let t1 = Node 4 t213 (Node 8 t657 (Node 9 Empty Empty)) in
  37. let t2 = Node 8 (Node 4 t213 t657) (Node 9 Empty Empty) in
  38. t1 == t2
  39.  
  40. test2 =
  41. let t213 = Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty) in
  42. let t657 = Node 6 (Node 5 Empty Empty) (Node 7 Empty Empty) in
  43. let t1 = Node 4 t213 (Node 8 t657 (Node 9 Empty Empty)) in
  44. let t2 = Node 8 (Node 4 t213 t657) (Node 9 Empty (Node 10 Empty Empty)) in
  45. t1 /= t2

Report this snippet  

You need to login to post a comment.