[18nleung]

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!

[rs86]

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]

Best explanation i've encountered thanks

[nv-vn]

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.

[aappleby]

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

[anothergoogler]

What similarities are you talking about? I'm not seeing it.

[jacobwilliamroy]

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]

Space complexity will depend on the computational model you choose.