Skip to content

Instantly share code, notes, and snippets.

@dyoder

dyoder/y-combinator.coffee

Created October 3, 2012 05:04
Show Gist options
  • Save dyoder/3825117 to your computer and use it in GitHub Desktop.
Save dyoder/3825117 to your computer and use it in GitHub Desktop.
Download ZIP
CoffeeScript is good at lambda calculus
Raw
y-combinator.coffee
# λf.(λg.f (g g)) (λg.f (g g))
Y = (f) -> ((g) -> f((x) -> g(g)(x)))((g) -> f((x) -> g(g)(x)))
# ß-reduction of Y: λf.(λg.g g) (λg.f (g g))
X = (f) -> ((g) -> g((x) -> g(x)))((g) -> f((x) -> g(g)(x)))
# applied to factorial ... this returns 720
X((f) -> (x) -> if x is 1 then 1 else x * f(x - 1))(6)
@dyoder
Copy link
Author

dyoder commented Oct 3, 2012

As an aside, I'd love to better understand the semantics of:

λg.f h

That is, why does it mean this:

(g) -> f((x) -> h(x))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment