Ich konnte den Y-Combinator nicht verstehen, also habe ich versucht, ihn zu implementieren und etwas Kürzeres gefunden, das funktioniert hat. Wie ist das möglich?
Ich konnte den Y-Kombinator nicht verstehen und habe versucht, eine Funktion zu implementieren, die eine Rekursion ohne native Implementierung ermöglicht. Nach einigem Nachdenken kam ich zu folgendem Ergebnis:
Y = λx.(λv.(x x) v)
Welches ist kürzer als das eigentliche:
Y = λf.(λx.f (x x)) (λx.f (x x))
Und zu meiner Überraschung hat es funktioniert. Einige Beispiele:
// 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)
Beide Snippets geben erwartungsgemäß 10 (Summation von 0 bis 4) aus.
Was ist das, warum ist es kürzer und warum bevorzugen wir die längere Version?