In mathematics and computer science in general, a fixed point of a function is a value that is mapped to itself by the function. In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator):page 26 is a higher-order function that returns some fixed point of its argument function, if one exists.
Formally, if the function f has one or more fixed points, then
and hence, by repeated application,
Because fixed-point combinators can be used to implement recursion, it is possible to use them to describe specific types of recursive computations, such as those in fixed-point iteration, iterative methods, recursive join in relational databases, data-flow analysis, FIRST and FOLLOW sets of non-terminals in a context-free grammar, transitive closure, and other types of closure operations.
A function for which every input is a fixed point is called an A function for which every input is a fixed point is called an identity function. Formally:
In contrast to universal quantification over all , a fixed-point combinator constructs one value that is a fixed point of . The remarkable property of a fixed-point combinator is that it constructs a fixed point for an arbitrary given function .
Other functions have the special property that, after being applied once, further applications don't have any effect. More formally: