Skip to content

Instantly share code, notes, and snippets.

@YBogomolov
Last active January 23, 2018 21:46
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save YBogomolov/be0dcda0ebc7fb064e965ddb143aad0e to your computer and use it in GitHub Desktop.
Save YBogomolov/be0dcda0ebc7fb064e965ddb143aad0e to your computer and use it in GitHub Desktop.
Y-combinator in JavaScript (ES6) with memoization
// `fix` is an Y-combinator implementation (recursive calls in lambda calculus):
// Y = \f -> (\x -> f (x x))(\x -> f (x x))
// fix :: (a -> a) -> a
const fix = f => (x => f(y => (x(x))(y)))(x => f(y => (x(x))(y)));
// Generator function. Inner signature should correspond to actual function interface.
// mapgen :: ((a -> b) -> [a] -> [b]) -> (a -> b) -> [a] -> [b]
const mapgen = map => f => list => list.length === 0 ? [] : [f(list[0]), ...map(f)(list.slice(1))];
// Memoization of a function of N arguments:
// memoize :: ([a] -> b) -> [a] -> b
const memoize = fn => (...x) => {
const hash = x.reduce((acc, el) => `${acc}|${el === Object(el) ? JSON.stringify(el) : el.toString()}`, '');
fn.memoize = fn.memoize || {};
return (hash in fn.memoize) ? fn.memoize[hash] : (fn.memoize[hash] = fn.call(null, ...x));
};
// map :: (a -> b) -> [a] -> [b]
const map = fix(memoize(mapgen));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment