Y-Combinator Practical Example

Question

I've been reading a bit lately about functional programming and I am trying to grok the Y-Combinator. I understand that you can use the Y-Combinator to effectively implement recursion in a language that doesn't support recursion directly. However, every language that I'm likely to use already supports recursion so I'm not sure how useful it would be to use the Y-Combinator for that.

Is there a better practical example of Y-Combinator usage that I'm missing? Has anyone actually used one in real production code? Or is using the Y-Combinator really just a mind-bending academic exercise (albeit a pretty cool one).

Answer 1

Others can correct me if I'm wrong, but I'm pretty sure the Y combinator is strictly academic. Think about it: to implement it your language needs to support higher-order functions but not recursion. There's only one language I know like that: lambda calculus.

So until our machines switch from Turing machines to running on lambda calculus, the Y combinator will be strictly academic.

Note: other functional techniques related to the Y combinator are useful, so keep at it. Understanding the Y combinator will help you understand continuations, lazy evaluation, etc.

Answer 2

You can think of the combinator as the virtual machine which runs your function, which you describe by a non-recursive functional (= higher-order function).

Sometimes it would be nice to have this combinator under program control, to do similar things as aspect oriented programming (memoizing, tracing, ...), but no programming language I know of allows it. Probably it would be too cumbersome most of the time and/or too hard to learn.

Answer 3

You could check out this nifty post on implementing the Y Combinator in C#: Recursive Lambda Expressions, it might help you understand the idea better.

You may want to check out some nice articles on wikipedia: Fixed point combinator and Fixed point theorems

As Nathan says, many fuctional techniques are related to the Y combinator and are useful, so keep at it! Y really is useful because it lets you understand your code better, but I don't think that's a particularly helpful to describe how it helps.

Answer 4

I'm going to disagree with other answers: The fixed-point (Y) combinator does have practical applications, but it takes a very imaginative mind to find them. Like Bruce McAdam. Here's the abstract from his paper That About Wraps it Up:

The Y combinator for computing fixed points can be expressed in Standard ML. It is frequently used as an example of the power of higher-order functions, but is not generally regarded as a useful programming construction. Here, we look at how a programming technique based on the Y combinator and wrappers can give programmers a level of control over the internal workings of functions not otherwise possible without rewriting and recompiling code. As an experiment, the type-inference algorithm W is implemented using this technique, so that error messages are produced with minimum interference to the algorithm. The code for this example program illustrates the genuine usefulness of the concepts and the ease with which they can be applied. A number of other implementation techniques and possible applications are also discussed, including the use of higher-order functions to simulate the use of exceptions and continuations.

It's a great paper; anyone interested in functional programming will probably enjoy reading it.