我不能理解Y-Combinator，所以我试着实现它，最后得到了一个更短的东西，它起作用了。那件事怎么可能？

Question

我不能理解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)。

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

Answer 1

它更短的原因是你实现的不是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自我应用程序时，因为这些语言是严格的。

Answer 2

与“真实”版本的不同之处在于，你确实需要传递你自己的函数和参数，通常你不需要这样做-Y通过给你的函数提供其自身的递归变量来进行抽象。

JavaScript中的Sum应为

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

当我将common JS expression重新构造为

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