Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Deriving the Y Combinator in JavaScript (enlight.nyc)
49 points by shamdasani on July 5, 2018 | hide | past | favorite | 19 comments


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!


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.


Best explanation i've encountered thanks


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.


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


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


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.


Space complexity will depend on the computational model you choose.


Jim Weirich's 2012 Ruby Conf talk is also a great introduction to the Y Combinator and Lambda Calculus.

https://www.youtube.com/watch?v=FITJMJjASUs


This is an article, not a Show HN. Please read the rules: https://news.ycombinator.com/showhn.html.


Of course, if your language doesn't support recursion it probably doesn't have first-class functions either. It's pretty trivial to implement recursion if you can pass a function pointer around.


I mean, recursion is just a way of saving state on the program's call stack implicitly instead of explicitly in a stack data structure.

fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.

C can do recursion. It can't do first class functions, though it can pass function pointers. It just can't create new functions dynamically based on non local variables, at least not without shenanigans.


Recursion is not defined in terms of the execution of the program (such as storing data on the call stack). For example you can have stack less languages with recursion.


> fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.

That's one possible implementation of recursion on commodity hardware. Recursion itself is a mathematical method for defining a function which may not even be computable, or may be computable using other primitives.


Functions are syntactic sugar on calls and calls are syntactic sugar on jumps so those dynamic shenanigans would be messing with calling conventions? That might not be too ridiculous.


Maybe a stupid question ...

Isn't passing a function to itself kind of like recursion?


no, it's more like passing a continuation in this case (which is the function itself). but the function is not defined in terms of itself.


I don't get it. I do not want to define recursion, but for me as a programmer stackoverflow is a recursion, what is happening if I call y(factorialFactory)(10000).





Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: