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