paperbot · PL 论文追踪

全部论文 待读 收藏

P2 More Fixpoints! (Functional Pearl)

更多不动点!(函数式 Pearl)
ICFP 7(ICFP)2023匹配度 1/10 · 该论文属于函数式编程(Haskell)中通过 unsafePerformIO 实现生产性递归定义的技术,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向均无直接关联。引用 1 inbox
Joachim Breitner
crossref: 2026-09-10

AI 速览

一句话:用不安全的 unsafePerformIO 实现可生产的纯布尔与集合结构,使 Haskell 递归定义不再落入黑洞。

Haskell 的惰性求值让程序员可用递归方程自然、声明式地解决问题,但当输入“过于递归”时,这些优雅写法会落入 black hole,使程序员不得不改用更笨拙的方法。本文构造了常见纯数据结构(布尔值与集合)的变体,使递归定义具有生产性(productive),从而避免发散。实现内部依赖声名狼藉的 unsafePerformIO,但对外仍暴露纯 API。由此,用户原本漂亮的递归惯用法可以再次“神奇地”工作。这是一篇函数式编程 pearl,展示了如何在不牺牲纯接口的前提下恢复递归定义的可用性。

问题
Haskell 中惰性递归定义在“过于递归”的输入下会导致 black hole,使原本优雅的递归惯用法无法使用。
方法
构造布尔值与集合等纯数据结构的变体,内部用 unsafePerformIO 实现生产性递归定义,同时对外保持纯 API。
评估
以函数式 pearl 的形式给出构造与递归惯用法示例,展示这些变体使原本失败的递归写法重新生效;摘要未报告系统化基准或形式化证明。
原文摘要(Abstract)

Haskell’s laziness allows the programmer to solve some problems naturally and declaratively via recursive equations. Unfortunately, if the input is “too recursive”, these very elegant idioms can fall into the dreaded black hole, and the programmer has to resort to more pedestrian approaches. It does not have to be that way: We built variants of common pure data structures (Booleans, sets) where recursive definitions are productive. Internally, the infamous unsafePerformIO is at work, but the user only sees a beautiful and pure API, and their pretty recursive idioms – magically – work again.

链接与引用

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

BibTeX
@article{paperbot1913,
  title = {More Fixpoints! (Functional Pearl)},
  author = {Joachim Breitner},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {ICFP},
  year = {2023},
  doi = {10.1145/3607853}
}