Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Y Combinator

mvanier.livejournal.com

Post reply on HN
Print view View original

1–10 of 39 posts

Re: The Y Combinator

#4

Post by eru »

tromp wrote: post #3

Curiously, the graphical lambda calculus notation for the Y combinator slightly resembles a Y, especially when bent a little as shown at the top of https://tromp.github.io/cl/diagrams.html

I always assumed that's where it got the same from?

Re: The Y Combinator

#5

Post by amelius »

tromp wrote: post #3

Curiously, the graphical lambda calculus notation for the Y combinator slightly resembles a Y, especially when bent a little as shown at the top of https://tromp.github.io/cl/diagrams.html

They should draw these diagrams upside-down.

Then they resemble a λ.

Re: The Y Combinator

#6

Post by tromp »

eru wrote: post #4
tromp wrote: post #3

Curiously, the graphical lambda calculus notation for the Y combinator slightly resembles a Y, especially when bent a little as shown at the top of https://tromp.github.io/cl/diagrams.html

I always assumed that's where it got the same from?

The name Y combinator is many decades old, while this graphical notation is not even one decade old. But you do raise an interesting question:

How did the fixed point combinator come to be known as the Y combinator?

Re: The Y Combinator

#8

Post by Joker_vD »

I still think it's a device of rather dubious value, the most actual use of it I've seen is from being able to do it at the type-level (in one of Kiselyov's articles), because honestly, if you are allowed to name things at all, getting the function to refer to itself is pretty straightforward:

    factorial' self n =
        if n == 0
        then 1
        else n * self self (n - 1)

    factorial n = factorial' factorial' n
That's it. Unless your evaluation strategy is literally implemented as term substitution/rewriting, it's about as efficient as having actual letrec primitive.

This technique is straightforwardly extended to the case of mutual recursion:

    even' even odd n =
        if n == 0
        then True
        else odd even odd (n - 1)

   odd' even odd n =
        if n == 0
        then False
        else even even odd (n - 1)

   even n = even' even' odd' n
   odd n  = odd'  even' odd' n

Re: The Y Combinator

#9

Post by amelius »

tromp wrote: post #6
eru wrote: post #4

Earlier quoted context omitted.

I always assumed that's where it got the same from?

The name Y combinator is many decades old, while this graphical notation is not even one decade old. But you do raise an interesting question: How did the fixed point combinator come to be known as the Y combinator?

Probably just drawing letters from the alphabet.

It's like the question: why do we use "x" to denote the unknown value in mathematics, most of the time?

Re: The Y Combinator

#10

Post by bidirectional »

amelius wrote: post #9
tromp wrote: post #6

Earlier quoted context omitted.

The name Y combinator is many decades old, while this graphical notation is not even one decade old. But you do raise an interesting question: How did the fixed point combinator come to be known as the Y combinator?

Probably just drawing letters from the alphabet. It's like the question: why do we use "x" to denote the unknown value in mathematics, most of the time?

The drawing random letters is true for the lambda in lambda-calculus, but not true for (at least some) combinators. e.g. the K combinator derives from Konstanzfunktion, and I from Identitätsfunktion[1]. So I do think it is an interesting question why Y, and we can't just assume it's arbitrary.

[1] https://www.johndcook.com/blog/2014/02/06/schonfinkel-combin...

Post reply on HN