Eu não conseguia entender o Y-Combinator, então tentei implementá-lo e acabei com algo mais curto, o que funcionou. Como isso é possível?
Eu não consegui entender o Y-combinator, então tentei implementar uma função que permitisse a recursão sem implementação nativa. Depois de pensar um pouco, acabei com isso:
Y = λx.(λv.(x x) v)
Qual é mais curto que o real:
Y = λf.(λx.f (x x)) (λx.f (x x))
E, para minha surpresa, funcionou. Alguns exemplos:
// 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)
Os dois fragmentos emitem 10 (soma de 0 a 4) conforme o esperado.
O que é isto, porque é mais curto e porque preferimos a versão mais longa?