The Y Combinator

[mvanier]

OK, I'm going to try to explain what the Y combinator is, why it's interesting, and how it works. I'll have to include a bit of background information to try to make this post self-contained.

The Y combinator has become a bit of a cool buzzphrase since Paul Graham named his startup incubator company Y Combinator. Why did he choose that name? I

Comments

Nice explication

[gcurious]

It's always amazing how a thing as simple as the Y-combinator can be as hard to explain. Now explain why typing it is so hard :-)

[darius]

Y can be handy in practice because once your function is in a form like almost-factorial's -- "open recursion" -- you can apply different combinators to it, to add caching or tracing, etc. There was a paper mentioned on LtU about this. Ah, here's another one, not the one I was thinking of, but it does use this idea -- I see you've already seen it: http://lambda-the-ultimate.org/classic/message8479.html

Y in Practical Programs

[jamesiry]

This might be what you were looking for, Darius: http://citeseer.ist.psu.edu/mcadams01practical.html