Monuses and Heaps

a day ago

Monuses are algebraic structures useful for algorithms involving ordered weights, particularly in heap-based algorithms.
A heap is a tree where each node's weight is less than or equal to its children's weights, supporting operations like popMin and insert.
Monuses support a partial subtraction operation (��) and are often positive monoids, such as the positive cone of a group.
The heap property can be represented by storing weight differences between nodes rather than absolute weights, enabling efficient global updates.
Pairing heaps in Haskell can be implemented using monuses to maintain the heap property and support efficient merging and sorting.
The Phases applicative transformer can be implemented using a pairing heap to reorder effects based on arbitrary keys while maintaining stability.
A stable heap can be achieved using a Key monus, which combines an ordered key with an offset to preserve the original order of equal keys.
The Search monadic heap uses monuses to store weight differences, enabling efficient monadic operations and collapsing of layers.

Hasty Briefsbeta