Fixed point combinator

related topics
{math, number, function}

A fixed point combinator (or fixed-point operator) is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that f(x) = x. For example, 0 and 1 are fixed points of the function f(x) = x2, because 02 = 0 and 12 = 1. Whereas a fixed-point of a first-order function (a function on "simple" values such as integers) is a first-order value, a fixed point of a higher-order function f is another function p such that f(p) = p. A fixed point combinator, then, is a function g which produces such a fixed point p for any function f:

or, alternately:

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 incorrectly used sometimes to refer to any fixed point combinator. The untyped lambda calculus however, contains an infinity 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 function literals, 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.[1][2]

Contents

How it works

Ignoring for now the question whether fixed point combinators even exist (to be addressed in the next section), we illustrate how a function satisfying the fixed point combinator equation works. To easily trace the computation steps, we choose untyped lambda calculus as our programming language. The (computational) equality from the equation that defines a fixed point combinator corresponds to beta reduction in lambda calculus.

Full article ▸

related documents
Paracompact space
Prim's algorithm
Commutator subgroup
Riemann mapping theorem
Compactification (mathematics)
Recursive descent parser
Augmented Backus–Naur Form
Open set
Outer product
Depth-first search
Existential quantification
Jules Richard
Gram–Schmidt process
Base (topology)
Poisson process
Octal
Generalized mean
Rank (linear algebra)
Pigeonhole principle
Riesz representation theorem
Definable real number
Trie
ML (programming language)
Boolean ring
Merkle-Hellman
Legendre polynomials
Closure (topology)
2 (number)
Procedural programming
Linear search