What is a y-combinator?

[btilly]

My favorite explanation remains the one I came up with at http://www.mail-archive.com/[email protected]/msg02716.h....

[Xurinos]

Let's just pretend we are binding values. There are ways to make perl look like you are doing parameter assignment.

    sub {
        my $builder = shift;
        return sub {
            my $n = shift;
            return $builder->($builder)->($n);
        };
    }->(
        sub {
            my $recurse = shift;
            return sub {
                my $n = shift;
                say "$n";  # Just a way to test
                if (0 == $n) {
                    return 1;
                }
                else {
                    return $n * $recurse->($recurse)->($n - 1);
                }
            };
       }
    )->(5);

I was confused about the "perl can't do this" part.

[dionidium]

You should definitely add that as an answer on SO. The current answers are not very useful.

[draegtun]

Aristotle also does a great explanation in this use.perl.org post: http://use.perl.org/~Aristotle/journal/30896

[speckledjim]

Has anyone on HN ever actually used one of these in code they've written?

I've never understood why y-combinator is useful or impressive. Interesting, maybe, but not really useful.

[fexl]

I use them in the Fexl language http://fexl.com .

Although the Fexl language itself has syntax for recursive definitions, it translates everything to combinators internally, so there are no "symbol tables" or "environments" at run time. Therefore it uses the Y combinator to implement those recursive definitions.

A while ago I wrote this detailed example: http://news.ycombinator.com/item?id=2719635

tl;dr here is a non-recursive definition of the append function for two lists:

  (Y \append \x\y x y \h\t cons h; append t y)

If you need more parentheses for clarity, here you go:

  (Y (\append \x\y x y \h\t cons h (append t y)))

[Homunculiheaded]

I would say that the y-combinator is interesting to the such a degree that it becomes useful. Sure you won't and shouldn't use the y-combinator in any real world applications. But first off it demonstrates the true power of the lambda calculus to represent computation, and more importantly to the practical programmer is that understanding it will provide a deep insight into the nature of computation, which is profoundly useful if you ask me.

[GregBuchholz]

"Y in Practical Programs" by Bruce McAdam:

http://www.dsi.uniroma1.it/~labella/absMcAdam.ps (or search with Google for an HTML translation).

[ianl]

It's useful for lambda functions that recursively call themselves, you don't need these in practice because you wouldn't use a lambda. You would use a named function, therefore, they are almost purely theoretical aspect of Lambda Calculus. I can't think of any programming language that is purely lambda calculus.

[kotrin]

http://www.dreamsongs.com/Files/WhyOfY.pdf

[yters]

It's all about removing dependencies, and y-combinators have the fewest dependencies for accomplishing the greatest number of functions.

[guelo]

After you wrap your head around that barely useful, rarely used technique the next question is, why did pg name his company after it?

[rjbond3rd]

He started a business, and now his business is starting other businesses. Recursive...

[de90]

He actually mentions why in a Mixergy interview. I believe it's one that's still free to view, but to paraphrase:

People who see it and recognize it are the type of people he wants to catch attention from(hackers). Suits, would see it and ignore it.

[sampsonjs]

It's an opportunity for HN'ers to hold forth on programming.

[SimHacker]

FORTH ?KNOW IF HONK ELSE FORTH LEARN THEN

[karmafeeder]

Fixed.