Posted By

u1ik on 08/28/09

Tagged

Versions (?)

Last Edited at 08/28/09 01:46pm

Statistics

Viewed 321 times

Favorited by 1 user(s)

Related snippets

Compare Binary Search Trees (flawed)

/ Published in: Haskell

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

Highlighted TextExpand

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

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

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.