Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in mathematical language) that, given a function $f$, returns a fixed point of $f$. In mathematical language,

$$f(G(f)) = G(f)$$

This can be considered the defining equation of a fixed-point combinator.

Note that $f$ might be a function whose range and domain are themselves function spaces -- in fact this is the most common use of a fixed-point combinator: you can define a function $\alpha$ by specifying that it is the fixed point of another function $f$, and then compute $\alpha$ as $G(f)$.

As mathematicians we're used to functions having names, eg $f:x\mapsto x^2$ is the function called $f$ that maps $x$ to $x^2$. But there's no reason why you can't have anonymous function. Since the lambda calculus deals with these a lot, there's a special notation for them:

$$\lambda x.x^2$$

is the function that takes $x$ to $x^2$, so that e.g. $(\lambda x.x^2)(2) = 4$. When there's no ambiguity, we can write function application by concatenation: $(\lambda x.x^2) 2 = 4$, and if we defined $f = \lambda x.x^2$ then $f\; 2 = 4$.

Okay, now we get to the meat of the question. The Y combinator is a higher-order function (functional) defined as

$$Y = \lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))$$

I can follow through the algebra and see that this is indeed a fixed-point combinator:

$$\begin{align} Y\; g & = (\lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))) \; g \\ & = (\lambda x. g (x\;x)) \; (\lambda x. g (x\;x)) \\ & = (\lambda y. g (y\;y)) \; (\lambda x. g (x\;x)) \\ & = g \; (\lambda x. g (x\;x)) (\lambda x. g (x\;x)) \\ & = g\; (Y\; g) \end{align}$$

but I have no intuition as to why it works, or how someone might have come up with it. More to the point, I don't see how it can be practically used to compute functions as fixed-points of functionals.

Anyone got a good 'intuitive' explanation?

share|improve this question
1  
A question about the history of the Y combinator: mathoverflow.net/questions/31893/… –  Carl Mummert Jul 13 '11 at 16:18
2  
The Y combinator is informally quite similar to the proof of Kleene's recursion theorem and to the proof of the fixed-point theorem in formal arithmetic. Here is a question where people tried to explain the version in arithmetic: mathoverflow.net/questions/30874/arithmetic-fixed-point-theorem/… –  Carl Mummert Jul 13 '11 at 16:21

2 Answers 2

up vote 7 down vote accepted

The $Y$ combinator is a function that takes a function $f$ and returns something applied to itself (specifically $\lambda x.f(xx)$). So if we want to make $Y(f)$ a fixed point of $f$, $Y(f)$ has to be equal to $f(Y(f))$. So we want some $a$ such that $aa = f(aa)$. Now, $a$ has access to itself (it is applied to itself). Because of this, we can directly create such an $a$. $$aa=f(aa)$$ $$a=\lambda a.f(aa)$$ $$a=\lambda x.f(xx)$$ $$Y=\lambda f.aa=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$ Essentially, by applying $a$ to itself, you are giving $a$ a reference to itself, allowing it to use itself in a recursive manner. However, $a$ is only an intermediate value - it is not the recursive function itself, as it still needs a reference to itself to do the recursion. The $Y$ combinator completely eliminates this need by finding the fixed point - giving a function its final, recursive form.

share|improve this answer

The $Y$ combinator can be defined also Turing way. Let us use less formal but more descriptive variable names to define the combinator: $$ \begin{align} A &= \lambda \text{self}.\lambda f.f\ (\text{self}\ \text{self}\ f);\\ Y &= A\ A. \end{align} $$

The $A$ combinator can be considered as a function that takes itself as its first argument and the target function, fixed point of which is to be found, as the second one. It returns the function applied to $A\ A\ f$, just like we wanted.

Then, an arbitrary combinator F which is defined in the terms of itself like $$ F\ x\ y = F\ y\ x\ F $$ can be defined in terms of $Y$ and some other combinator $F_r$. Specifically, $$ F\ x\ y = F\ y\ x\ F $$ is equivalent to $$ F = \lambda x.\lambda y.F\ y\ x\ F, $$ which in turn follows from $$ F = (\lambda \text{self}.\lambda x.\lambda y.\text{self}\ y\ x\ \text{self}) F. $$ Finally, let us call the resulting subexpression $$ F_r = \lambda \text{self}.\lambda x.\lambda y.\text{self}\ y\ x\ \text{self}. $$ Then $F = Y\ F_r$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.