←back to thread

Baking the Y Combinator from Scratch

(the-nerve-blog.ghost.io)
125 points mprast | 2 comments | | HN request time: 0.419s | source
Show context
mkagenius ◴[] 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 ◴[] 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 #
1. chabska ◴[] No.43639741[source]

That misses the whole point, in that you cannot refer to Y inside of Y in an environment that doesn't have recursion.

replies(1): >>43646883 #
2. bloppe ◴[] No.43646883[source]

Fair enuf