binary search tree

bstree.hs

module BTree where
 
data BTree a b = Empty 
               | BNode {
                    kv :: (a, b), 
                    left :: BTree a b,
                    right :: BTree a b
               } 
               deriving(Show, Eq)
 
insert :: (Ord a) => (a, b) -> BTree a b -> BTree a b
insert (k,v) Empty = BNode (k, v) Empty Empty
insert (k,v) pnode@(BNode (pk, _) lnode rnode) 
    | k == pk   = pnode { kv = (k,v) }
    | k <  pk   = pnode { left  = insert (k,v) lnode }
    | k >  pk   = pnode { right = insert (k,v) rnode }
 
find :: (Ord a) => a -> BTree a b -> Maybe b
find k Empty = Nothing
find k (BNode (pk,pv) lnode rnode)
    | k == pk = Just pv
    | k <= pk = find k lnode
    | k >  pk = find k rnode
find _ _ = Nothing

findMin Empty = Empty
findMin pnode@(BNode _ lnode _) 
    | isEmpty lnode = pnode
findMin pnode@(BNode _ lnode _) = findMin lnode
 
remove :: (Ord a) => a -> BTree a b -> BTree a b
remove k Empty = Empty
remove k pnode@(BNode (pk,_) lnode rnode) 
    | k == pk   = removeTop pnode
    | k <  pk   = pnode { left  = remove k lnode }
    | k >  pk   = pnode { right = remove k rnode }
 
-- scenary 1: the target node has no child
removeTop (BNode _ Empty Empty) = Empty
-- scenary 2: the target node has one child
removeTop (BNode _ lnode Empty) = lnode
removeTop (BNode _ Empty rnode) = rnode
-- scenary 3: the target node has both children
removeTop pnode@(BNode (pk,pv) lnode rnode) =   
    pnode { kv = kv snode, right = nnode }
    where (snode, nnode) = spanMin rnode

spanMin Empty = (Empty, Empty)
spanMin pnode@(BNode _ lnode _) 
    | isEmpty lnode = (pnode, Empty)
spanMin pnode@(BNode _ lnode _) =
    (fst $ spanMin lnode, pnode)

-- 

merge :: (Ord a) => BTree a b -> BTree a b -> BTree a b
merge lnode rnode = fromList $ (toList lnode) ++ (toList rnode)
 
--helper
isEmpty Empty = True 
isEmpty _     = False
 
fromList :: (Ord a) => [(a,b)] -> BTree a b
fromList = foldl (flip insert) Empty 
 
toList :: BTree a b -> [(a,b)]
toList Empty = [] 
toList (BNode (k,v) lnode rnode) = 
    (toList lnode) ++ [(k,v)] ++ (toList rnode)

-- for test
root = fromList $ [
    (4, "fleurer"), 
    (10, "ssword"), 
    (100, "ssword"), 
    (10, "fleuria"), 
    (2, "xx")]