I couldn't understand the Y-binator, so I tried to implement a function that enabled recursion without native implementation. After some thinking, I ended up with this:
Y = λx.(λv.(x x) v)
Which is shorter than the actual one:
Y = λf.(λx.f (x x)) (λx.f (x x))
And, for my surprise, worked. Some examples:
// 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)
Both snippets output 10 (summation from 0 to 4) as expected.
What is this, why it is shorter and why we prefer the longer version?
I couldn't understand the Y-binator, so I tried to implement a function that enabled recursion without native implementation. After some thinking, I ended up with this:
Y = λx.(λv.(x x) v)
Which is shorter than the actual one:
Y = λf.(λx.f (x x)) (λx.f (x x))
And, for my surprise, worked. Some examples:
// 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)
Both snippets output 10 (summation from 0 to 4) as expected.
What is this, why it is shorter and why we prefer the longer version?
Share Improve this question edited Dec 23, 2012 at 9:05 MaiaVictor asked Dec 7, 2012 at 8:07 MaiaVictorMaiaVictor 53k47 gold badges157 silver badges301 bronze badges 6- Uh, it is shorter because it is in another language? I'm not fluent in Scheme, but it seems the JS and Scheme definitions are equivalent. What is your question exactly? "Why aren't we all writing in the tersest language possible?" – lanzz Commented Dec 7, 2012 at 8:15
- i don't even now which part you mean. Do you mean the JS part because you added linebreaks or the scheme part because you left all line breaks out? This question doesn't make any sense. – zhujik Commented Dec 7, 2012 at 8:18
- 3 The question is clearly language independent. This "Y binator" is in both cases shorter than the actual one. – Eli Barzilay Commented Dec 7, 2012 at 8:20
- 1 Sorry, I assumed you're paring your JS implementation against the Scheme code. And no, I did not downvote you. – lanzz Commented Dec 7, 2012 at 8:25
-
1
The JS and Scheme implementations aren't equivalent to the λ-calculus version, as they pass
xtox, instead of passing the application ofxtovtox. What you've implemented isY = λx.(λv.(x x) v). – outis Commented Dec 22, 2012 at 23:58
2 Answers
Reset to default 13The reason it is shorter is that what you implemented is not the Y binator. It's something that is between the actual Y binator, and something that is sometimes known as a U binator. To be a proper Y binator, this should work:
(define sum
(Y (lambda (f)
(lambda (v) (if (equal? n 0) 0 (+ n (f (- n 1))))))))
or in Javascript:
sum = Y( function(f) { return function(n) {
return n == 0 ? 0 : n + f(n-1);
};});
If you work your way to something that makes that work, you'll find that one thing that will make it longer is that you need to move the duplicated f thing into the Y, and the next thing that makes it even longer is when you end up protecting the x x self-application inside a function since these language are strict.
The difference from the "real" version is that you do need to pass your own function along with the parameters, which you usually don't need to - Y does abstract over that by giving your function the recursice variant of itself.
Sum in JavaScript should be just
Y (function(rec){ return function (n) { return n==0 ? 0 : n + rec(n-1); };})
I understood the Y binator when I restructured the mon JS expression to
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);
}