Я не мог понять 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);
}