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) = x, because 0 = 0 and 1 = 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.

PropertyValue
dbpprop:abstract
  • 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) = x, because 0 = 0 and 1 = 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: p = g(f), f(p) = p or, alternately: f(g) = 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·f). 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.
  • 不动点组合子（或不动点算子）是计算其他函数的一个不动点的高阶函数。 函数 f 的不动点是一个值 x 使得 f(x) = x。例如，0 和 1 是函数 f(x) = x 的不动点，因为 0 = 0 而 1 = 1。鉴于一阶函数（在简单值比如整数上的函数）的不动点是个一阶值，高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g。那么，不动点算子是任何函数 fix 使得对于任何函数 f 都有 f(fix) = fix(f). 不动点组合子允许定义匿名的递归函数。有些令人惊奇，它们可以用非递归的lambda 抽象来定义。
dbpprop:hasPhotoCollection
dbpprop:reference
rdfs:comment
  • 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) = x, because 0 = 0 and 1 = 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.
  • 不动点组合子（或不动点算子）是计算其他函数的一个不动点的高阶函数。 函数 f 的不动点是一个值 x 使得 f(x) = x。例如，0 和 1 是函数 f(x) = x 的不动点，因为 0 = 0 而 1 = 1。鉴于一阶函数（在简单值比如整数上的函数）的不动点是个一阶值，高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g。那么，不动点算子是任何函数 fix 使得对于任何函数 f 都有 f(fix) = fix(f).
rdfs:label
  • Fixed point combinator
  • 不动点组合子
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of