Stephan Friedrichs wrote:
I just uploaded a generalised heap (min-, max- and custom-heaps) implementation:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/heap-0.1
Feedback would be appreciated :)
Feedback: I think the HeapPolicy thing is too non-standard. The canonical way would be to use a MinHeap and let the Ord instance handle everything. A MaxHeap can then be obtained via a different Ord instance newtype Ord a => Reverse a = Reverse { unReverse :: a } instance Ord a => Ord (Reverse a) where compare = comparing unReverse This newtype should be in Data.Ord, of course. Being minimum/maximum-agnostic seems like a noble goal but turns out not to be that good. To see why, I'd like to report the first documentation bug: will a custom heap's head be the minimum or the maximum with respect to a custom heapCompare ? (ok, the docs for head indicate minimum, but the docs for HeapPolicy should say so, too.) Simply setting type MaxHeap a = MinHeap (Reverse a) is inferior to a "native" MaxHeap since we'd have to pack/unpack the Reverse all the time. But a type class for heaps - which should be present anyway - can solve that problem: class Heap h where empty :: h a insert :: Ord a => a -> h a -> h a viewHead :: Ord a => h a -> Maybe (a, h a) fromAscList :: Ord a => [a] -> h a toAscList :: Ord a => h a -> [a] null :: Ord a => h a -> Bool null = isNothing . viewHead singleton :: Ord a => a -> h a singleton = flip insert empty head :: Ord a => h a -> a head = fst . fromJust . viewHead deleteHead :: Ord a => h a -> h a deleteHead = maybe empty snd . viewHead ... etc. instance Heap MinHeap where ... newtype MaxHeap a = M (MinHeap (Reverse a)) instance Heap MaxHeap where ... The union and unions functions are probably best not put in this class but implemented via separate Monoid instances. In conclusion: the ordering policy stuff should not be part of Data.Heap, this is a job for Data.Ord. In particular, Data.Ord might contain something like newtype OrdBy p a = OrdBy { unOrdBy :: a } class OrdPolicy p a where ... instance OrdPolicy p a => Ord (OrdBy p a) where ... which can then be used to implement heaps with such different orderings in one go: newtype OrdPolicy p a => HeapP p a = HeapP (MinHeap (OrdBy p a)) instance Heap (HeapP p) where ... Regards, apfelmus