Y-combinator (strict version, Z-combinator) with automatic memoization

y_combinator_memoization.js

// Without memoization

const U = f => f(f);
const Z_ = t => (f => f(n => t(t)(f)(n)));
const Z = U(Z_);

// With memoization

const U_mem = f => f(f, {});

/*

const Z_mem_ = (t, cache) => (f => (n =>
  cache[n] ? (console.log("reading f(" + n + ") from cache"), cache[n])
           : (console.log("storing f(" + n + ") to cache"),
              cache[n] = f(n => t(t, cache)(f)(n))(n))));

*/

const Z_mem_ = (t, cache) => (f => (n =>
  cache[n] ? cache[n]
           : cache[n] = f(n => t(t, cache)(f)(n))(n)));

const Z_mem = U_mem(Z_mem_);

// Examples

const fact_   = f => (n => n == 0 ? 1 : n * f(n-1));
const fact    = Z_mem(fact_);

const fib_    = f => (n => n < 3 ? 1 : f(n-1) + f(n-2));
const fib     = Z(fib_);
const fib_mem = Z_mem(fib_);

/*

Here fib(40) takes some amount of time,
and fib_mem(40) works in a blink of an eye:

const tick = () => _moment = Date.now();
const tack = () => _moment = Date.now() - _moment;

tick(); fib(40); tack(); // => 16738
tick(); fib_mem(40); tack(); // => 0

*/