-- Example: Binary tree
data Tree a = Empty | Node a (Tree a) (Tree a)
deriving (Eq, Show)
-- assumption: < is a linear ordering
find :: Ord a => a -> Tree a -> Bool
find _ Empty = False
find x (Node a l r)
| x == a = True
| x < a = find x l
| otherwise = find x r
insert :: Ord a => a -> Tree a -> Tree a
insert x Empty = Node x Empty Empty
insert x (Node a l r)
| x == a = Node a l r
| x < a = Node a (insert x l) r
| otherwise = Node a l (insert x r)
delete :: Ord a => a -> Tree a -> Tree a
delete x Empty = Empty
delete x (Node a l r)
| x == a = combine l r
| x < a = Node a (delete x l) r
| otherwise = Node a l (delete x r)
combine :: Tree a -> Tree a -> Tree a
combine Empty r = r
combine l Empty = l
combine l r = Node m l r' where (m,r') = delMin r
-- delMin t = (leftmost/minimal element of t, t without that element)
delMin :: Tree a -> (a, Tree a)
delMin (Node a Empty r) = (a, r)
delMin (Node a l r) = (m, Node a l' r) where (m,l') = delMin l