I couldn't understand the Y-Combinator, so I tried to implement it and ended up with something shorter, which worked. How is that possible?

Question

I couldn't understand the Y-combinator, 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?

Foresheet

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?" – Bluh

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. – Viviyan

@Bluh do you know the Y-Combinator? It's bigger than the example I provided in both languages. I posted them so it could be comprehended by more people. If that was the reason you downvoted please reconsider, you are mistaken. – Foresheet

The question is clearly language independent. This "Y combinator" is in both cases shorter than the actual one. – Edirne

Sorry, I assumed you're comparing your JS implementation against the Scheme code. And no, I did not downvote you. – Bluh

The JS and Scheme implementations aren't equivalent to the λ-calculus version, as they pass x to x, instead of passing the application of x to v to x. What you've implemented is Y = λx.(λv.(x x) v). – Crazyweed

Answer 1

The reason it is shorter is that what you implemented is not the Y combinator. It's something that is between the actual Y combinator, and something that is sometimes known as a U combinator. To be a proper Y combinator, 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.

Edirne

Great answer, thanks! Why we prefer the Y-combinator over the U-combinator, though? Edit: oh, wait, mine's not the U-Combinator, which is still simpler. Is there a name for this one? – Foresheet

@Dokkat: The main point of the actual version is that the code does not change -- you don't need to know that you're doing a recursive call or calling any other function. (Also, I don't know if there's a name for your version.) – Edirne

@Viclib your lambda calc can be simplified to λx. (x x) which is the U-combinator. However, to implement and use it (in javascript) the way you have done here, you need to prevent immediate recursion by wrapping (x x) in (λv. ... v), thus: λx. λv. (x x) v. This is because javascript uses applicative order evaluation and lambda calc uses normal order. Not surprisingly, the Y-combinator is even more easily expressed using the U-combinator. Y := (U (λf. λx.f (x x))) which expands to (λf. λx.f (x x)) (λf. λx.f (x x)). – Osteopathy

@naomik a little late but fair enough! – Foresheet

Answer 2

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 combinator when I restructured the common 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);
}

Callahan

Great explanation, the "Y does abstract over that by giving your function the recursice variant of itself." part made it very clear. Thank you! – Foresheet

What I could not understand a long time was that the two alt functions were basically the same and calling each other alternatingly. – Callahan

In many functional languages, the "shortcut" of defining a function once and applying it on itself is not really making things much shorter. Also, your this function is basically equal to Y comment is wrong -- that function is actually equal to x(x) except that it prevents the infinite loop that you normally get; it's just a device that delays the self-calling loop so it happens only when it's needed. – Edirne

@EliBarzilay: You are right; and I'm currently working too much with a lazy evaluating language :-) – Callahan