Fixed-point Combinator

In computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function that computes a fixed point of other functions. If the effect of the other function is to advance a particular computation one step, or to do nothing if the computation is finished, then the fixed point will be a function that advances the same computation by as many steps as required to complete it. This can be used to construct recursive anonymous functions.

A fixed point of a function f is a value that f doesn't change (x such that f(x) = x ). Consider the function f(x) = x2. 0 and 1 are fixed points of this function, because 0 = 02 and 1 = 12. This function has no other fixed points.

A very different example comes up with many familiar markup languages. For example, HTML list elements contain item elements which contain paragraphs (p elements) which contain text, emphasis elements like b and i, and so on (this amounts to a tree). Given a set of elements, it is often useful also to retrieve all of their descendents. One way is to define a simpler function (call it f) that takes a set of elements, and returns a set that contains all of those elements plus all of their (direct) child elements. For example, if x is a set of 3 paragraphs, f(x) includes those 3 paragraphs and all of the emphasis elements, text, and other they directly contain. If you use f again (f(f(x))), you add all of x's grandchild elements. Repeating eventually accumulates all of the descendants. Then evaluating f again can never add any more elements. This is a fixed-point for f, because the set returned by f is the same as the set passed to f. Thus, a function g that applies f repeatedly and returns the set of original elements and all their descendants, is a fixed-point combinator.

The Recursive join in relational databases is very similar.

The function for which any input is a fixed point is called the Identity function. Other functions have the special property that after being applied once, further applications don't have any effect. More formally: f(f(x)) = f(x) for all x. Such functions are called idempotent. An example of such a function is the function that returns 0 for all even integers, and 1 for all odd integers.

When f is a first-order function (a function on "simple" values such as integers), a fixed point is a first-order value. However, the notion also applies to higher-order functions: f takes another function p such that p = f(p). A fixed-point combinator, then, is a function g which produces such a fixed point p for any function f:

g(f) = p, where p = f(p)

or, alternatively:

g(f) = f(g(f)).

Because fixed-point combinators are higher-order functions, their history is intimately related to the development of lambda calculus. One well-known fixed-point combinator in the untyped lambda calculus is Haskell Curry's Y = λf·(λx·f (x x)) (λx·f (x x)). The name of this combinator is sometimes incorrectly used to refer to any fixed-point combinator. The untyped lambda calculus however, contains an infinitude of fixed-point combinators. Fixed-point combinators do not necessarily exist in more restrictive models of computation. For instance, they do not exist in simply typed lambda calculus.

In programming languages that support anonymous functions, fixed-point combinators allow the definition and use of anonymous recursive functions, i.e. without having to bind such functions to identifiers. In this setting, the use of fixed-point combinators is sometimes called anonymous recursion.