Binominal Heap in Haskell

BinHeap.hs

module BinHeap (
  Heap,
  empty,
  insert,
  findMin,
  deleteMin,
  fromList,
  toList
  ) where

import Data.List (minimumBy, unfoldr)
import Data.Function (on)

data Tree a = Tree { label :: a, heap :: Heap a } deriving Show
type Heap a = [(Int, Tree a)]

mergeTree :: Ord a => Int -> Tree a -> Tree a -> Tree a
mergeTree r t@(Tree x xs) s@(Tree y ys)
  | x < y     = Tree x ((r, s):xs)
  | otherwise = Tree y ((r, t):ys)

insertTree :: Ord a => Int -> Tree a -> Heap a -> Heap a
insertTree r t [] = [(r, t)]
insertTree r t (x@(r', t'):xs)
  | r <  r' = (r, t):x:xs
  | r == r' = insertTree (r+1) (mergeTree r t t') xs
  | r >  r' = x:insertTree r t xs

empty :: Heap a
empty = []

insert :: Ord a => a -> Heap a -> Heap a
insert x h = insertTree 0 (Tree x []) h

findMin :: Ord a => Heap a -> Maybe a
findMin [] = Nothing
findMin h = Just . minimum $ map (label . snd) h

deleteMin :: Ord a => Heap a -> Maybe (a, Heap a)
deleteMin [] = Nothing
deleteMin h = Just (x, h''')
  where
    (r, Tree x h') = minimumBy (compare `on` (label . snd)) h
    h'' = filter ((r/=) . fst) h
    h''' = foldr (uncurry insertTree) h'' h'

fromList :: Ord a => [a] -> Heap a
fromList = foldr insert empty

toList :: Ord a => Heap a -> [a]
toList = unfoldr deleteMin

Main.hs

import qualified BinHeap as H

heapSort :: Ord a => [a] -> [a]
heapSort = H.toList . H.fromList

main :: IO ()
main = print $ heapSort [8, 2, 3, 1, 6, 5, 9, 4, 0, 7]