Deriving the Y Combinator in JavaScript • Hacker News Board

Re: Deriving the Y Combinator in JavaScript

#21

Post by dustingetz » Fri, Jul 06, 2018, 11:41 AM UTC

rs86 wrote: post #11

18nleung wrote: post #3

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 explorat…

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 "functio…

Best explanation i've encountered thanks

Re: Deriving the Y Combinator in JavaScript

#22

Post by rs86 » Fri, Jul 06, 2018, 9:25 PM UTC

lsiebert wrote: post #13

Retra wrote: post #4

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…

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.

Re: Deriving the Y Combinator in JavaScript

#23

Post by azatom » Sat, Jul 07, 2018, 5:22 PM UTC

rs86 wrote: post #9

mchahn wrote: post #7

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).