3 ms·

The Y combinator is a programming construct allowing one to write recursive functions without explicitly calling themselves (unnamed recursive functions): (d

• tlrobinson 16y ago
  I took the liberty of translating this to JavaScript, primarily to help me understand it, but thought I should share: // (define Y // (lambda (X) // ((lambda (procedure) // (X (lambda (arg) ((procedure procedure) arg)))) // (lambda (procedure) // (X (lambda (arg) ((procedure procedure) arg))))))) var Y = function(X) { return (function (procedure) { return X(function (arg) { return procedure(procedure)(arg); }); })(function (procedure) { return X(function (arg) { return procedure(procedure)(arg); }); }); } // (define F* // (lambda (func-arg) // (lambda (n) // (if (zero? n) // 1 // (* n (func-arg (- n 1))))))) var F = function(func_arg) { return function(n) { if (n === 0) return 1; else return n * func_arg(n - 1); }; } // (define fact (Y F*)) var fact = Y(F); // (write (fact 8)) console.log(fact(8));
  • tlrobinson 16y ago
    This will probably go unnoticed, but this function seems to be equivalent, at least for the factorial example. What's the difference? var Y = function(X) { var Z = X(function(arg) { return Z(arg); }); return Z; }
    • ostso 16y ago
      The difference is that the whole point of the Y combinator is that it's a fixed-point combinator that doesn't use explicit recursion. Imagine that you didn't have "var", and couldn't name anything (which is the situation in, say, the lambda calculus). Using the Y combinator you could still define recursive functions.