{-# 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

ey0jIExBTkdVQUdFIEdBRFRzICMtfQoKaW1wb3J0IFByZWx1ZGUgaGlkaW5nIChmb2xkcikKaW1wb3J0IERhdGEuTW9ub2lkCmltcG9ydCBEYXRhLkZvbGRhYmxlCgpjbGFzcyBIZWFwIGggd2hlcmUKICAgIGVtcHR5IDo6IE9yZCBhID0+IGggYSAKICAgIGlzRW1wdHkgOjogT3JkIGEgPT4gaCBhIC0+IEJvb2wKICAgIGluc2VydCA6OiBPcmQgYSA9PiBhIC0+IGggYSAtPiBoIGEgCiAgICBmaW5kTWluIDo6IE9yZCBhID0+IGggYSAtPiBhCiAgICBkZWxldGVNaW4gOjogT3JkIGEgPT4gaCBhIC0+IGggYSAKCmRhdGEgTGlzdEhlYXAgYSB3aGVyZSAKICAgIExIIDo6IE9yZCBhID0+IFthXSAtPiBMaXN0SGVhcCBhCgppbnNlcnRPcmRlcmVkIDo6IE9yZCBhID0+IGEgLT4gW2FdIC0+IFthXSAKaW5zZXJ0T3JkZXJlZCBhIFtdID0gW2FdIAppbnNlcnRPcmRlcmVkIGEgKHg6eHMpID0gaWYgYSA8IHggdGhlbiBhOng6eHMgZWxzZSB4OihpbnNlcnRPcmRlcmVkIGEgeHMpIAoKaW5zdGFuY2UgU2hvdyBhID0+IFNob3cgKExpc3RIZWFwIGEpIHdoZXJlCiAgICBzaG93IChMSCB4cykgPSAiTGlzdEhlYXAgIiArKyAoc2hvdyB4cykgCgppbnN0YW5jZSBIZWFwIExpc3RIZWFwIHdoZXJlCiAgICBlbXB0eSA9IExIIFtdCgogICAgaXNFbXB0eSAoTEggeHMpID0gbnVsbCB4cwoKICAgIGluc2VydCBhIChMSCB4cykgPSBMSCAkIGluc2VydE9yZGVyZWQgYSB4cwoKICAgIGZpbmRNaW4gKExIIFtdKSA9IGVycm9yICJFbXB0eSBoZWFwIgogICAgZmluZE1pbiAoTEggKHg6eHMpKSA9IHggCgogICAgZGVsZXRlTWluIChMSCBbXSkgPSBlcnJvciAiRW1wdHkgaGVhcCIKICAgIGRlbGV0ZU1pbiAoTEggKHg6eHMpKSA9IExIIHhzCgotLSBTdXBwb3NlIHRoZSBpbm5lciBzdHJ1Y3R1cmUgaXMgY29tcGxleCBzbyB3ZSBkb24ndCB3YW50Ci0tIHRvIHVzZSBpdCBkaXJlY3R5LCBidXQgd2Ugc3RpbGwgaGF2ZSB0byBwYXR0ZXJuLW1hdGNoIG9uIGl0Cmluc3RhbmNlIEZvbGRhYmxlIExpc3RIZWFwIHdoZXJlCiAgICBmb2xkTWFwIGYgaEAoTEggXykKICAgICAgfCBpc0VtcHR5IGggPSBtZW1wdHkKICAgICAgfCBvdGhlcndpc2UgPSBmIChmaW5kTWluIGgpIGBtYXBwZW5kYCBmb2xkTWFwIGYgKGRlbGV0ZU1pbiBoKQoKLS0gWWVwLCB3ZSBhcmUgZm9sZGFibGUhCmZyb21MaXN0IDo6IE9yZCBhID0+IFthXSAtPiBMaXN0SGVhcCBhCmZyb21MaXN0ID0gZm9sZHIgaW5zZXJ0IGVtcHR5CgptYWluID0gZG8gbGV0IGggPSBmcm9tTGlzdCBbMSwgNSwgMywgNywgOV0KICAgICAgICAgIHByaW50ICQgaW5zZXJ0IDEwIGg=