関数プログラミングの楽しみ 1章 binary heap

binary-heap.hs

-- 関数プログラミングの楽しみ 第1章

data (Ord a) => Tree a = Null | Fork a (Tree a) (Tree a)
  deriving (Show, Eq)

isEmpty :: Tree a -> Bool
isEmpty Null = True
isEmpty x = False

minElem :: Ord a => Tree a -> a
minElem (Fork x l r) = x

deleteMin :: Ord a => Tree a -> Tree a
deleteMin Null = Null
deleteMin (Fork x l r) = merge l r

insert :: Ord a => a -> Tree a -> Tree a
insert x t = merge (Fork x Null Null) t

merge :: Ord a => Tree a -> Tree a -> Tree a
merge Null r = r 
merge l Null = l
merge l@(Fork x _ _) r@(Fork y _ _) 
  | x <= y = join l r
  | otherwise = join r l
  where
    join (Fork x lx rx) r = Fork x (merge r rx) lx 
    --join (Fork x lx rx) r = Fork x rx $ merge lx r 


-- test 
test0 = insert 5 Null
test1 = insert 10 (insert 5 Null)
test2 = insert 4 (insert 10 (insert 5 Null))
test3 = insert 11 (insert 4 (insert 10 (insert 5 Null)))