paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Unscanning by Möbius Inversion (Functional Pearl)

基于 Möbius 反演的逆扫描(函数式珍珠)
ICFP 10(ICFP)2026匹配度 1/10 · 该论文属于函数式编程与代数计算/算法推导领域,讨论偏序集上的 Möbius 反演及其在逆扫描中的应用,与用户关注的 LLM/Agent 静态分析、浮点程序分析、贝叶斯程序分析及 AI 与 PL 交叉方向没有直接关联。引用 0 inbox
Keisuke Nakano
crossref: 2026-09-10

AI 速览

一句话:将偏序集上的 Möbius 反演用作逆扫描计算,导出递归规则、系数稀疏性并跨数据结构复用。

本文是一篇函数式珍珠,指出经典偏序集 Möbius 反演可视为逆扫描这类累积计算的通用计算方法。作者把扫描函数建模为在下有限偏序集的主下集上求和:局部值按偏序累积。由此可直接导出逆问题的递归式;将递归展开为累积值的线性组合时,系数恰为偏序集的 Möbius 系数。于是经典定理给出代数依据,计算则揭示系数来源。作者进一步用消去律确定非零系数,得到每个逆扫描规则实际需要的累积值,且稀疏模式仅由索引顺序决定,因此可在不同数据结构间复用。文中用五个标准例子说明:列表前缀和、网格求和面积表、树子树和、子集和与除数和。

问题
如何系统地反转 scan 类累积计算,即由累积值恢复局部值,并解释逆规则中系数来源及实际所需的累积值。
方法
把 scan 建模为下有限偏序集主下集上的求和,从该规约直接导出逆递归,再利用 Möbius 反演与消去律得到系数和稀疏模式。
评估
在列表前缀和、网格求和面积表、树子树和、子集和与除数和五个标准例子上演示方法的适用性与跨数据结构复用。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@article{Nakano26,
  title = {Unscanning by Möbius Inversion (Functional Pearl)},
  author = {Keisuke Nakano},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {ICFP},
  year = {2026},
  doi = {10.1145/3828710}
}