Heap -is:module

A min-heap of values of type a.

This type alias is an abbreviation for a HeapT which uses the HeapItem instance of pol item to organise its elements.

Heaps in Haskell A flexible Haskell implementation of minimum, maximum, minimum-priority, maximum-priority and custom-ordered heaps.

The program's heap is reaching its limit, and the program should take action to reduce the amount of live data it has. Notes:

• It is undefined which thread receives this exception. GHC currently throws this to the same thread that receives UserInterrupt, but this may change in the future.
• The GHC RTS currently can only recover from heap overflow if it detects that an explicit memory limit (set via RTS flags). has been exceeded. Currently, failure to allocate memory from the operating system results in immediate termination of the program.

HeapItem pol item is a type class for items that can be stored in a HeapT. A raw HeapT prio val only provides a minimum priority heap (i. e. val doesn't influence the ordering of elements and the pair with minimal prio will be extracted first, see HeapT documentation). The job of this class is to translate between arbitrary items and priority-value pairs (Prio pol item, Val pol item), depending on the policy pol to be used. This way, we are able to use HeapT not only as MinPrioHeap, but also as MinHeap, MaxHeap, MaxPrioHeap or a custom implementation. In short: The job of this class is to deconstruct arbitrary items into a (prio, val) pairs that can be handled by a minimum priority HeapT. Example: Consider you want to use HeapT prio val as a MaxHeap a. You would have to invert the order of a (e. g. by introducing newtype InvOrd a = InvOrd a along with an apropriate Ord instance for it) and then use a type MaxHeap a = HeapT (InvOrd a) (). You'd also have to translate every x to (InvOrd x, ()) before insertion and back after removal in order to retrieve your original type a. This functionality is provided by the HeapItem class. In the above example, you'd use a MaxHeap. The according instance declaration is of course already provided and looks like this (simplified): @data MaxPolicy instance (Ord a) => HeapItem MaxPolicy a where newtype Prio MaxPolicy a = MaxP a deriving (Eq) type Val MaxPolicy a = () split x = (MaxP x, ()) merge (MaxP x, _) = x instance (Ord a) => Ord (Prio MaxPolicy a) where compare (MaxP x) (MaxP y) = compare y x @ MaxPolicy is a phantom type describing which HeapItem instance is actually meant (e. g. we have to distinguish between MinHeap and MaxHeap, which is done via MinPolicy and MaxPolicy, respectively) and MaxP inverts the ordering of a, so that the maximum will be on top of the HeapT. The conversion functions split and merge have to make sure that

1. forall p v. split (merge (p, v)) == (p, v) (merge and split don't remove, add or alter anything)
2. forall p v f. fst (split (merge (p, f v)) == fst (split (merge (p, v))) (modifying the associated value v doesn't alter the priority p)