16

我无法理解 Y-combinator，所以我尝试实现一个在没有本地实现的情况下启用递归的函数。经过一番思考，我最终得出了这个结论：

Y = λx.(λv.(x x) v)

这比实际的短：

Y = λf.(λx.f (x x)) (λx.f (x x))

而且，令我惊讶的是，它奏效了。一些例子：

// JavaScript
Y = function(x){
  return function(v){
    return x(x, v);
  };
};
sum = Y(function(f, n){
  return n == 0 ? 0 : n + f(f, n - 1);
});
sum(4);

; Scheme
(define Y (lambda (x) (lambda (v) (x x v))))
(define sum (Y 
    (lambda (f n) 
        (if (equal? n 0) 
            0 
            (+ n (f f (- n 1)))))))
(sum 4)

两个片段都按预期输出 10（从 0 到 4 的总和）。

这是什么，为什么它更短，为什么我们更喜欢更长的版本？

4

2 回答 2

13

它更短的原因是您实现的不是Y 组合器。它介于实际的 Y 组合器和有时被称为 U 组合器之间的东西。要成为一个合适的 Y 组合器，这应该有效：

(define sum
  (Y (lambda (f)
       (lambda (v) (if (equal? n 0) 0 (+ n (f (- n 1))))))))

或在 Javascript 中：

sum = Y( function(f) { return function(n) {
  return n == 0 ? 0 : n + f(n-1);
};});

如果你按照自己的方式工作，你会发现会让它变长的一件事是你需要将复制f的东西移到 Y 中，而下一个让它变得更长的事情是当你结束时由于这些语言是严格的，因此可以保护x x函数内部的自应用程序。

于 2012-12-07T08:25:40.880 回答
6

与“真实”版本的区别在于，您确实需要传递自己的函数以及通常不需要的参数 - Y 通过为函数提供自身的递归变体来对其进行抽象。

JavaScript 中的 Sum 应该是

Y (function(rec){ return function (n) { return n==0 ? 0 : n + rec(n-1); };})

当我将常见的 JS 表达式重组为

function Y (f) {
    function alt (x) {
        function rec (y) { // this function is basically equal to Y (f)
             return x(x)(y); // as x === alt
        }
        return f (rec);
    }
    return alt(alt);
}
于 2012-12-07T08:33:59.927 回答