我无法理解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的总和应该是

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