Skip to content

Instantly share code, notes, and snippets.

@serapath
Created May 21, 2016 16:55
Show Gist options
  • Save serapath/1e00ef73f95be05bfeb6f5f46722338f to your computer and use it in GitHub Desktop.
Save serapath/1e00ef73f95be05bfeb6f5f46722338f to your computer and use it in GitHub Desktop.
y combinator
function Y (F) {
function fn (x) {
return F(function (y) { return x(x)(y) })
}
return F(function (y) { return fn(fn)(y) })
}
function FactGen (fact) {
return function (n) {
return (n == 0) ? 1 : (n*fact(n-1))
}
}
(Y(FactGen))(6)
// stuff
function Ymem(F, cache) {
if (!cache) cache = {}
return function (arg) {
if (cache[arg]) return cache[arg]
var answer = (F(function(n) {
return (Ymem(F,cache))(n)
}))(arg) // compute answer
return cache[arg] = answer
}
}
var fib = Ymem(function (g) {
return function (n) {
if (n == 0) return 0
if (n == 1) return 1
return g(n-1) + g(n-2)
}
})
fib(100)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment