Y-combinator derivation

yc-derivation.js

/**
 * This pretty much works.
 * The rest is simplifying and prettifying
 * while also extracting the Y-combinator function
 * as a generic utility.
 */
const factorial = (f => n => {

  if (n < 2) 1;
  return n * f(f)(n-1);

})(f => n => {

  if (n < 2) return 1;
  return n * f(f)(n-1);

})

/**
 * Separate out `recur` as a helper function that
 * calls itself with itself so we don't have to rewrite
 * the recursing logic twice.
 */

const recur = f => f(f);

const factorial2 = recur(f => n => {
  if (n < 2) return 1;
  return n * f(f)(n-1)
})


/**
 * The `f(f)(n-1)` part is kinda ugly so we create
 * the `g` function here to abtract that out.
 */

const factorial3 = recur((f) => {

  const g = (n) => f(f)(n);
  return (n) => {
    if (n < 2) return 1;
    return n * g(n - 1);
  }

})

/**
 * Extract both the `wrap` and the `g` function
 * into a `wrap` function.
 */

const wrap = (h) => {
  return recur(f => {
    const g = (n) => f(f)(n);
    return h(g);
  })
}

const factorial4 = wrap(g => n => {
  if (n < 2) return 1;
  return n * g(n - 1);
})

/**
 * Don't bother naming the `g` function.
 * Just inline define it and call it immediately.
 */

const wrap2 = (h) => {
  return recur(f => h(n => f(f)(n)));
}

const factorial5 = wrap2(g => n => {
  if (n < 2) return 1;
  return n * g(n - 1);
})

/**
 * Do the same thing for `recur`, just inline it.
 * This final version of `wrap` is the Y-combinator.
 */

const Y = (h) => {
  return (f => f(f))(f => h(n => f(f)(n)))
}

const almostFactorial = (g) => {
  return (n) => {
    if (n < 2) return 1;
    return n * g(n - 1);
  }
}
const factorial6 = Y(almostFactorial)

/**
 * Additional
 */

//compact Y-combinator
const Ycompact = (h) => (f => f(f))(f => h(n => f(f)(n)));
const factorial7 = Ycompact(almostFactorial);
//recur abstracted our more readable?
const Yother = (h) => recur(f => h(n => f(f)(n)));

/**
 * Testing
 */

console.log(factorial(4));
console.log(factorial2(4));
console.log(factorial3(4));
console.log(factorial4(4));
console.log(factorial5(4));
console.log(factorial6(4));
console.log(factorial7(4));