4 ms·

Hi! Author here, and glad to see my writeup on HN. I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator

Hi! Author here, and glad to see my writeup on HN. I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator. The Y writeups currently online that I read were wonderful for a seasoned Haskell programmer, but I thought it would be great to explore the concept from a more FP beginner-friendly lens, and through a more familiar language - JavaScript. I hope this exploration is helpful, and feel free to leave any questions or comments you may have below!

jacobwilliamroy 8y ago
Is it impossible to write a y-combinator with space complexity O(1)? I'm in the very early stages of a comp/sci education and have not yet learned how to prove that something is impossible.
- rs86 8y ago
  Space complexity will depend on the computational model you choose.
nv-vn 8y ago
Hey dude! Not sure if you remember me but I talked to you a while ago on a2c. Anyways, this is a cool article and I thought you did a good job of explaining some of the technical details. Btw, since you have a JS background I thought I'd recommend ReasonML to you. I just started using it, but I think it's a really nice mix of functional programming with JS type stuff, plus it's designed by the guy who made React.
rs86 8y 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.
- dustingetz 8y ago
  Best explanation i've encountered thanks
aappleby 8y ago
Some uncanny similarities to my version - https://medium.com/@tanjent/refactoring-out-a-y-combinator-99427d483186 https://medium.com/@tanjent/refactoring-out-a-y-combinator-9...
- anothergoogler 8y ago
  What similarities are you talking about? I'm not seeing it.

jacobwilliamroy 8y ago

Is it impossible to write a y-combinator with space complexity O(1)? I'm in the very early stages of a comp/sci education and have not yet learned how to prove that something is impossible.

rs86 8y ago
Space complexity will depend on the computational model you choose.

nv-vn 8y ago

Hey dude! Not sure if you remember me but I talked to you a while ago on a2c. Anyways, this is a cool article and I thought you did a good job of explaining some of the technical details. Btw, since you have a JS background I thought I'd recommend ReasonML to you. I just started using it, but I think it's a really nice mix of functional programming with JS type stuff, plus it's designed by the guy who made React.

rs86 8y 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.

dustingetz 8y ago
Best explanation i've encountered thanks

aappleby 8y ago

Some uncanny similarities to my version - https://medium.com/@tanjent/refactoring-out-a-y-combinator-99427d483186 https://medium.com/@tanjent/refactoring-out-a-y-combinator-9...

anothergoogler 8y ago
What similarities are you talking about? I'm not seeing it.