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

Can't we replace the conversion of the arguments array-like-object with the ES6 rest operator?

let Ym = (f, x = {}) => (...args) => {
  var y = JSON.stringify(args)
  return x[y] || (x[y] = f(z => Ym(f, x)(z)).apply(this, args))
}

You can also replace the apply with ...args, and I think you'll need to use ...z if your intent is to support multi-param functions:

let Ym = (f, memo = {}) => (...args) => {
  let key = JSON.stringify(args);
  return key in x ? memo[key] : (memo[key] = f((...z) => Ym(f, x)(...z))(...args));
}

How about this so you don't need both ...z and ...args:

// Z = λf.(λg.g g) (λx.f (λv.((x x) v)))
let Y = f => (g => g(g))(x => f((...v) => (x(x))(...v)));

// Z with memoization
let Ym = (f, cache = {}) => (g => g(g))(x => f((...v) => {
  let key = JSON.stringify(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));
let fact = Ym(f => n => n <= 1 ? 1 : n * f(n - 1));

@mstaicu quite right. In my haste I forgot about rest params, thanks for reminding me!

@mozjag interesting ideas. I wonder though if we can also improve the JSON.stringify expression with something lighter? Any ideas?

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 :)