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?

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.

Solution 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) { returnfunction(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.

Solution 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){ returnfunction (n) { return n==0 ? 0 : n + rec(n-1); };})

I understood the Y combinator when I restructured the common JS expression to

functionY (f) {
    functionalt (x) {
        functionrec (y) { // this function is basically equal to Y (f)returnx(x)(y); // as x === alt
        }
        return f (rec);
    }
    returnalt(alt);
}