An exploration of the monus algebraic structure and its application to heap-based algorithms in Haskell. A monus is an ordered monoid supporting partial subtraction, useful for representing heap weights as differences rather than absolute values. The post covers pairing heap implementation using monuses, derives an efficient

14m read time From doisinkidney.com
Post cover image
Table of contents
Monuses in HaskellPairing Heaps in HaskellRetrieving a Normal HeapPhases as a Pairing HeapStabilising PhasesLocal Computation in a Monadic HeapConclusion

Sort: