y combinator

ycomb.js

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)