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的旗。

这里显示出它的工作原理会话：

$ 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 Combinator，而不是从我那里获取信息。我不是理论家，只是一个不起眼的修炼者。

以下的实际计算几乎是不可能的（但绝对值得我确信）。但高层次的想法就是这样。

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

因此，第一个目标是找到其固定点是阶乘函数的函数。这是定义的第二行。如果你给它一个类型为int -> int的函数，它会让你回到int -> int类型的另一个函数。如果你给它的阶乘函数，它会让你回到阶乘函数。这意味着阶乘函数是它的固定点。

那么，当你将Y Combinator应用到这个函数时，你确实得到了阶乘函数。

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

最后，我们需要一些将g变成实际递归定义的东西。 这样做是非常通用的任务。回想一下g提高了逼近质量。最终阶乘函数fact是一个不能进一步改进的函数。因此，将g应用于fact应与fact相同。 （实际上，从价值的角度来看，这只是真的，g fact n对于某些n的实际计算与fact n的实际计算不同，但返回的值是相同的）。换句话说，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 
... 

而没有得到调用g。 的解决方案是使用的y内递延计算：

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

一个缺点是y不任意类型的工作了。它只适用于函数类型。

​​

但是你问函数的递归定义，而不是其他值的递归定义。因此，我们对阶乘函数的定义是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)) 

UPDATE：

定义y只与-rectypes选项的作用。原因是我们自己申请了x。