-
-
Save therealklanni/ae84f6a94176f02b356f to your computer and use it in GitHub Desktop.
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 |
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));
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 :)
Can't we replace the conversion of the arguments array-like-object with the ES6 rest operator?