CODEWITHSUNDEEP
javascriptrecursionfunctional-programmingschemey-combinator
MaiaVictor
MaiaVictor

Reputation: 52977

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.(λ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?

Upvotes: 17

Views: 990

Answers (2)

Bergi
Bergi

Reputation: 664494

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);
}

Upvotes: 6

Eli Barzilay
Eli Barzilay

Reputation: 29546

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.

Upvotes: 13

Related Questions