Unscanning by Möbius Inversion (Functional Pearl)

This pearl presents the classical Möbius inversion theorem for posets as a calculation method for inverting scan-like cumulative computations. We model a scan function as summation over principal down-sets of a lower-finite poset: local values are accumulated according to the order. From this specification, the inverse can be derived directly as a recursion. When this recursion is expanded as a linear combination of cumulative values, the coefficients obtained are precisely the Möbius coefficients of the poset. In this way, the usual theorem gives the algebraic justification, while the calculation shows where the coefficients come from in the inverse problem. We then use a cancellation law to identify the nonzero coefficients, which determines which cumulative values are actually needed in each unscan rule. Because this sparsity pattern is determined only by the indexing order, the same calculation can be reused across different data structures. We illustrate the method with five standard examples: prefix sums on lists, summed-area tables on grids, subtree sums on trees, subset sums, and divisor sums.