haskell - 什么时候需要显式递归？

Question

在 Haskell 中，将尽可能多的代码写在高阶函数(如折叠、映射和展开)中是惯用的。那么什么样的代码不能用那些高阶函数编写呢？什么时候需要显式递归？

Answer 1

假设我们有一种没有递归或类似的语言。这也意味着没有循环结构。这也意味着我们也有(非递归)类型，因此我们不能形成 Y 组合器并转义。在这种语言中，我们真的很弱，与我们的许多工具分开。

但是我们可以就这种语言提出一个非常好的问题。也就是说，为了让它变得像没有这种限制的语言一样强大，我们必须给予它最小的东西是什么？

原来有两个答案。

我们可以引入递归绑定(bind)器，例如 let rec命令或类似 Haskell 的 let始终为 let rec .换句话说，一个让我们定义 let x = e in b 的结构。这样如果 x在 e 中免费然后将其计算为方程 x = e 上的不动点.

我们可以介绍函数fix :: (a -> a) -> a这样fix f一步减少到f (fix f) .

从上面的介绍中应该可以清楚地看到 fix可以使用递归绑定(bind)器来实现。不太清楚的是递归绑定(bind)器可以使用修复从非递归绑定(bind)器实现，但这里我们是:

let x = fix $ \this -> e

值 this指的是最终绑定(bind)为 x 的整个表达式这正是我们想要的。

那么，为什么我会特意说出以上所有内容呢？

本质上，我想说的是，不可能说递归一定是通过像 map 这样的 HOF 组合子实现的。只要你愿意考虑 fix在那个名单上。我还想争辩说，该集合中的组合器实现的任何递归都可以使用递归绑定(bind)器“显式”完成。他们同样强大。

当您考虑像 foldr 这样的 HOF 组合子时，有趣的部分就出现了。/ unfoldr通过他们自己。这些在技术上比 fix 要弱一些。/递归绑定(bind)器。优点是，如果您仅使用一组精选的 foldr 构建编程语言，/ unfoldr -like 原则，那么您可以获得非常丰富的子图灵完整语言，可以完全或保证终止。