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

11–20 of 39 posts

Re: The Y Combinator

#11

Post by amelius »

bidirectional wrote: post #10
amelius wrote: post #9

Earlier quoted context omitted.

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

Then perhaps this reply comes closest to the truth:

> Y because the letter Y has one stem which splits in two, just like what the function does. That’s probably the reason, or at least that’s how I look at it.

Re: The Y Combinator

#12

Post by Koshkin »

Joker_vD wrote: post #8

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…

As the article points out, the value of the Y combinator is largely theoretical/aesthetical, in both of which aspects your examples suffer greatly: they are ad hoc, lack abstraction/code reuse (which is why, perhaps, you needed more examples), and they look ugly (at least to my untrained eye). The point of the Y combinator is that it is a beautiful, mathematically precise, abstract, purely-functional way of expressing recursion.

Re: The Y Combinator

#14

Post by arethuza »

Joker_vD wrote: post #8

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…

"if you are allowed to name things at all, getting the function to refer to itself is pretty straightforward"

The neat thing about the Y-combinator is that it allows recursion to be defined in systems, such as the lambda calculus, which don't have naming and therefore a function can't refer to itself by name.

Re: The Y Combinator

#15

Post by Joker_vD »

Koshkin wrote: post #12
Joker_vD wrote: post #8

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…

As the article points out, the value of the Y combinator is largely theoretical/aesthetical, in both of which aspects your examples suffer greatly: they are ad hoc, lack abstraction/code reuse (which is why, perhaps, you needed more examples), and they look ugly (at least to my untrained eye). The point of the Y combinator is that it is a beautiful, mathematically precise, abstract, purely-functional way of expressin…

"Ad hoc, lack abstraction/code reuse"? How does this

    fix f = f f

    almost_factorial f n =
        if n == 0
        then 1
        else n * f f (n - 1)

    factorial = fix almost_factorial
lack code reuse compared to

    fix f = (\x. x x) (\x. f (\y. x x y))

    almost_factorial f n =
        if n == 0
        then 1
        else n * f (n - 1)

    factorial = fix almost_factorial
? As for ugliness, well, it is indeed in the eye of the beholder: I personally think the fixpoint combinators that enable mutual recursion are pretty ugly, even more so than "(\x. x x) (\x. f (\y. x x y))".

The only real problem is that in my approach the recursive calls look like "f closed_over_functions... new_args..." instead of "f new_args..." but that's what the compilers are for: this transformation is called "closure conversion" and is pretty straightforward. Sure, if you have to encode those things manually, then perhaps using Y is clearer and may even be the only option if you can't mess with the original definitions.

Re: The Y Combinator

#16

Post by Joker_vD »

ProfHewitt wrote: post #13

Y Combinator does not work for strongly-typed programs because the definition is not strongly typed. Instead recursion must be added as an additional primitive to the lambda calculus. See https://papers.ssrn.com/abstract=3418003

It's perfectly well typed in System F as "forall a. (a -> a) -> a".

Re: The Y Combinator

#17

Post by Joker_vD »

arethuza wrote: post #14
Joker_vD wrote: post #8

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…

"if you are allowed to name things at all, getting the function to refer to itself is pretty straightforward" The neat thing about the Y-combinator is that it allows recursion to be defined in systems, such as the lambda calculus, which don't have naming and therefore a function can't refer to itself by name.

Well, lambda calculus does have names, but yes, I agree, it's a very neat trick in environments where naming is heavily restricted, it gives you "anonymous recursion", so to speak. Church-encoding is another similarly neat trick, for environments with substitutions/applications but without built-in natural numbers.

It's just that it seems there are not that many such systems used in practice except for "advanced type systems".

Re: The Y Combinator

#18

Post by ProfHewitt »

Joker_vD wrote: post #16
ProfHewitt wrote: post #13

Y Combinator does not work for strongly-typed programs because the definition is not strongly typed. Instead recursion must be added as an additional primitive to the lambda calculus. See https://papers.ssrn.com/abstract=3418003

It's perfectly well typed in System F as "forall a. (a -> a) -> a".

Could you write this in Java?

Re: The Y Combinator

#19

Post by bidirectional »

Joker_vD wrote: post #16
ProfHewitt wrote: post #13

Y Combinator does not work for strongly-typed programs because the definition is not strongly typed. Instead recursion must be added as an additional primitive to the lambda calculus. See https://papers.ssrn.com/abstract=3418003

It's perfectly well typed in System F as "forall a. (a -> a) -> a".

Can you type that in System F? It doesn't seem logically valid, a -> a is trivially true, but apparently implies any a?
Post reply on HN