GoKawiilMonuses and Heaps
Posted on March 3, 2026
This post is about a simple algebraic structure that I have found useful for algorithms that involve searching or sorting based on some ordered weight. I used it a bit in a pair of papers on graph search (2021; 2025), and more recently I used it to implement a version of the Phases type (Easterly 2019) that supported arbitrary keys, inspired by some work by Blöndal (2025a; 2025b) and Visscher (2025).
The algebraic structure in question is a monus, which is a kind of monoid that supports a partial subtraction operation (that subtraction operation, denoted by the symbol ∸, is itself often called a “monus”). However, before giving the full definition of the structure, let me first try to motivate its use. The context here is heap-based algorithms. For the purposes of this post, a heap is a tree that obeys the “heap property”; i.e. every node in the tree has some “weight” attached to it, and every parent node has a weight less than or equal to the weight of each of its children. So, for a tree like the following:
The heap property is satisfied when a ≤ b a \leq b , a ≤ c a \leq c , b ≤ d b \leq d , and b ≤ e b \leq e .
Usually, we also want our heap structure to have an operation like popMin :: Heap k v -> Maybe (v, Heap k v) that returns the least-weight value in the heap paired with the rest of the heap. If this operation is efficient, we can use the heap to efficiently implement sorting algorithms, graph search, etc. In fact, let me give the whole basic interface for a heap here:
popMin :: Heap k v -> Maybe (v, Heap k v) k v(v,k v) insert :: k -> v -> Heap k v -> Heap k v k vk v empty :: Heap k v k v
Using these functions it’s not hard to see how we can implement a sorting algorithm:
sortOn :: (a -> k) -> [a] -> [a] (ak)[a][a] = unfoldr popMin . foldr (\x -> insert (k x) x) empty sortOn kunfoldr popMin(\xinsert (k x) x) empty
The monus becomes relevant when the weight involved is some kind of monoid. This is quite a common situation: if we were using the heap for graph search (least-cost paths or something), we would expect the weight to correspond to path costs, and we would expect that we can add the costs of paths in a kind of monoidal way. Furthermore, we would probably expect the monoidal operations to relate to the order in some coherent way. A monus (Amer 1984) is an ordered monoid where the order itself can be defined in terms of the monoidal operations :
... continue reading