{-# LANGUAGE GADTs #-}

import Prelude hiding (foldr)
import Data.Monoid
import Data.Foldable

class Heap h where
    empty :: Ord a => h a 
    isEmpty :: Ord a => h a -> Bool
    insert :: Ord a => a -> h a -> h a 
    findMin :: Ord a => h a -> a
    deleteMin :: Ord a => h a -> h a 

data ListHeap a where 
    LH :: Ord a => [a] -> ListHeap a

insertOrdered :: Ord a => a -> [a] -> [a] 
insertOrdered a [] = [a] 
insertOrdered a (x:xs) = if a < x then a:x:xs else x:(insertOrdered a xs) 

instance Show a => Show (ListHeap a) where
    show (LH xs) = "ListHeap " ++ (show xs) 

instance Heap ListHeap where
    empty = LH []

    isEmpty (LH xs) = null xs

    insert a (LH xs) = LH $ insertOrdered a xs

    findMin (LH []) = error "Empty heap"
    findMin (LH (x:xs)) = x 

    deleteMin (LH []) = error "Empty heap"
    deleteMin (LH (x:xs)) = LH xs

-- Suppose the inner structure is complex so we don't want
-- to use it directy, but we still have to pattern-match on it
instance Foldable ListHeap where
    foldMap f h@(LH _)
      | isEmpty h = mempty
      | otherwise = f (findMin h) `mappend` foldMap f (deleteMin h)

-- Yep, we are foldable!
fromList :: Ord a => [a] -> ListHeap a
fromList = foldr insert empty

main = do let h = fromList [1, 5, 3, 7, 9]
          print $ insert 10 h