何时需要显式递归？

Question

在 Haskell 中，使用 fold、map 和 unfold 等高阶函数撰写尽可能多的代码是惯用法。那么，哪些代码不能使用这些高阶函数来编写？何时需要使用显式递归？

- Ramith Jayatilleka

---

你是在询问递归何时是“必要的”还是何时是“惯用的”？你的标题说的是前者，而你的最后一句话则是后者。 - Christian Conkle

好问题。我有点想知道两个问题，但我会限制为一个问题：何时需要显式递归？我会编辑这个问题。 - Ramith Jayatilleka

高阶函数如map和fold是通过递归实现的。如果你在使用它们，从语义上讲，你就是在使用递归。从语法上讲，除了一次之外，你永远不需要使用递归 - 那就是定义“规范递归函数”的时候 - fix f = let x = f x in x。 - user2407038

但是 fix 是作弊的 -- 一个诚实的程序员会说使用 fix 的函数是递归的。在 fix 下面有丰富的理论方案；请参阅著名的 Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire 进行处理。 - luqui

从Haskell的角度来看，计算理论只能走到这里——多态递归在fix方面可能不会表现得很好。 - dfeuer

你可以使用 fix 实现多态递归，但是你需要一个新类型包装器来告诉 Haskell 你想要实例化的精确位置。 - J. Abrahamson

Answer 1

假设我们有一种没有递归或类似递归的语言。这意味着没有循环结构。这也意味着我们有（非递归的）类型，以便我们无法形成Y组合子并逃脱。在这种语言中，我们确实是弱的，与许多工具隔离开来。

但我们可以对这种语言提出一个非常好的问题。换句话说，我们必须给它什么最小的东西，才能使它变得和没有这样限制的语言一样强大?

结果有两个答案:

1. 我们可以引入递归绑定器，如let rec命令或像Haskell的let一样始终为let rec。换句话说，一个结构，它让我们定义let x = e in b，使得如果x在e中是自由的，则将其计算为方程x = e上的不动点。

2. 我们可以引入函数fix :: (a -> a) -> a，使得fix f在一步内缩减为f (fix f)。

从上述演示中可以清楚地看出，fix可以使用递归绑定器来实现。不太清楚的是，递归绑定器可以使用fix从非递归绑定器中实现，但我们在这里:

let x = fix $ \this -> e

this指的是整个表达式，最终被绑定为x，这正是我们想要的。

---

那么我为什么要费力说出上面的所有内容呢？

实际上，我想要证明，只要考虑到列表上的fix，就不可能说递归一定通过HOF组合子（如map）来实现。我还想主张，使用该组合子集实现的任何递归都可以使用递归绑定器“显式”完成。它们同样强大。

有趣的部分在于，当你单独考虑HOF组合子（如foldr/unfoldr）时，就会涉及到更多内容。这些技术上有些比fix/递归绑定器要弱一些。优点是，如果你只使用一组类似foldr/unfoldr的原则来构建编程语言，则可以获得非常丰富的、次图灵完备的语言，其可以是total或保证终止。

- J. Abrahamson

Answer 2

我认为很多人觉得递归数据定义比Mu/Fix/Nu类型更易读。虽然不是必需的，但在那里非常有用。

同样地，您将通过使用递归来编写这种数据类型的可折叠/可展开实例，但一旦提供了这些实例，以后就不需要显式递归了。

- Boyd Stephen Smith Jr.