recursion - OCaml 中的匿名递归函数

Question

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

let a =
  fun x -> ....

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

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 标志。

这是一个显示它有效的 session :

$ 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

更新

免责声明:您最好阅读 lambda 演算、不动点和 Y 组合器，而不是从我这里获取信息。我不是理论家，只是一个谦虚的实践者。

遵循实际计算几乎是不可能的(但我确信绝对值得这样做)。但从高层次来看，想法是这样的。

定义的第一行是 Y Combinator，它通常计算函数的不动点。恰好递归函数就是函数从函数到函数的不动点。

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

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