What is a Y-combinator

A combinator is an elementary function of higher order. "Elementary" means that this function is intended to build other functions on its basis; In some axiom systems, combinators are considered indivisible.

"Higher order" means that the function accepts or returns not a scalar value, but another function.

A fixed point is a term from mathematical analysis, it means a point x _{0 such} that f (x ₀ ) = x ₀ (each function has its fixed points).

Thus, a fixed point combinator is an elementary higher order function that searches for a specified function for its fixed point.

From the point of view of mathematics, the search for a fixed point is a solution to the equation, a rather difficult task. But everything changes when a fixed point is searched not for an ordinary function, but for a higher order function.

And so, let's say we have a function f, and it has a fixed point x:

fx = x 

By definition, a fixed point combinator must, for any f, find x:

 Y f = x 

Substituting the second equation in the first, we get

 f (Y f) = Y f 

Or, which is the same

 Y f = f (Y f) = f (f (f (f (f (f (f (f (f ...)))))))) 

This equality is true for any fixed point combinator, but for the combinator Y this is not just an equality, but also an algorithm: it works just like that. Of course, such infinite recursion is possible only in "lazy" versions of the λ-calculus.

What is this combinator used for? It is used to write recursive functions in languages ​​where there is no other way to do it.

Consider, for example, one of the possible factorial entries:

 fac n = if (n = 0) 1 (fac (n-1)) 

If the language prohibits making a direct recursive call (refer to fac from within the definition of fac) - you can use a fixed point combinator:

 fac = Y (λf . λn . if (n = 0) 1 (f (n-1))) 

In practice, almost no one writes that, because recursion is allowed in all normal languages.

In theory, the fixed point combinator is the standard implementation of recursive calls.