Y-Combinator Case Study

Question

I have read a bit about functional programming lately and am trying to get Y-Combinator. I understand that you can use Y-Combinator to efficiently implement recursion in a language that does not support recursion directly. However, every language I’m most likely to use already supports recursion, so I'm not sure how useful it would be to use Y-Combinator for this.

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

Answer 1

I'm going to disagree with the other answers: The fixed-point (Y) combinator has practical applications , but it takes a very creative mind to find them. Like Bruce McAdam. Here's an abstraction from his article What Collapses About It :

Y combinator for calculating fixed points can be expressed in standard ML. It is often used as an example of the power of higher-order functions, but is usually not considered a useful programming construct. Here we look at how a programming method based on Y combinator and wrappers can give programmers a level of control over the internal workings of functions that cannot be used without rewriting and recompiling the code. As an experiment, the I / O algorithm W is implemented using this method, so that error messages are generated with minimal interference to the algorithm. The code for this sample program illustrates the true usefulness of concepts and the ease with which they can be applied. A number of other implementation methods and possible applications are also discussed, including the use of higher-order functions to simulate the use of exceptions and continuations.

This is a great article; anyone interested in functional programming is likely to read it.

Answer 2

You can check out this great post when implementing Y Combinator in C #: Recursive lambda expressions , this can help you understand the idea better.

You can check out some interesting Wikipedia articles: Fixed-Point Combinator and Fixed-Point Theorems

According to Nathan, many functional methods are related to Y Combinator and are useful, so hold on! Y is really useful because it allows you to better understand your code, but I don't think it is especially useful for describing how this helps.

Answer 3

You can imagine a combinator as a virtual machine that runs your function, which you describe using 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 not a single programming language that I know allows. This would probably be too cumbersome most of the time and / or too difficult to learn.

Answer 4

Others may correct me if I am mistaken, but I am sure that Y combinator is strictly academic. Think about it: to implement this language, your language must support higher-order functions, but not recursion. There is only one language that I know so: lambda calculus.

So, until our machines move from Turing machines to lambda-based launches, Y combinator will be strictly academic.

Note. Other functional methods related to Y combinator are useful, so hold on to them. Understanding Y combinator will help you understand continuation, lazy appreciation, etc.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun abc _ -> Sprite(a,c)) let sprites = let rec yfx = f (yf) x // The Y Combinator //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work. let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x)) many1Indents sprite sprites_up 

Here is an example from the compiler for a small game library that I am making in F #. More specifically, in the above case, I need sprites_up to call itself recursively differently, the indentation parser will not work correctly.

Without Y Combinator, I could not correctly process the parser and resort to writing something like this:

 let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

It would not be a great solution, Y Combinator really saved me there. This, of course, is not the first thing that came to mind though.