Skip to content

Instantly share code, notes, and snippets.

@kevbuchanan
Last active February 12, 2016 21:53
Show Gist options
  • Save kevbuchanan/f845cc7f3f89fa2d658b to your computer and use it in GitHub Desktop.
Save kevbuchanan/f845cc7f3f89fa2d658b to your computer and use it in GitHub Desktop.
Y Combinators
(def y
(fn [improver]
((fn [gen] (improver (fn [v] ((gen gen) v))))
(fn [gen] (improver (fn [v] ((gen gen) v)))))))
(def fact-improver
(fn [partial]
(fn [n]
(if (= n 0)
1
(* n (partial (dec n)))))))
(def fact (y fact-improver))
(println (fact 5))
console.log(function() {
var y = function(improver) { // 1. improver is factImprover
return function(gen) { // 2. define fn that takes a gen
return improver(function(v) { // 4. improver is returned with recurse bound to this fn, takes an n: line 26
return gen(gen)(v) // 5. Recurse. v is bound to 4. gen' is called with gen'
// 7. bound improver from #6 is called with 4
})
}(function(gen) { // 3. this fn is gen' that takes a gen. bind gen from #2 to gen'
return improver(function(v) { // 6. this fn is g'', gen is bound to gen'. gen' returns improver with recurse bound to g'', takes an n
return gen(gen)(v) // 8. Recurse. v is bound to 3, gen' is called with gen', go to 6, then 9
// 9. bound improver from #6 is called with 3, go to 8, go to 9, repeat: now in fixpoint
})
})
}
var factImprover = function(recurse) {
return function(n) {
if (n === 0) {
return 1
} else {
return n * recurse(n - 1)
}
}
}
var fact = y(factImprover)
return fact(5)
}());
puts ->{
y = ->(improver) {
->(gen) {
improver[->(v) {
gen[gen][v]
}]
}[->(gen) {
improver[->(v) {
gen[gen][v]
}]
}]
}
fact_improver = ->(recurse) {
->(n) {
if n == 0
1
else
n * recurse[n - 1]
end
}
}
fact = y[fact_improver]
fact[5]
}[]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment