paperbot · PL 论文追踪

全部论文 待读 收藏

P2 An optimal, purely functional implementation of the Garsia–Wachs algorithm

Garsia–Wachs 算法的最优纯函数式实现
JFP vol.302020匹配度 1/10 · 该论文研究 Garsia–Wachs 算法的纯函数式实现，属于函数式编程与算法实现方向，与用户画像中的静态分析、ML/Agentic 程序分析、浮点程序分析、贝叶斯程序分析及 LLM 与 PL 交叉均无直接关联。引用 2 inbox
RICHARD S. BIRD
函数式编程
dblp: 2026-09-10crossref: 2026-09-10

AI 速览

一句话：给出 Garsia–Wachs 算法的纯函数式实现，在保持最优叶树构造的同时达到 O(n log n) 时间。

论文讨论 Garsia–Wachs 算法：给定输入序列，构造一棵叶子顺序恰好等于该序列且总代价最小的二叉叶树。该问题与 Huffman 编码类似，但额外要求叶子的排列固定，不能任意置换。作者给出该算法的纯函数式实现，并证明其运行时间为 O(n log n)，即对长度为 n 的输入只需线性对数步，与 Huffman 编码的时间界相同。该工作展示了如何以纯函数式风格有效地实现这一最优树构造算法。

问题
构造叶子顺序固定且总代价最小的二叉叶树，即带顺序约束的 Huffman 树构造问题。
方法
用纯函数式风格实现 Garsia–Wachs 算法，并分析其运行时间。
评估
通过对长度为 n 的输入进行渐近运行时间分析，得到 O(n log n) 的上界。
原文摘要（Abstract）

The Garsia–Wachs algorithm is an algorithm for building a binary leaf tree whose cost is as small as possible. The problem and the algorithm are described in more detail below, but the task is essentially the same as that of building a Huffman coding tree with the added constraint that the fringe of the tree has to be exactly the given list of inputs (in Huffman coding, the fringe of the tree can be any permutation of the input). As we will show below, the Garsia–Wachs algorithm can be implemented with a linearithmic running time—a running time of O ( n log n ) steps for an input of length n , the same time bound as for Huffman coding.

链接与引用

DOI 原文 · PDF（开放获取） · DBLP

BibTeX 
@article{Bird20,
  title = {An optimal, purely functional implementation of the Garsia–Wachs algorithm},
  author = {RICHARD S. BIRD},
  journal = {Journal of Functional Programming},
  volume = {30},
  year = {2020},
  doi = {10.1017/s0956796819000194}
}