javascript - 我无法理解 Y-Combinator，所以我尝试实现它并最终得到了一些更短的东西，但它起作用了。这怎么可能？

Question

我无法理解 Y 组合器，因此我尝试实现一个无需 native 实现即可启用递归的函数。经过一番思考，我得出了这样的结论:

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 自应用程序时，因为这些语言是严格的。