OCaml中的匿名递归函数

Question

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

let a =
  fun x -> ....

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

- GraphLearner

Answer 1

以下是只使用匿名函数定义阶乘的定义：

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

这需要使用-rectypes标志。

下面是一个会话，展示了它的工作原理:

$ rlwrap ocaml -rectypes
        OCaml version 4.03.0

let fact =
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a))
    (fun f n -> if n < 2 then 1 else n * f (n - 1));;
val fact : int -> int = <fun>
# fact 8;;
- : int = 40320

我有点作弊，参考了这里的Y Combinator：Rosetta Code: Y Combinator

更新

免责声明：如果您从我这里获取信息而不是阅读关于λ演算、不动点和Y组合子的知识，那么建议您最好去看正式的介绍。我只是一个谦虚的实践者，不是理论家。

跟踪实际计算几乎是不可能的（但肯定值得一做）。但从高层次来看，其思路如下。

定义的第一行是Y组合子，在一般情况下计算函数的不动点。这恰好是递归函数是从函数到函数的函数的不动点。

所以第一个目标是找到其不动点为阶乘函数的函数。这就是定义的第二行。如果您给它一个类型为int -> int的函数，它将返回另一个类型为int -> int的函数。如果您把阶乘函数给它，它将返回阶乘函数。这意味着阶乘函数是其不动点。

因此，当您将Y组合子应用于该函数时，确实会得到阶乘函数。

- Jeffrey Scofield

---

我已经修改了我的答案，但这是一个很大的话题。而我只知道很少一部分。 - Jeffrey Scofield

@JeffreyScofield 你可以通过定义类似 type t = T of t -> t 的东西来避免使用 -rectypes。喜欢你的回答。 - PatJ

是的，这在上面链接的Y Combinator页面上有解释。谢谢！ - Jeffrey Scofield

Answer 2

让我稍微解释一下Jeffrey Scofield的答案。非匿名递归定义阶乘函数可以表示为：

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接受阶乘函数的近似值，即适用于所有n直到某个限制N的函数f，并返回更好的近似值，即适用于所有n直到N + 1的函数。

最后我们需要将g转化为实际的递归定义。这是一个非常通用的任务。回想一下g提高了近似质量。最终的阶乘函数fact是无法进一步改进的。因此将g应用于fact应该与仅使用fact相同。换句话说，fact是g的不动点。因此，我们需要计算不动点的东西。

幸运的是，有一个单一的函数可以这样做：Y组合子。从值的角度来看，Y组合子（让我们在OCaml中使用y，因为大写字母是保留给构造函数的）的定义是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
...

解决方案是在y内使用延迟计算，而不需要调用 g。

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))

更新：

只有使用-rectypes选项才能定义y。原因是我们将x应用于自身。

- kne

Answer 3

还有一种“直观”的方法可以实现匿名递归，而不需要使用Y组合器。

它利用let绑定来存储接受自身作为参数的lambda表达式的值，以便可以使用自身作为第一个参数调用自身，例如：

let fact = (let fact0 = (fun self n -> if n < 2 then 1 else n * self self (n - 1)) in (fun n -> fact0 fact0 n));;

只有在未使用 let rec 定义时，它才是匿名的。

- Hypertable