←back to thread

Baking the Y Combinator from Scratch

(the-nerve-blog.ghost.io)
123 points mprast | 1 comments | 09 Apr 25 19:04 UTC | HN request time: 0.202s | source
Show context
mkagenius ◴[09 Apr 25 20:59 UTC] No.43637919[source]▶
Is there a technique to remember this? I will understand it today and forget after a few weeks.
replies(4): >>43638317 #>>43638319 #>>43639364 #>>43639727 #
bloppe ◴[09 Apr 25 21:39 UTC] No.43638319[source]▶
It's easier to remember if you use a more common notation:

    (Y(f))(x) = f(f(f(...(x)...)))
Or express it in python, which is still a bit weird but probably still more readable than pure LC to pretty much everybody:

    def Y(f):
        return lambda x: f(Y(f)(x))
replies(2): >>43638405 #>>43639741 #
tromp ◴[09 Apr 25 21:50 UTC] No.43638405[source]▶
> (Y(f))(x) = f(f(f(...(x)...)))

I think that should be (Y(f))(x) = f(f(f(...)))(x)

replies(1): >>43646874 #
1. bloppe ◴[10 Apr 25 18:38 UTC] No.43646874[source]▶
Think of f as a function that takes a value and returns a value. Y takes a function and returns a function. Y(f) returns a new function that takes a value and applies f to it, recursively forever, ultimately converging on a value (or infinity).

In your example, f(...) would have to return a function that is then applied to x.

I realize there are no non-function values in LC.