Я не мог понять Y-Combinator, поэтому я попытался его реализовать и закончил что-то более короткое, что сработало. Как это возможно?

Я не мог понять 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), как ожидалось.

Что это, почему оно короче и почему мы предпочитаем более длинную версию?

Ответ 1

Причина, по которой она короче, заключается в том, что вы реализовали не Y combinator. Это нечто, что находится между фактическим Y combinator и тем, что иногда называют U-комбинатором. Чтобы быть правильным Y combinator, это должно работать:

(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 внутри функции, поскольку этот язык является строгим.

Ответ 2

Отличие от "реальной" версии заключается в том, что вам нужно передать свою собственную функцию вместе с параметрами, которые вам обычно не нужны - Y делает абстрактным над этим, предоставляя вашей функции вариант рекурсии.

Сумма в JavaScript должна быть просто

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

Я понял Y combinator, когда я изменил общее выражение 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);
}