106 lines
4.1 KiB
Markdown
106 lines
4.1 KiB
Markdown
---
|
|
created_at: '2013-11-11T07:33:45.000Z'
|
|
title: What is a y-combinator? (2008)
|
|
url: http://stackoverflow.com/questions/93526/what-is-a-y-combinator
|
|
author: emanuelsaringan
|
|
points: 57
|
|
story_text: ''
|
|
comment_text:
|
|
num_comments: 20
|
|
story_id:
|
|
story_title:
|
|
story_url:
|
|
parent_id:
|
|
created_at_i: 1384155225
|
|
_tags:
|
|
- story
|
|
- author_emanuelsaringan
|
|
- story_6710450
|
|
objectID: '6710450'
|
|
year: 2008
|
|
|
|
---
|
|
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](http://en.wikipedia.org/wiki/Lambda_calculus). The
|
|
[expression](http://en.wikipedia.org/wiki/Expression_\(programming\))-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](http://en.wikipedia.org/wiki/Type_system#Type_checking)
|
|
languages (which [procedural
|
|
languages](http://en.wikipedia.org/wiki/Procedural_programming) 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:
|
|
|
|
``` lang-c# prettyprint-override
|
|
// 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.
|
|
|
|
``` lang-c# prettyprint-override
|
|
// 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.
|
|
|
|
``` lang-c# prettyprint-override
|
|
// 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**.
|