User:WillNess/Fixed-point combinator

Fixed-point combinator

In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator), is a higher-order function (i.e. a function which takes a function as argument) that returns some fixed point (a value that is mapped to itself) of its argument function, if one exists.

Formally, if ${\textrm {fix}}$ is a fixed-point combinator and the function $f$ has one or more fixed points, then ${\textrm {fix}}\ f$ is one of these fixed points, i.e.

${\textrm {fix}}\ f\ =f\ ({\textrm {fix}}\ f)=f\ (f\ ({\textrm {fix}}\ f))=\ ...$

Fixed-point combinators can be defined in the lambda calculus and in functional programming languages and provide a means to allow for recursive definitions, when recursion is seen as a computational step repeated an indefinite number of times – with the above equation seen as definition.

For example, a recursive definition of factorial can be seen as a repetition of the computational step performing the decision whether the received argument is a base case, where a final result is to be returned. Or it is not a base case, whereas the whole process should be repeated anew with an updated argument.

$f\ r\ n\ =if\ (base\ n)\ n'\ (r\ n'')$

$fact\ n\ =fix\ f\ n\ =f\ (fix\ f)\ n$

And because the argument $n$ can not be known in advance, this means that the computational step $f$ must be able to be repeated an indefinite number of times.

Y combinator in lambda calculus

In the classical untyped lambda calculus, every function has a fixed point. A particular implementation of ${\textrm {fix}}$ is Haskell Curry's paradoxical combinator Y, given by

$Y=\lambda f.\ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))$

(Here we use the standard notations and conventions of lambda calculus: Y is a function that takes one argument f and returns the entire expression following the first period; the expression $\lambda x.f\ (x\ x)$ denotes a function that takes one argument x, thought of as a function, and returns the expression $f\ (x\ x)$, where $(x\ x)$ denotes x applied to itself. Juxtaposition of expressions denotes function application, is left-associative, and has higher precedence than the period.)

In combinators notation, this is

                  $H\ f\ x\$       $:=\ f\ (x\$     $x$       $)$

$Y\ f\ :=H\ f\ (H\ f)=f\ (H\ f\ (H\ f))=f\ (Y\ f)$

Now, if

$F\ r\ y\ =\ ...\ z\ ...\ r\ y'\ ...$

expresses a "computational step" expecting $r$ to express "the rest of computation", which decides whether to "return" $z$ right away or to perform the rest of the computation $r\ y'\$ with the "updated argument value" $y'\$, then in

$Y\ F\ y\ =\ F\ (Y\ F)\ y\ =\ ...\ z\ ...\ (Y\ F)\ y'\ ...$

the rest of the computation $(Y\ F)$ is the same as $(Y\ F)$ itself, which is the definition of recursion, as a process which might use itself to perform the rest of computation with an updated argument, after considering whether to stop with some base case.

And $(Y\ F)\ y'\$, when "called", will become $F\ (Y\ F)\ y'\$, re-doing the same $F$ "function" again, with the same $(Y\ F)\$ and the updated $y'\$ as arguments. Thus the fixed point $R$ for the given computational step function $F$ is the recursive function $R\ =\ Y\ F\ =F\ (Y\ F)\ =\ F\ R\$ which uses $R\ =\ Y\ F\$ itself to perform the rest of the computation, if $F$ so chooses.