Fixed point combinator, Fixed point combinator - Example, Fixed point combinator - Existence of fixed point combinators, Fixed point combinator - Other fixed point combinators, combinatory logic, untyped lambda calculus, typed lambda calculus, anonymous recursion
ARTICLES RELATED TO Fixed point combinator - Example
Consider the factorial function (under Church encoding). The usual recursive mathematical equation is
fact(n) = if n=0 then 1 else n * fact(n-1)
We can express a "single step" of this recursion in lambda calculus as
F = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x))),
where "f" is a place-holder argument for the factorial function to be passed to itself. The function F performs a single step in the evaluation of the recursive formula. A ...
In certain formalizations of mathematics, such as the untyped lambda calculus and combinatorial calculus, every expression can be considered a higher-order function. In these formalizations, the existence of a fixed-point combinator means that every function has at least one fixed point; a function may have more than one distinct fixed point.
In some other systems, for example the simply typed lambda calculus, a well-typed fixed-point combinator cannot be written -- in those systems any support for recursion must be explicitly ...
A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
The Y combinator can be expressed in the SKI-calculus as
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
The simplest fixed point combinator in the SK-calculus, found by John Tromp, is
Y = S S K (S (K (S S (S (S S K)))) K)
which corresponds to the lambda expres ...
A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
The Y combinator can be expressed in the SKI-calculus as
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
The simplest fixed point combinator in the SK-calculus, found by John Tr ...
