Y-combinator

index.js

"use strict";

function recur (f) {
  return f(f);
}

function wrap (h) {
  return recur(function (f) {
    return h(function (n) {
      return f(f)(n);
    });
  });
}


var Y = function (h) {
  return (function (f) {
    return f(f);
  }(function (f) {
    return h(function (n) {
      return f(f)(n);
    });
  }));
};


// step 0 – base factorial
var fact0 = function (n) {
    return n < 2 ? 1 :
           n * fact0(n - 1);
};

// step 1
var fact1 = (function (f) {
    return function (n) {
      return n < 2 ? 1 :
             n * f(f)(n - 1);
    };
})(function (f) {
    return function (n) {
      return n < 2 ? 1 :
             n * f(f)(n - 1);
    };
});

// step 2
var fact2 = recur(function (f) {
  return function (n) {
    return n < 2 ? 1 :
           n * f(f)(n - 1);
  };
});

// step 3
var fact3 = recur(function (f) {
  var g = function (n) {
    return f(f)(n);
  };
  return function (n) {
    return n < 2 ? 1 :
           n * g(n - 1);
  };
});

// step 4
var fact4 = wrap(function (g) {
  return function (n) {
    return n < 2 ? 1 :
           n * g(n - 1);
  };
});

// step 5
var fact5 = Y(function (g) {
  return function (n) {
    return n < 2 ? 1 :
           n * g(n - 1);
  };
});

/***** ES6 short version *****/
const Y = (h) => (f => f(f))(f => h((...n) => f(f)(...n)));

// sample
const fac = Y(g => n => n < 2 ? 1 : n * g(n - 1));
const fib = Y(g => n => n <= 2 ? 1 : g(n - 1) + g(n - 2));

console.log([0,  1,  2,  3,  4,  5,  6,  7,  8,  9].map(fac));
console.log([0,  1,  2,  3,  4,  5,  6,  7,  8,  9].map(fib));