OCaml 中的匿名递归函数

Question

如何创建一个匿名递归函数（简单的函数，例如阶乘 n？）我听说这是可能的，但不知道如何使其在 OCaml 中工作。

let a =
  fun x -> ....

我只是不知道如何继续下去...

Answer 1

让我尝试扩展一下杰弗里·斯科菲尔德的答案。阶乘函数的非匿名递归定义可以是

let rec fact n =
    if n < 2 then 1 else n * fact (n - 1)

当您尝试定义匿名递归函数时遇到的第一个问题是如何执行实际的递归调用（fact (n - 1)在我们的例子中）。对于调用，我们需要一个名称，但我们没有匿名函数的名称。解决方案是使用临时名称。使用临时名称f，定义主体只是

fun n -> if n < 2 then 1 else n * f (n - 1)

该术语没有类型，因为“临时名称”f未绑定。f但我们也可以通过边界将其转换为具有类型的值。让我们称结果为g：

let g = fun f n -> if n < 2 then 1 else n * f (n - 1)

g目前还没有匿名，但只是因为我想再次提及它。观察其g类型为(int -> int) -> (int -> int)。我们想要的（阶乘函数）的类型为(int -> int)。因此，g采用我们想要的类型（在本例中为函数类型）并生成相同类型的内容。直觉是它g采用阶乘函数的近似值，即f适用于所有n直到某个限制 N 的函数并返回更好的近似值，即适用于所有直到 N+1 的函数n。

最后，我们需要一些可以变成g实际递归定义的东西。这样做是一项非常通用的任务。回想一下，这g提高了近似质量。最终的阶乘函数fact是无法进一步改进的。所以申请gtofact应该和 just 一样fact。（实际上，这仅从值的角度来看是正确的。g fact nfor some中固有的实际计算与n的计算不同fact n。但返回的值是相同的。）换句话说，fact是 的一个不动点g。所以我们需要的是计算不动点的东西。

幸运的是，有一个函数可以做到这一点：Y 组合器。从值的角度来看，Y 组合器（让我们y在 OCaml 中使用，因为大写字母是为构造函数保留的）是由以下事实定义的：y g = g (y g)对于所有g：给定某个函数g，组合器返回其固定点之一。最后，

y : (`a -> `a) -> `a

在我们的例子中，类型变量由 实例化(int -> int)。一种可能的定义方法y是

let y = fun g -> (fun x -> g (x x)) (fun x -> g (x x))

但这仅适用于惰性求值（我相信 Haskell 就是这样）。由于 OCaml 具有急切求值功能，因此在使用时会产生堆栈溢出。原因是 OCaml 试图将类似的东西y g 8变成

g (y g) 8
g (g (y g)) 8
g (g (g (y g))) 8
...

从来没有打电话过g。解决方案是在 内部使用延迟计算y：

let y = fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a)

一个缺点是它y不再适用于任意类型。它仅适用于函数类型。

y : ((`b -> `c) -> (`b -> `c)) -> (`b -> `c)

但无论如何，您都要求函数的递归定义，而不是其他值的递归定义。因此，我们对阶乘函数的定义是y g和y，g定义如上。y两者都不是g匿名的，但这可以很容易地解决：

(fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a))
    (fun f n -> if n < 2 then 1 else n * f (n - 1))

更新：

定义y仅适用于-rectypes选项。原因是我们应用于x自身。