What is a Y-combinator?
Solution 1
If you're ready for a long read, Mike Vanier has a great explanation. Long story short, it allows you to implement recursion in a language that doesn't necessarily support it natively.
Solution 2
A Y-combinator is a "functional" (a function that operates on other functions) that enables recursion, when you can't refer to the function from within itself. In computer-science theory, it generalizes recursion, abstracting its implementation, and thereby separating it from the actual work of the function in question. The benefit of not needing a compile-time name for the recursive function is sort of a bonus. =)
This is applicable in languages that support lambda functions. The expression-based nature of lambdas usually means that they cannot refer to themselves by name. And working around this by way of declaring the variable, refering to it, then assigning the lambda to it, to complete the self-reference loop, is brittle. The lambda variable can be copied, and the original variable re-assigned, which breaks the self-reference.
Y-combinators are cumbersome to implement, and often to use, in static-typed languages (which procedural languages often are), because usually typing restrictions require the number of arguments for the function in question to be known at compile time. This means that a y-combinator must be written for any argument count that one needs to use.
Below is an example of how the usage and working of a Y-Combinator, in C#.
Using a Y-combinator involves an "unusual" way of constructing a recursive function. First you must write your function as a piece of code that calls a pre-existing function, rather than itself:
// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);
Then you turn that into a function that takes a function to call, and returns a function that does so. This is called a functional, because it takes one function, and performs an operation with it that results in another function.
// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
(recurs) =>
(x) =>
x == 0 ? 1 : x * recurs(x - 1);
Now you have a function that takes a function, and returns another function that sort of looks like a factorial, but instead of calling itself, it calls the argument passed into the outer function. How do you make this the factorial? Pass the inner function to itself. The Y-Combinator does that, by being a function with a permanent name, which can introduce the recursion.
// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
return
t => // A function that...
F( // Calls the factorial creator, passing in...
Y(F) // The result of this same Y-combinator function call...
// (Here is where the recursion is introduced.)
)
(t); // And passes the argument into the work function.
}
Rather than the factorial calling itself, what happens is that the factorial calls the factorial generator (returned by the recursive call to Y-Combinator). And depending on the current value of t the function returned from the generator will either call the generator again, with t - 1, or just return 1, terminating the recursion.
It's complicated and cryptic, but it all shakes out at run-time, and the key to its working is "deferred execution", and the breaking up of the recursion to span two functions. The inner F is passed as an argument, to be called in the next iteration, only if necessary.
Solution 3
I've lifted this from http://www.mail-archive.com/[email protected]/msg02716.html which is an explanation I wrote several years ago.
I'll use JavaScript in this example, but many other languages will work as well.
Our goal is to be able to write a recursive function of 1 variable using only functions of 1 variables and no assignments, defining things by name, etc. (Why this is our goal is another question, let's just take this as the challenge that we're given.) Seems impossible, huh? As an example, let's implement factorial.
Well step 1 is to say that we could do this easily if we cheated a little. Using functions of 2 variables and assignment we can at least avoid having to use assignment to set up the recursion.
// Here's the function that we want to recurse.
X = function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
};
// This will get X to recurse.
Y = function (builder, n) {
return builder(builder, n);
};
// Here it is in action.
Y(
X,
5
);
Now let's see if we can cheat less. Well firstly we're using assignment, but we don't need to. We can just write X and Y inline.
// No assignment this time.
function (builder, n) {
return builder(builder, n);
}(
function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
},
5
);
But we're using functions of 2 variables to get a function of 1 variable. Can we fix that? Well a smart guy by the name of Haskell Curry has a neat trick, if you have good higher order functions then you only need functions of 1 variable. The proof is that you can get from functions of 2 (or more in the general case) variables to 1 variable with a purely mechanical text transformation like this:
// Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j);
where ... remains exactly the same. (This trick is called "currying" after its inventor. The language Haskell is also named for Haskell Curry. File that under useless trivia.) Now just apply this transformation everywhere and we get our final version.
// The dreaded Y-combinator in action!
function (builder) { return function (n) {
return builder(builder)(n);
}}(
function (recurse) { return function (n) {
if (0 == n)
return 1;
else
return n * recurse(recurse)(n - 1);
}})(
5
);
Feel free to try it. alert() that return, tie it to a button, whatever. That code calculates factorials, recursively, without using assignment, declarations, or functions of 2 variables. (But trying to trace how it works is likely to make your head spin. And handing it, without the derivation, just slightly reformatted will result in code that is sure to baffle and confuse.)
You can replace the 4 lines that recursively define factorial with any other recursive function that you want.
Solution 4
I wonder if there's any use in attempting to build this from the ground up. Let's see. Here's a basic, recursive factorial function:
function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
Let's refactor and create a new function called fact
that returns an anonymous factorial-computing function instead of performing the calculation itself:
function fact() {
return function(n) {
return n == 0 ? 1 : n * fact()(n - 1);
};
}
var factorial = fact();
That's a little weird, but there's nothing wrong with it. We're just generating a new factorial function at each step.
The recursion at this stage is still fairly explicit. The fact
function needs to be aware of its own name. Let's parameterize the recursive call:
function fact(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
}
function recurser(x) {
return fact(recurser)(x);
}
var factorial = fact(recurser);
That's great, but recurser
still needs to know its own name. Let's parameterize that, too:
function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser);
Now, instead of calling recurser(recurser)
directly, let's create a wrapper function that returns its result:
function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y();
We can now get rid of the recurser
name altogether; it's just an argument to Y's inner function, which can be replaced with the function itself:
function Y() {
return (function(f) {
return f(f);
})(function(f) {
return fact(function(x) {
return f(f)(x);
});
});
}
var factorial = Y();
The only external name still referenced is fact
, but it should be clear by now that that's easily parameterized, too, creating the complete, generic, solution:
function Y(le) {
return (function(f) {
return f(f);
})(function(f) {
return le(function(x) {
return f(f)(x);
});
});
}
var factorial = Y(function(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
});
Solution 5
Most of the answers above describe what the Y-combinator is but not what it is for.
Fixed point combinators are used to show that lambda calculus is turing complete. This is a very important result in the theory of computation and provides a theoretical foundation for functional programming.
Studying fixed point combinators has also helped me really understand functional programming. I have never found any use for them in actual programming though.
Chris Ammerman
I am a software developer, passionate about the art and science of the craft. I describe myself as being a "lazy" developer, to the core. Anything that increases the expressiveness of my code (thereby allowing me to type and repeat myself less) is okay in my book. Sites: Blog - http://www.turbulentintellect.com Twitter - http://twitter.com/cammerman
Updated on May 09, 2020Comments
-
Chris Ammerman about 4 years
A Y-combinator is a computer science concept from the “functional” side of things. Most programmers don't know much at all about combinators, if they've even heard about them.
- What is a Y-combinator?
- How do combinators work?
- What are they good for?
- Are they useful in procedural languages?
-
xitrium over 13 yearsJavascript doesn't need a Y-combinator to do anonymous recursion because you can access the current function with arguments.callee (see en.wikipedia.org/wiki/…)
-
dave1010 about 13 years
arguments.callee
is not allowed in Strict Mode: developer.mozilla.org/en/JavaScript/… -
Brian Henk almost 13 yearsWhy oh why did you have to call it 'Y' and the parameter 'F'! They just gets lost in the type arguments!
-
Peaker almost 13 yearsIn Haskell, you can abstraction recursion with:
fix :: (a -> a) -> a
, and thea
can in turn be a function of as many arguments as you'd like. This means that static typing doesn't really make this cumbersome. -
GrantJ almost 13 yearsAccording to Mike Vanier's description, your definition for Y is actually not a combinator because it's recursive. Under "Eliminating (most) explicit recursion (lazy version)" he has the lazy scheme equivalent of your C# code but explains in point 2: "It is not a combinator, because the Y in the body of the definition is a free variable which is only bound once the definition is complete..." I think the cool thing about Y-combinators is that they produce recursion by evaluating the fixed-point of a function. In this way, they don't need explicit recursion.
-
Chris Ammerman almost 13 years@GrantJ You make a good point. It's been a couple years since I posted this answer. Skimming Vanier's post now I see that I've written Y, but not a Y-Combinator. I'll read his post again soon and see if I can post a correction. My gut is warning me that the strict static typing of C# may prevent it in the end, but I'll see what I can do.
-
Pops about 12 yearsA similar explanation in JavaScript: igstan.ro/posts/…
-
Wayne about 12 yearsI have never seen the word "functional" used as a noun in this way. Can you point to any other source that uses the term similarly?
-
Esailija almost 12 yearsYou can still give any function a name, and if it's function expression then that name is only known inside the function itself.
(function fact(n){ return n <= 1? 1 : n * fact(n-1); })(5)
-
Tony over 11 yearsHere is another great explanation that can complement this very great one: blogs.msdn.com/b/wesdyer/archive/2007/02/02/…
-
Will Ness almost 11 yearsvery funny. :) young(er) ones might not recognize the reference though.
-
tina Miller about 10 yearsIf I'm understanding this answer to my question correctly, you can't do a Y-combinator in C# because it wants to evaluate parameters before calling functions.
-
Martijn Pieters almost 9 yearsIt is slightly more than a link though; it is a link with a very brief summary. A longer summary would be appreciated.
-
Yavar over 8 yearsIt is just a link BUT it cannot get better than this. This answer deserves (add1 votes) with no base case condition to exit; aka infinite recursion.
-
Admin over 8 yearshaha! Yep, the young one (me) can still understand...
-
Mörre over 8 yearsYou lost me when you introduced the function
recurser
. Not the slightest idea what it's doing, or why. -
Wayne over 8 yearsWe're trying to build up to a generic recursive solution for functions that aren't explicitly recursive. The
recurser
function is the first step toward this goal, because it gives us a recursive version offact
that never references itself by name. -
Jørgen Fogh over 8 years@Andre MacFie: I didn't comment on the effort, I commented on the quality. In general, the policy on Stack Overflow is that answers should be self contained, with links to more information.
-
YoTengoUnLCD about 8 years@WayneBurkett It's a pretty common practice in mathematics.
-
VoronoiPotato almost 8 yearsexcept in IE. kangax.github.io/nfe
-
Noctis Skytower over 7 yearsAre you sure it does not create more problems than it solves?
-
zumalifeguard over 7 yearsNoctis, can you clarify your question? Are you asking whether the concept of a y-combinator itself creates more problems than it solves, or are you talking about specifically that I chose to demonstrate using JavaScript in particular, or my specific implementation or my recommendation to learn it by discovering it yourself as I described?
-
v7d8dpo4 over 7 yearsNice explanation. Why did you write
function (n) { return builder(builder)(n);}
instead ofbuilder(builder)
? -
btilly over 7 years@v7d8dpo4 Because I was turning a function of 2 variables into a higher order function of one variable using currying.
-
TheChetan about 7 yearsIs this the reason we need closures?
-
btilly about 7 years@TheChetan Closures let us tie customized behavior behind a call to an anonymous function. It is just another abstraction technique.
-
obataku over 6 years@YoTengoUnLCD: not quite--functionals are those map from function spaces to some field of scalars, not just general purpose maps of functions to functions
-
neevek about 6 years@WayneBurkett, Can I rewrite the Y combinator like this:
function Y(recurse) { return recurse(recurse); } let factorial = Y(creator => value => { return value == 0 ? 1 : value * creator(creator)(value - 1); });
. And this is how I digest it(not sure if it is correct): By not explicitly referencing the function(not allowed as a combinator), we can use two partially applied/curried functions(a creator function and the calculate function), with which we can create lambda/anonymous functions that achieve recursive without need for a name for the calculate function? -
Saw Thinkar Nay Htoo almost 6 yearsI thought it was real and I ended up here. youtube.com/watch?v=HyWqxkaQpPw Recent Article futurism.com/scientists-made-real-life-flux-capacitor
-
Dathan almost 6 yearsI think Mads Torgersen correctly implements the Y combinator in C# at blogs.msdn.microsoft.com/madst/2007/05/11/…
-
Will Ness almost 6 yearsthis should be the accepted answer. BTW, with
U x = x x
,Y = U . (. U)
(abusing Haskell-like notation). IOW, with proper combinators,Y = BU(CBU)
. Thus,Yf = U (f . U) = (f . U) (f . U) = f (U (f . U)) = f ((f . U) (f . U))
. -
toraritte over 5 years@galdre is right. It is a great link, but it is just a link. It has also been mentioned in 3 other answers below but only as a supporting document as they all good explanations on their own. This answer also doesn't even attempt to answer the OP's questions.
-
Quelklef over 5 yearsY combinator can work with pass-by-value and lazy evaluation.
-
mike over 4 yearsI think this answer could be especially confusing for non-English speakers. One might devote quite some time to understanding this claim before (or never) realizing that it is a humorous popular culture reference. (I like it, I just would feel bad if I had answered this and discovered that someone learning was discouraged by it)
-
TYeung almost 3 yearsThis is a great answer and breaks down Y combinator nicely. However, I feel like "a recursive function of 1 variable using only functions of 1 variables and no assignments" doesn't provide enough incentive for writing a Y combinator since you can easily write a normal factorial satisfying the criteria. I am guessing that the function being anonymous should also be a requirement?
-
btilly almost 3 years@LearningMathematics Declaring a function is, in fact, a form of assignment. In most languages, it is in a different namespace though. But in JavaScript it isn't, you can even replace a declared function with assignment!
-
TYeung almost 3 years@btilly is passing parameters to a function a form of assignment then?
-
btilly almost 3 years@LearningMathematics No. It is creating a new environment with the name already bound to it. This may seem like an arbitrary distinction, but from both the view of a compiler, and the view of functional programming, it is an important one. There is only one place to look for the binding. Where you declare the environment.
-
Everton J. Carpes over 2 yearsYour step-by-step approach is pretty good, thanks for sharing it.