No pude entender el Y-Combinator, así que traté de implementarlo y terminé con algo más corto, que funcionó. ¿Cómo es eso posible?
No pude entender el Y-combinator, así que intenté implementar una función que permitiera la recursión sin implementación nativa. Después de pensar un poco, terminé con esto:
Y = λx.(λv.(x x) v)
Que es más corto que el actual:
Y = λf.(λx.f (x x)) (λx.f (x x))
Y, para mi sorpresa, funcionó. Algunos ejemplos:
// 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)
Ambos fragmentos de código de salida 10 (suma de 0 a 4) como se esperaba.
¿Qué es esto, por qué es más corto y por qué preferimos la versión más larga?