在 Haskell 中,使用 fold、map 和 unfold 等高阶函数撰写尽可能多的代码是惯用法。那么,哪些代码不能使用这些高阶函数来编写?何时需要使用显式递归?
假设我们有一种没有递归或类似递归的语言。这意味着没有循环结构。这也意味着我们有(非递归的)类型,以便我们无法形成Y组合子并逃脱。在这种语言中,我们确实是弱的,与许多工具隔离开来。
但我们可以对这种语言提出一个非常好的问题。换句话说,我们必须给它什么最小的东西,才能使它变得和没有这样限制的语言一样强大?
结果有两个答案:
我们可以引入递归绑定器,如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
可以使用递归绑定器来实现。不太清楚的是,递归绑定器可以使用fix从非递归绑定器中实现,但我们在这里:
let x = fix $ \this -> e
this
指的是整个表达式,最终被绑定为x
,这正是我们想要的。
那么我为什么要费力说出上面的所有内容呢?
实际上,我想要证明,只要考虑到列表上的fix
,就不可能说递归一定通过HOF组合子(如map
)来实现。我还想主张,使用该组合子集实现的任何递归都可以使用递归绑定器“显式”完成。它们同样强大。
有趣的部分在于,当你单独考虑HOF组合子(如foldr
/unfoldr
)时,就会涉及到更多内容。这些技术上有些比fix
/递归绑定器要弱一些。优点是,如果你只使用一组类似foldr
/unfoldr
的原则来构建编程语言,则可以获得非常丰富的、次图灵完备的语言,其可以是total或保证终止。
map
和fold
是通过递归实现的。如果你在使用它们,从语义上讲,你就是在使用递归。从语法上讲,除了一次之外,你永远不需要使用递归 - 那就是定义“规范递归函数”的时候 -fix f = let x = f x in x
。 - user2407038fix
是作弊的 -- 一个诚实的程序员会说使用fix
的函数是递归的。在fix
下面有丰富的理论方案;请参阅著名的 Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire 进行处理。 - luquifix
方面可能不会表现得很好。 - dfeuerfix
实现多态递归,但是你需要一个新类型包装器来告诉 Haskell 你想要实例化的精确位置。 - J. Abrahamson