Last active
June 5, 2017 01:19
-
-
Save qntm/01e0dfcad7eb58bed1e7c6a863995abb to your computer and use it in GitHub Desktop.
Variadic fixed point combinators? They're more likely than you think
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
/** | |
Analogous to Array.prototype.map but for objects. If you | |
REALLY don't want to modify Object.prototype you can | |
modify this into a regular function `objectMap(obj, f)` I GUESS | |
but it doesn't affect the basic idea of what happens below | |
*/ | |
Object.prototype.map = function(f) { | |
const mapped = {}; | |
Object.keys(this).forEach(key => { | |
mapped[key] = f(this[key], key, this); | |
}) | |
return mapped; | |
}; | |
/** | |
Variadic equivalent to the Y combinator. Resolves a collection | |
of functions which refer to one another, without the need for | |
mutability or any of whatever. | |
Compare with the regular Y combinator, which is: | |
const y = unresolved => | |
(f => f(f))(f => unresolved(x => f(f)(x))); | |
*/ | |
const variadicY = unresolveds => | |
(fs => fs.map(f => f(fs)))(unresolveds.map(unresolved => fs => unresolved(fs.map(f => x => f(fs)(x))))); | |
/** | |
Some functions which attempt to refer to one another by name, but | |
aren't quite there yet. Notice that there is no actual recursion | |
here and everything is const and so on. The fixed point of | |
(funcs => unresolveds.map(funcs)) is our desired collection of | |
named functions. I think. It's late. | |
*/ | |
const unresolveds = { | |
isEven: funcs => | |
x => x === 0 ? true : funcs.isOdd(x - 1), | |
isOdd: funcs => | |
x => x === 0 ? false : funcs.isEven(x - 1) | |
}; | |
const resolveds = variadicY(unresolveds); | |
// That's better! | |
console.log(resolveds.isEven(6)); | |
// true | |
// If this is all wrong I'll scrap and recreate it tomorrow |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment