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?

up vote 20 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.

  • How do you get from 1st step to the second? – aroma Apr 23 at 14:20
  • Ohh okay I get it. – aroma Apr 23 at 14:26

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$.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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