|
|
|
|
|
|
by rs86
2909 days ago
|
|
|
Nice article but you can't write the Y-combinator in Haskell (or in simply typed lambda calculus). You can write it in the untyped lambda calculus. "y = \f -> (\x -> f (x x)) (\x -> f (x x))" will fail to type check in haskell. Also it would be cool to show that what the Y-combinator does is find a fixed point for a function. When you define fact as "function fact(f, n) {...}" you are actually defining it as "function fact(f) { n => ... }" and the Y-combinator finds a fixed point for fact. A fixed point is x such that f(x) = x. so fact(fact) = fact. In lambda calculus _every_ function has a fixed point; In a simply typed lambda calculus it does not. This gives a way to define recursion as fixed points and not as circular references. |
|
|