Я не мог понять Y-Combinator, поэтому я попытался реализовать его и в итоге получил что-то более короткое, что сработало. Как это возможно?
Я не могЯ не понимаю Y-комбинатор, поэтому я попытался реализовать функцию, которая включала рекурсию без собственной реализации. Подумав немного, я закончил с этим:
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), как и ожидалось.
Что это, почему оно короче и почему мы предпочитаем более длинную версию?