Memoized Y-Combinator in ES6

y-memo.js

let Ym = (f, s = JSON.stringify) => (g => g(g))(x => f((...v) => (k => k in x ? x[k] : x[k] = x(x)(...v))(s(v))))

let fib = Ym(f => n => n <= 1 ? n : f(n - 1) + f(n - 2))

console.log('fib(1000)', fib(1000)) // => 4.346655768693743e+208

I did a quick search on that earlier and I didn't find anything then. Apparently there's a known issue with JSON.stringify() in that it doesn't guarantee anything about the order of object properties, so { a: 1, b: 2 } and { b: 2, a: 1 } stringify differently. Not a big deal for memoization, just inefficient when it happens. Also note that JSON doesn't support cycles, and I suspect anything that does would be a bit slower. If your function only takes one argument and it's guaranteed to be a number or string you can simplify it to x => x or x => "" + x, which would lead to something like:

let Ym = (f, makeKey = JSON.stringify, cache = {}) => (g => g(g))(x => f((...v) => {
  let key = makeKey(v);
  return key in cache ? cache[key] : (cache[key] = (x(x))(...v));
}));

let fib  = Ym(f => n => n <= 1 ? n : f(n - 1) + f(n - 2), x => x);
let fact = Ym(f => n => n <= 1 ? 1 : n * f(n - 1), x => x);

Bonus: "Look ma, no let!"

let Ym1a = (f, makeKey = JSON.stringify, cache = {}) => (g => g(g))(x => f((...v) =>
           (key => key in cache ? cache[key] : (cache[key] = (x(x))(...v)))(makeKey(v))));

let Ym1b = (f, makeKey = JSON.stringify, cache = {}) => (g => g(g))(x => f((...v) =>
           ((key = makeKey(v)) => key in cache ? cache[key] : (cache[key] = (x(x))(...v)))()));

Yeah, that's what I had found as well. I like putting JSON.stringify in as a default param, so we can use the abbreviated arrow function syntax. Thanks for your feedback!

Updated the gist. I also removed the cache param. The cache will be stored in the anonymous function x instead.

Very clever, using the recursion function as the cache.

I'm using key in cache (now k in x) so you can store false-y values in your cache without having to calculate them over and over.

It's also possible to get rid of some extraneous parentheses, leading to:

let Ym = (f, s = JSON.stringify) => (g => g(g))(x => f((...v) => (k => k in x ? x[k] : x[k] = x(x)(...v))(s(v))));

Oh, I see. I wasn't sure why you used in instead of just trying to read the cached value. Good call, I'll update the code. By the way, post your Twitter handle, so I can credit you for your contribution :)