Last active
October 2, 2016 22:37
-
-
Save therealklanni/ae84f6a94176f02b356f to your computer and use it in GitHub Desktop.
Memoized Y-Combinator in ES6
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
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 :)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Updated the gist. I also removed the
cache
param. The cache will be stored in the anonymous functionx
instead.