Fixed-point combinator

Fixed-point combinator

The Y combinator is an implementation of a fixed-point combinator in lambda calculus. Fixed-point combinators may also be easily defined in other functional and imperative languages. The implementation in lambda calculus is more difficult due to limitations in lambda calculus. The fixed-point combinator may be used in a number of different areas:

• General mathematics
• Untyped lambda calculus
• Typed lambda calculus
• Functional programming
• Imperative programming

Fixed-point combinators may be applied to a range of different functions, but normally will not terminate unless there is an extra parameter. When the function to be fixed refers to its parameter, another call to the function is invoked, so the calculation never gets started. Instead, the extra parameter is used to trigger the start of the calculation.

The type of the fixed point is the return type of the function being fixed. This may be a real or a function or any other type.

In the untyped lambda calculus, the function to apply the fixed-point combinator to may be expressed using an encoding, like Church encoding. In this case particular lambda terms (which define functions) are considered as values. "Running" (beta reducing) the fixed-point combinator on the encoding gives a lambda term for the result, which may then be interpreted as fixed-point value.

Alternately, a function may be considered as a lambda term defined purely in lambda calculus.

These different approaches affect how a mathematician and a programmer may regard a fixed-point combinator. A mathematician may see the Y combinator applied to a function as being an expression satisfying the fixed-point equation, and therefore a solution.

In contrast, a person only wanting to apply a fixed-point combinator to some general programming task may see it only as a means of implementing recursion.

Values and domains

Many functions do not have any fixed points, for instance ${\displaystyle f:\mathbb{N}\to \mathbb{N}}$ with ${\displaystyle f(n)=n+1}$. Using Church encoding, natural numbers can be represented in lambda calculus, and this function f can be defined in lambda calculus. However, its domain will now contain all lambda expressions, not just those representing natural numbers. The Y combinator, applied to f, will yield a fixed-point for f, but this fixed-point won't represent a natural number. If trying to compute Y f in an actual programming language, an infinite loop will occur.

Function versus implementation

The fixed-point combinator may be defined in mathematics and then implemented in other languages. General mathematics defines a function based on its extensional properties. That is, two functions are equal if they perform the same mapping. Lambda calculus and programming languages regard function identity as an intensional property. A function's identity is based on its implementation.

A lambda calculus function (or term) is an implementation of a mathematical function. In the lambda calculus there are a number of combinators (implementations) that satisfy the mathematical definition of a fixed-point combinator.

Definition of the term "combinator"

Combinatory logic is a higher-order functions theory. A combinator is a closed lambda expression, meaning that it has no free variables. The combinators may be combined to direct values to their correct places in the expression without ever naming them as variables.

Recursive definitions and fixed-point combinators

Fixed-point combinators can be used to implement recursive definition of functions. However, they are rarely used in practical programming. Strongly normalizing type systems such as the simply typed lambda calculus disallow non-termination and hence fixed-point combinators often cannot be assigned a type or require complex type system features. Furthermore, fixed-point combinators are often inefficient compared to other strategies for implementing recursion, as they require more function reductions and construct and take apart a tuple for each group of mutually recursive definitions.

The factorial function

The factorial function provides a good example of how a fixed-point combinator may be used to define recursive functions. The standard recursive definition of the factorial function in mathematics can be written as

${\displaystyle \mathrm{fact}n=\{\begin{array}{ll}1& \text{if}n=0\\ n\times \mathrm{fact}(n-1)& \text{otherwise.}\end{array}}$

where n is a non-negative integer.

This poses a problem, though, as ${\displaystyle \mathrm{fact}}$ inside the definition of ${\displaystyle \mathrm{fact}}$ cannot possibly signify the inclusion of the definition as a whole inside itself. Instead, as it normally goes almost unnoticed, it is the reference to the definition by its name. This presupposes the existence of a global registry of names, so called "environment". And the lambda calculus lacks this entirely.

Still, name references do exist in lambda calculus – local names, names of parameters of a given function. And thus the above can be re-written as

${\displaystyle \begin{array}{cc}& \mathrm{fact}(n)=\mathrm{f}(\mathrm{f},n)\\ & \text{where}\\ & \mathrm{f}(s,n)=\{\begin{array}{ll}1& \text{if}n=0\\ n\times s(s,n-1)& \text{otherwise}\end{array}\end{array}}$

Splitting off a separate copy of ${\displaystyle \mathrm{f}}$ and passing it as an argument to itself makes it available to itself to be called, as and if needed, inside itself. In such a call it must again be passed along as an argument so it will be available to the next invocation, and so on, as the chain of invocations progresses. The definition of ${\displaystyle \mathrm{f}}$ is open recursive, and calling ${\displaystyle \mathrm{f}}$ with itself as an argument at the top closes the circle.

Implementing this in lambda calculus is now trivial, and directly leads to the definition of the Y combinator, one instance of a fixed-point combinator, such that ${\displaystyle \mathrm{fix}f=f(\mathrm{fix}f)}$. Or directly, define a function F of two arguments f and n:

${\displaystyle Ffn=(\mathrm{IsZero}n)1(\mathrm{multiply}n(f(\mathrm{pred}n)))}$

(Here ${\displaystyle (\mathrm{IsZero}n)}$ is a function that takes two arguments and returns its first argument if n=0, and its second argument otherwise; ${\displaystyle \mathrm{pred}n}$ evaluates to n–1.)

Now define ${\displaystyle \mathrm{fact}=\mathsf{\text{fix}}F=F(\mathsf{\text{fix}}F)}$. Then ${\displaystyle \mathrm{fact}}$ is a fixed-point of F, which gives

${\displaystyle \begin{array}{cc}\mathrm{fact}n& =F\mathrm{fact}n\\ & =(\mathrm{IsZero}n)1(\mathrm{multiply}n(\mathrm{fact}(\mathrm{pred}n)))\end{array}}$

as desired.

Fixed-point combinators in lambda calculus

The Y combinator, discovered by Haskell Curry, is defined as

${\displaystyle Y=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))}$

Other fixed-point combinators

In untyped lambda calculus fixed-point combinators are not especially rare. In fact there are infinitely many of them. In 2005 Mayer Goldberg showed that the set of fixed-point combinators of untyped lambda calculus is recursively enumerable.

The Y combinator can be expressed in the SKI-calculus as

${\displaystyle \mathsf{Y}\mathsf{=}\mathsf{S}\mathsf{(}\mathsf{K}\mathsf{(}\mathsf{S}\mathsf{I}\mathsf{I}\mathsf{)}\mathsf{)}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{K}\mathsf{S}\mathsf{)}\mathsf{K}\mathsf{)}\mathsf{(}\mathsf{K}\mathsf{(}\mathsf{S}\mathsf{I}\mathsf{I}\mathsf{)}\mathsf{)}\mathsf{)}\mathsf{=}\mathsf{S}\mathsf{S}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{K}\mathsf{S}\mathsf{)}\mathsf{K}\mathsf{)}\mathsf{)}\mathsf{(}\mathsf{K}\mathsf{(}\mathsf{S}\mathsf{I}\mathsf{I}\mathsf{)}\mathsf{)}}$

Additional combinators (B, C, K, W system) allow for much shorter encodings. With ${\displaystyle \mathsf{U}\mathsf{=}\mathsf{S}\mathsf{I}\mathsf{I}}$ the self-application combinator, since ${\displaystyle \mathsf{S}(\mathsf{K}x)yz=x(yz)=\mathsf{B}xyz}$ and ${\displaystyle \mathsf{S}x(\mathsf{K}y)z=xzy=\mathsf{C}xyz}$, the above becomes

${\displaystyle \mathsf{Y}\mathsf{=}\mathsf{S}\mathsf{(}\mathsf{K}\mathsf{U}\mathsf{)}\mathsf{(}\mathsf{S}\mathsf{B}\mathsf{(}\mathsf{K}\mathsf{U}\mathsf{)}\mathsf{)}\mathsf{=}\mathsf{B}\mathsf{U}\mathsf{(}\mathsf{C}\mathsf{B}\mathsf{U}\mathsf{)};\mathsf{Y}\mathsf{=}\mathsf{S}\mathsf{S}\mathsf{I}\mathsf{(}\mathsf{B}\mathsf{W}\mathsf{B}\mathsf{)}}$

The shortest fixed-point combinator in the SK-calculus using S and K combinators only, found by John Tromp, is

${\displaystyle {\mathsf{Y}}^{\prime }\mathsf{=}\mathsf{S}\mathsf{S}\mathsf{K}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{K}\mathsf{(}\mathsf{S}\mathsf{S}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{S}\mathsf{S}\mathsf{K}\mathsf{)}\mathsf{)}\mathsf{)}\mathsf{)}\mathsf{K}\mathsf{)}\mathsf{=}\mathsf{W}\mathsf{C}\mathsf{(}\mathsf{S}\mathsf{B}\mathsf{(}\mathsf{C}\mathsf{(}\mathsf{W}\mathsf{C}\mathsf{)}\mathsf{)}\mathsf{)}}$

although note that it is not in normal form, which is longer. This combinator corresponds to the lambda expression

${\displaystyle {\mathsf{Y}}^{\prime }=(\lambda xy.xyx)(\lambda yx.y(xyx))}$

The following fixed-point combinator is simpler than the Y combinator, and β-reduces into the Y combinator; it is sometimes cited as the Y combinator itself:

${\displaystyle \mathsf{X}=\lambda f.(\lambda x.xx)(\lambda x.f(xx));\mathsf{X}\mathsf{f}\mathsf{=}\mathsf{U}\mathsf{(}\mathsf{B}\mathsf{f}\mathsf{U}\mathsf{)}}$

Another common fixed-point combinator is the Turing fixed-point combinator (named after its discoverer, Alan Turing):

${\displaystyle \mathrm{\Theta }=(\lambda xy.y(xxy))(\lambda xy.y(xxy))=\mathsf{S}\mathsf{I}\mathsf{I}\mathsf{(}\mathsf{S}\mathsf{(}\mathsf{K}\mathsf{(}\mathsf{S}\mathsf{I}\mathsf{)}\mathsf{)}\mathsf{(}\mathsf{S}\mathsf{I}\mathsf{I}\mathsf{)}\mathsf{)}\mathsf{=}\mathsf{U}\mathsf{(}\mathsf{B}\mathsf{(}\mathsf{S}\mathsf{I}\mathsf{)}\mathsf{U}\mathsf{)}}$

Its advantage over ${\displaystyle \mathsf{Y}}$ is that ${\displaystyle \mathrm{\Theta }f}$ beta-reduces to ${\displaystyle f(\mathrm{\Theta }f)}$, whereas ${\displaystyle \mathsf{Y}f}$ and ${\displaystyle f(\mathsf{Y}f)}$ only beta-reduce to a common term.

${\displaystyle \mathrm{\Theta }}$ also has a simple call-by-value form:

${\displaystyle {\mathrm{\Theta }}_v=(\lambda xy.y(\lambda z.xxyz))(\lambda xy.y(\lambda z.xxyz))}$

The analog for mutual recursion is a polyvariadic fix-point combinator, which may be denoted Y*.

Strict fixed-point combinator

In a strict programming language the Y combinator will expand until stack overflow, or never halt in case of tail call optimization. The Z combinator will work in strict languages (also called eager languages, where applicative evaluation order is applied). The Z combinator has the next argument defined explicitly, preventing the expansion of ${\displaystyle Zg}$ in the right-hand side of the definition:

${\displaystyle Zgv=g(Zg)v.}$

and in lambda calculus it is an eta-expansion of the Y combinator:

${\displaystyle Z=\lambda f.(\lambda x.f(\lambda v.xxv))(\lambda x.f(\lambda v.xxv)).}$

Non-standard fixed-point combinators

If F is a fixed-point combinator in untyped lambda calculus, then there is:

${\displaystyle \mathsf{F}=\lambda x.Fx=\lambda x.x(Fx)=\lambda x.x(x(Fx))=\cdots }$

Terms that have the same Böhm tree as a fixed-point combinator, i.e., have the same infinite extension ${\displaystyle \lambda x.x(x(x\cdots ))}$, are called non-standard fixed-point combinators. Any fixed-point combinator is also a non-standard one, but not all non-standard fixed-point combinators are fixed-point combinators because some of them fail to satisfy the fixed-point equation that defines the "standard" ones. These combinators are called strictly non-standard fixed-point combinators; an example is the following combinator:

${\displaystyle \mathsf{N}\mathsf{=}\mathsf{B}\mathsf{U}\mathsf{(}\mathsf{B}\mathsf{(}\mathsf{B}\mathsf{U}\mathsf{)}\mathsf{B}\mathsf{)}}$

where

${\displaystyle \mathsf{B}=\lambda xyz.x(yz)}$

${\displaystyle \mathsf{U}=\lambda x.xx}$

since

${\displaystyle \mathsf{N}=\lambda x.Nx=\lambda x.x(N_{2}x)=\lambda x.x(x(x(N_{3}x)))=\lambda x.x(x(x(x(x(x(N_{4}x))))))=\cdots }$

where ${\displaystyle {\mathsf{N}}_i}$ are modifications of ${\displaystyle \mathsf{N}}$ created on the fly which add ${\displaystyle i}$ instances of ${\displaystyle x}$ at once into the chain while being replaced with ${\displaystyle {\mathsf{N}}_{i+1}}$.

The set of non-standard fixed-point combinators is not recursively enumerable.

Implementation in other languages

The Y combinator is a particular implementation of a fixed-point combinator in lambda calculus. Its structure is determined by the limitations of lambda calculus. It is not necessary or helpful to use this structure in implementing the fixed-point combinator in other languages.

Simple examples of fixed-point combinators implemented in some programming paradigms are given below.

Lazy functional implementation

In a language that supports lazy evaluation, as in Haskell, it is possible to define a fixed-point combinator using the defining equation of the fixed-point combinator which is conventionally named fix. Since Haskell has lazy data types, this combinator can also be used to define fixed points of data constructors (and not only to implement recursive functions). The definition is given here, followed by some usage examples. In Hackage, the original sample is:

<span id="mwAh8"></span><span class="nf" id="mwAiA">fix</span><span class="p" id="mwAiE">,</span><span class="w" id="mwAiI"> </span><span class="n" id="mwAiM">fix'</span><span class="w" id="mwAiQ"> </span><span class="ow" id="mwAiU">::</span><span class="w" id="mwAiY"> </span><span class="p" id="mwAic">(</span><span class="n" id="mwAig">a</span><span class="w" id="mwAik"> </span><span class="ow" id="mwAio">-></span><span class="w" id="mwAis"> </span><span class="n" id="mwAiw">a</span><span class="p" id="mwAi0">)</span><span class="w" id="mwAi4"> </span><span class="ow" id="mwAi8">-></span><span class="w" id="mwAjA"> </span><span class="n" id="mwAjE">a</span> <span class="nf" id="mwAjI">fix</span><span class="w" id="mwAjM"> </span><span class="n" id="mwAjQ">f</span><span class="w" id="mwAjU"> </span><span class="ow" id="mwAjY">=</span><span class="w" id="mwAjc"> </span><span class="kr" id="mwAjg">let</span><span class="w" id="mwAjk"> </span><span class="n" id="mwAjo">x</span><span class="w" id="mwAjs"> </span><span class="ow" id="mwAjw">=</span><span class="w" id="mwAj0"> </span><span class="n" id="mwAj4">f</span><span class="w" id="mwAj8"> </span><span class="n" id="mwAkA">x</span><span class="w" id="mwAkE"> </span><span class="kr" id="mwAkI">in</span><span class="w" id="mwAkM"> </span><span class="n" id="mwAkQ">x</span><span class="w" id="mwAkU"> </span><span class="c1" id="mwAkY">-- Lambda dropped. Sharing.</span> <span class="w" id="mwAkc"> </span><span class="c1" id="mwAkg">-- Original definition in Data.Function.</span> <span class="c1" id="mwAkk">-- alternative:</span> <span class="nf" id="mwAko">fix'</span><span class="w" id="mwAks"> </span><span class="n" id="mwAkw">f</span><span class="w" id="mwAk0"> </span><span class="ow" id="mwAk4">=</span><span class="w" id="mwAk8"> </span><span class="n" id="mwAlA">f</span><span class="w" id="mwAlE"> </span><span class="p" id="mwAlI">(</span><span class="n" id="mwAlM">fix'</span><span class="w" id="mwAlQ"> </span><span class="n" id="mwAlU">f</span><span class="p" id="mwAlY">)</span><span class="w" id="mwAlc"> </span><span class="c1" id="mwAlg">-- Lambda lifted. Non-sharing.</span> <span class="nf" id="mwAlk">fix</span><span class="w" id="mwAlo"> </span><span class="p" id="mwAls">(</span><span class="nf" id="mwAlw">\</span><span class="n" id="mwAl0">x</span><span class="w" id="mwAl4"> </span><span class="ow" id="mwAl8">-></span><span class="w" id="mwAmA"> </span><span class="mi" id="mwAmE">9</span><span class="p" id="mwAmI">)</span><span class="w" id="mwAmM"> </span><span class="c1" id="mwAmQ">-- this evaluates to 9</span> <span class="nf" id="mwAmU">fix</span><span class="w" id="mwAmY"> </span><span class="p" id="mwAmc">(</span><span class="nf" id="mwAmg">\</span><span class="n" id="mwAmk">x</span><span class="w" id="mwAmo"> </span><span class="ow" id="mwAms">-></span><span class="w" id="mwAmw"> </span><span class="mi" id="mwAm0">3</span><span class="kt" id="mwAm4">:</span><span class="n" id="mwAm8">x</span><span class="p" id="mwAnA">)</span><span class="w" id="mwAnE"> </span><span class="c1" id="mwAnI">-- evaluates to the lazy infinite list [3,3,3,...]</span> <span class="nf" id="mwAnM">fact</span><span class="w" id="mwAnQ"> </span><span class="ow" id="mwAnU">=</span><span class="w" id="mwAnY"> </span><span class="n" id="mwAnc">fix</span><span class="w" id="mwAng"> </span><span class="n" id="mwAnk">fac</span><span class="w" id="mwAno"> </span><span class="c1" id="mwAns">-- evaluates to the factorial function</span> <span class="w" id="mwAnw"> </span><span class="kr" id="mwAn0">where</span><span class="w" id="mwAn4"> </span><span class="n" id="mwAn8">fac</span><span class="w" id="mwAoA"> </span><span class="n" id="mwAoE">f</span><span class="w" id="mwAoI"> </span><span class="mi" id="mwAoM">0</span><span class="w" id="mwAoQ"> </span><span class="ow" id="mwAoU">=</span><span class="w" id="mwAoY"> </span><span class="mi" id="mwAoc">1</span> <span class="w" id="mwAog"> </span><span class="n" id="mwAok">fac</span><span class="w" id="mwAoo"> </span><span class="n" id="mwAos">f</span><span class="w" id="mwAow"> </span><span class="n" id="mwAo0">x</span><span class="w" id="mwAo4"> </span><span class="ow" id="mwAo8">=</span><span class="w" id="mwApA"> </span><span class="n" id="mwApE">x</span><span class="w" id="mwApI"> </span><span class="o" id="mwApM">*</span><span class="w" id="mwApQ"> </span><span class="n" id="mwApU">f</span><span class="w" id="mwApY"> </span><span class="p" id="mwApc">(</span><span class="n" id="mwApg">x</span><span class="o" id="mwApk">-</span><span class="mi" id="mwApo">1</span><span class="p" id="mwAps">)</span> <span class="nf" id="mwApw">fact</span><span class="w" id="mwAp0"> </span><span class="mi" id="mwAp4">5</span><span class="w" id="mwAp8"> </span><span class="c1" id="mwAqA">-- evaluates to 120</span>

Strict functional implementation

In a strict functional language, as illustrated below with OCaml, the argument to f is expanded beforehand, yielding an infinite call sequence,

${\displaystyle f(f...(f(\mathsf{f}\mathsf{i}\mathsf{x}f))...)x}$.

This may be resolved by defining fix with an extra parameter.

<span id="mwAqs"></span><span class="k" id="mwAqw">let</span> <span class="k" id="mwAq0">rec</span> <span class="n" id="mwAq4">fix</span> <span class="n" id="mwAq8">f</span> <span class="n" id="mwArA">x</span> <span class="o" id="mwArE">=</span> <span class="n" id="mwArI">f</span> <span class="o" id="mwArM">(</span><span class="n" id="mwArQ">fix</span> <span class="n" id="mwArU">f</span><span class="o" id="mwArY">)</span> <span class="n" id="mwArc">x</span> <span class="c" id="mwArg">(* note the extra x; hence fix f = \x-> f (fix f) x *)</span> <span class="k" id="mwArk">let</span> <span class="n" id="mwAro">factabs</span> <span class="n" id="mwArs">fact</span> <span class="o" id="mwArw">=</span> <span class="k" id="mwAr0">function</span> <span class="c" id="mwAr4">(* factabs has extra level of lambda abstraction *)</span> <span class="mi" id="mwAr8">0</span> <span class="o" id="mwAsA">-></span> <span class="mi" id="mwAsE">1</span> <span class="o" id="mwAsI">|</span> <span class="n" id="mwAsM">x</span> <span class="o" id="mwAsQ">-></span> <span class="n" id="mwAsU">x</span> <span class="o" id="mwAsY">*</span> <span class="n" id="mwAsc">fact</span> <span class="o" id="mwAsg">(</span><span class="n" id="mwAsk">x</span><span class="o" id="mwAso">-</span><span class="mi" id="mwAss">1</span><span class="o" id="mwAsw">)</span> <span class="k" id="mwAs0">let</span> <span class="o" id="mwAs4">_</span> <span class="o" id="mwAs8">=</span> <span class="o" id="mwAtA">(</span><span class="n" id="mwAtE">fix</span> <span class="n" id="mwAtI">factabs</span><span class="o" id="mwAtM">)</span> <span class="mi" id="mwAtQ">5</span> <span class="c" id="mwAtU">(* evaluates to "120" *)</span>

In a multi-paradigm functional language (one decorated with imperative features), such as Lisp, Peter Landin suggested the use of a variable assignment to create a fixed-point combinator, as in the below example using Scheme:

<span id="mwAuA"></span><span class="p" id="mwAuE">(</span><span class="k" id="mwAuI">define</span><span class="w" id="mwAuM"> </span><span class="nv" id="mwAuQ">Y!</span> <span class="w" id="mwAuU"> </span><span class="p" id="mwAuY">(</span><span class="k" id="mwAuc">lambda</span><span class="w" id="mwAug"> </span><span class="p" id="mwAuk">(</span><span class="nf" id="mwAuo">f</span><span class="p" id="mwAus">)</span> <span class="w" id="mwAuw"> </span><span class="p" id="mwAu0">((</span><span class="k" id="mwAu4">lambda</span><span class="w" id="mwAu8"> </span><span class="p" id="mwAvA">(</span><span class="nf" id="mwAvE">g</span><span class="p" id="mwAvI">)</span><span class="w" id="mwAvM"> </span> <span class="w" id="mwAvQ"> </span><span class="p" id="mwAvU">(</span><span class="k" id="mwAvY">set!</span><span class="w" id="mwAvc"> </span><span class="nv" id="mwAvg">g</span><span class="w" id="mwAvk"> </span><span class="p" id="mwAvo">(</span><span class="nf" id="mwAvs">f</span><span class="w" id="mwAvw"> </span><span class="p" id="mwAv0">(</span><span class="k" id="mwAv4">lambda</span><span class="w" id="mwAv8"> </span><span class="p" id="mwAwA">(</span><span class="nf" id="mwAwE">x</span><span class="p" id="mwAwI">)</span><span class="w" id="mwAwM"> </span><span class="p" id="mwAwQ">(</span><span class="nf" id="mwAwU">g</span><span class="w" id="mwAwY"> </span><span class="nv" id="mwAwc">x</span><span class="p" id="mwAwg">))))</span><span class="w" id="mwAwk"> </span><span class="c1" id="mwAwo">;; (set! g expr) assigns g the value of expr,</span> <span class="w" id="mwAws"> </span><span class="nv" id="mwAww">g</span><span class="p" id="mwAw0">)</span><span class="w" id="mwAw4"> </span><span class="c1" id="mwAw8">;; replacing g's initial value of #f, creating </span> <span class="w" id="mwAxA"> </span><span class="no" id="mwAxE">#f</span><span class="p" id="mwAxI">)))</span><span class="w" id="mwAxM"> </span><span class="c1" id="mwAxQ">;; thus the truly self-referential value in g</span>

Using a lambda calculus with axioms for assignment statements, it can be shown that Y! satisfies the same fixed-point law as the call-by-value Y combinator:

${\displaystyle (Y_{!}\lambda x.e)e^{\prime }=(\lambda x.e)(Y_{!}\lambda x.e)e^{\prime }}$

In more idiomatic modern Scheme usage, this would typically be handled via a letrec expression, as lexical scope was introduced to Lisp in the 1970s:

<span id="mwAyc"></span><span class="p" id="mwAyg">(</span><span class="k" id="mwAyk">define</span><span class="w" id="mwAyo"> </span><span class="nv" id="mwAys">Y*</span> <span class="w" id="mwAyw"> </span><span class="p" id="mwAy0">(</span><span class="k" id="mwAy4">lambda</span><span class="w" id="mwAy8"> </span><span class="p" id="mwAzA">(</span><span class="nf" id="mwAzE">f</span><span class="p" id="mwAzI">)</span> <span class="w" id="mwAzM"> </span><span class="p" id="mwAzQ">(</span><span class="k" id="mwAzU">letrec</span><span class="w" id="mwAzY"> </span><span class="c1" id="mwAzc">;; (letrec ((g expr)) ...) locally defines g </span> <span class="w" id="mwAzg"> </span><span class="p" id="mwAzk">((</span><span class="nf" id="mwAzo">g</span><span class="w" id="mwAzs"> </span><span class="c1" id="mwAzw">;; as expr recursively: g in expr refers to </span> <span class="w" id="mwAz0"> </span><span class="p" id="mwAz4">(</span><span class="nf" id="mwAz8">f</span><span class="w" id="mwA0A"> </span><span class="p" id="mwA0E">(</span><span class="k" id="mwA0I">lambda</span><span class="w" id="mwA0M"> </span><span class="p" id="mwA0Q">(</span><span class="nf" id="mwA0U">x</span><span class="p" id="mwA0Y">)</span><span class="w" id="mwA0c"> </span><span class="p" id="mwA0g">(</span><span class="nf" id="mwA0k">g</span><span class="w" id="mwA0o"> </span><span class="nv" id="mwA0s">x</span><span class="p" id="mwA0w">)))))</span><span class="w" id="mwA00"> </span><span class="c1" id="mwA04">;; that same g being defined, g = f (λx. g x)</span> <span class="w" id="mwA08"> </span><span class="nv" id="mwA1A">g</span><span class="p" id="mwA1E">)))</span><span class="w" id="mwA1I"> </span><span class="c1" id="mwA1M">;; ((Y* f) ...) = (g ...) = ((f (λx. g x)) ...)</span>

Or without the internal label:

<span id="mwA1c"></span><span class="p" id="mwA1g">(</span><span class="k" id="mwA1k">define</span><span class="w" id="mwA1o"> </span><span class="nv" id="mwA1s">Y*</span> <span class="w" id="mwA1w"> </span><span class="p" id="mwA10">(</span><span class="k" id="mwA14">lambda</span><span class="w" id="mwA18"> </span><span class="p" id="mwA2A">(</span><span class="nf" id="mwA2E">f</span><span class="p" id="mwA2I">)</span> <span class="w" id="mwA2M"> </span><span class="p" id="mwA2Q">((</span><span class="k" id="mwA2U">lambda</span><span class="w" id="mwA2Y"> </span><span class="p" id="mwA2c">(</span><span class="nf" id="mwA2g">i</span><span class="p" id="mwA2k">)</span><span class="w" id="mwA2o"> </span><span class="p" id="mwA2s">(</span><span class="nf" id="mwA2w">i</span><span class="w" id="mwA20"> </span><span class="nv" id="mwA24">i</span><span class="p" id="mwA28">))</span> <span class="w" id="mwA3A"> </span><span class="p" id="mwA3E">(</span><span class="k" id="mwA3I">lambda</span><span class="w" id="mwA3M"> </span><span class="p" id="mwA3Q">(</span><span class="nf" id="mwA3U">i</span><span class="p" id="mwA3Y">)</span> <span class="w" id="mwA3c"> </span><span class="p" id="mwA3g">(</span><span class="nf" id="mwA3k">f</span><span class="w" id="mwA3o"> </span><span class="p" id="mwA3s">(</span><span class="k" id="mwA3w">lambda</span><span class="w" id="mwA30"> </span><span class="nv" id="mwA34">x</span> <span class="w" id="mwA38"> </span><span class="p" id="mwA4A">(</span><span class="nb" id="mwA4E">apply</span><span class="w" id="mwA4I"> </span><span class="p" id="mwA4M">(</span><span class="nf" id="mwA4Q">i</span><span class="w" id="mwA4U"> </span><span class="nv" id="mwA4Y">i</span><span class="p" id="mwA4c">)</span><span class="w" id="mwA4g"> </span><span class="nv" id="mwA4k">x</span><span class="p" id="mwA4o">)))))))</span>

Imperative language implementation

This example is a slightly interpretive implementation of a fixed-point combinator. A class is used to contain the fix() function, called FixedPointCombinator, using CRTP. The function to be fixed is contained in a class that inherits from fixer. The fix() function accesses the function to be fixed using a concept to call apply(). As for the strict functional definition, fix() is explicitly given an extra parameter x, which means that lazy evaluation is not needed.

<span id="mwA5c"></span><span class="k" id="mwA5g">using</span><span class="w" id="mwA5k"> </span><span class="n" id="mwA5o">std</span><span class="o" id="mwA5s">::</span><span class="n" id="mwA5w">same_as</span><span class="p" id="mwA50">;</span> <span class="k" id="mwA54">template</span><span class="w" id="mwA58"> </span><span class="o" id="mwA6A"><</span><span class="k" id="mwA6E">typename</span><span class="w" id="mwA6I"> </span><span class="nc" id="mwA6M">R</span><span class="p" id="mwA6Q">,</span><span class="w" id="mwA6U"> </span><span class="k" id="mwA6Y">typename</span><span class="w" id="mwA6c"> </span><span class="nc" id="mwA6g">T</span><span class="p" id="mwA6k">,</span><span class="w" id="mwA6o"> </span><span class="k" id="mwA6s">typename</span><span class="w" id="mwA6w"> </span><span class="nc" id="mwA60">Self</span><span class="o" id="mwA64">></span> <span class="k" id="mwA68">concept</span><span class="w" id="mwA7A"> </span><span class="nc" id="mwA7E">FixedPointApplicable</span><span class="w" id="mwA7I"> </span><span class="o" id="mwA7M">=</span><span class="w" id="mwA7Q"> </span><span class="k" id="mwA7U">requires</span><span class="w" id="mwA7Y"> </span><span class="p" id="mwA7c">(</span><span class="n" id="mwA7g">T</span><span class="w" id="mwA7k"> </span><span class="n" id="mwA7o">x</span><span class="p" id="mwA7s">)</span><span class="w" id="mwA7w"> </span><span class="p" id="mwA70">{</span> <span class="w" id="mwA74"> </span><span class="p" id="mwA78">{</span><span class="w" id="mwA8A"> </span><span class="n" id="mwA8E">Self</span><span class="o" id="mwA8I">::</span><span class="n" id="mwA8M">apply</span><span class="p" id="mwA8Q">(</span><span class="n" id="mwA8U">x</span><span class="p" id="mwA8Y">)</span><span class="w" id="mwA8c"> </span><span class="p" id="mwA8g">}</span><span class="w" id="mwA8k"> </span><span class="o" id="mwA8o">-></span><span class="w" id="mwA8s"> </span><span class="n" id="mwA8w">same_as</span><span class="o" id="mwA80"><</span><span class="n" id="mwA84">R</span><span class="o" id="mwA88">></span><span class="p" id="mwA9A">;</span> <span class="p" id="mwA9E">};</span> <span class="k" id="mwA9I">template</span><span class="w" id="mwA9M"> </span><span class="o" id="mwA9Q"><</span><span class="k" id="mwA9U">typename</span><span class="w" id="mwA9Y"> </span><span class="nc" id="mwA9c">R</span><span class="p" id="mwA9g">,</span><span class="w" id="mwA9k"> </span><span class="k" id="mwA9o">typename</span><span class="w" id="mwA9s"> </span><span class="nc" id="mwA9w">T</span><span class="p" id="mwA90">,</span><span class="w" id="mwA94"> </span><span class="n" id="mwA98">FixedPointApplicable</span><span class="o" id="mwA-A"><</span><span class="n" id="mwA-E">R</span><span class="p" id="mwA-I">,</span><span class="w" id="mwA-M"> </span><span class="n" id="mwA-Q">T</span><span class="o" id="mwA-U">></span><span class="w" id="mwA-Y"> </span><span class="n" id="mwA-c">Self</span><span class="o" id="mwA-g">></span> <span class="k" id="mwA-k">class</span><span class="w" id="mwA-o"> </span><span class="nc" id="mwA-s">FixedPointCombinator</span><span class="w" id="mwA-w"> </span><span class="p" id="mwA-0">{</span> <span class="k" id="mwA-4">protected</span><span class="o" id="mwA-8">:</span> <span class="w" id="mwA_A"> </span><span class="n" id="mwA_E">FixedPointCombinator</span><span class="p" id="mwA_I">()</span><span class="w" id="mwA_M"> </span><span class="o" id="mwA_Q">=</span><span class="w" id="mwA_U"> </span><span class="k" id="mwA_Y">default</span><span class="p" id="mwA_c">;</span> <span class="k" id="mwA_g">public</span><span class="o" id="mwA_k">:</span> <span class="w" id="mwA_o"> </span><span class="k" id="mwA_s">static</span><span class="w" id="mwA_w"> </span><span class="n" id="mwA_0">R</span><span class="w" id="mwA_4"> </span><span class="n" id="mwA_8">fix</span><span class="p" id="mwBAA">(</span><span class="n" id="mwBAE">T</span><span class="w" id="mwBAI"> </span><span class="n" id="mwBAM">x</span><span class="p" id="mwBAQ">)</span><span class="w" id="mwBAU"> </span><span class="k" id="mwBAY">noexcept</span><span class="w" id="mwBAc"> </span><span class="p" id="mwBAg">{</span> <span class="w" id="mwBAk"> </span><span class="k" id="mwBAo">return</span><span class="w" id="mwBAs"> </span><span class="n" id="mwBAw">Self</span><span class="o" id="mwBA0">::</span><span class="n" id="mwBA4">apply</span><span class="p" id="mwBA8">(</span><span class="n" id="mwBBA">x</span><span class="p" id="mwBBE">);</span> <span class="w" id="mwBBI"> </span><span class="p" id="mwBBM">}</span> <span class="p" id="mwBBQ">};</span> <span class="k" id="mwBBU">class</span><span class="w" id="mwBBY"> </span><span class="nc" id="mwBBc">Factorial</span><span class="w" id="mwBBg"> </span><span class="o" id="mwBBk">:</span><span class="w" id="mwBBo"> </span><span class="k" id="mwBBs">public</span><span class="w" id="mwBBw"> </span><span class="n" id="mwBB0">FixedPointCombinator</span><span class="o" id="mwBB4"><</span><span class="kt" id="mwBB8">long</span><span class="p" id="mwBCA">,</span><span class="w" id="mwBCE"> </span><span class="kt" id="mwBCI">long</span><span class="p" id="mwBCM">,</span><span class="w" id="mwBCQ"> </span><span class="n" id="mwBCU">Factorial</span><span class="o" id="mwBCY">></span><span class="w" id="mwBCc"> </span><span class="p" id="mwBCg">{</span> <span class="k" id="mwBCk">private</span><span class="o" id="mwBCo">:</span> <span class="w" id="mwBCs"> </span><span class="n" id="mwBCw">Factorial</span><span class="p" id="mwBC0">()</span><span class="w" id="mwBC4"> </span><span class="o" id="mwBC8">=</span><span class="w" id="mwBDA"> </span><span class="k" id="mwBDE">default</span><span class="p" id="mwBDI">;</span> <span class="k" id="mwBDM">public</span><span class="o" id="mwBDQ">:</span> <span class="w" id="mwBDU"> </span><span class="k" id="mwBDY">static</span><span class="w" id="mwBDc"> </span><span class="kt" id="mwBDg">long</span><span class="w" id="mwBDk"> </span><span class="n" id="mwBDo">apply</span><span class="p" id="mwBDs">(</span><span class="kt" id="mwBDw">long</span><span class="w" id="mwBD0"> </span><span class="n" id="mwBD4">x</span><span class="p" id="mwBD8">)</span><span class="w" id="mwBEA"> </span><span class="k" id="mwBEE">noexcept</span><span class="w" id="mwBEI"> </span><span class="p" id="mwBEM">{</span> <span class="w" id="mwBEQ"> </span><span class="k" id="mwBEU">if</span><span class="w" id="mwBEY"> </span><span class="p" id="mwBEc">(</span><span class="n" id="mwBEg">x</span><span class="w" id="mwBEk"> </span><span class="o" id="mwBEo">==</span><span class="w" id="mwBEs"> </span><span class="mi" id="mwBEw">0</span><span class="p" id="mwBE0">)</span><span class="w" id="mwBE4"> </span><span class="p" id="mwBE8">{</span> <span class="w" id="mwBFA"> </span><span class="k" id="mwBFE">return</span><span class="w" id="mwBFI"> </span><span class="mi" id="mwBFM">1</span><span class="p" id="mwBFQ">;</span> <span class="w" id="mwBFU"> </span><span class="p" id="mwBFY">}</span> <span class="w" id="mwBFc"> </span><span class="k" id="mwBFg">return</span><span class="w" id="mwBFk"> </span><span class="n" id="mwBFo">x</span><span class="w" id="mwBFs"> </span><span class="o" id="mwBFw">*</span><span class="w" id="mwBF0"> </span><span class="n" id="mwBF4">fix</span><span class="p" id="mwBF8">(</span><span class="n" id="mwBGA">x</span><span class="w" id="mwBGE"> </span><span class="o" id="mwBGI">-</span><span class="w" id="mwBGM"> </span><span class="mi" id="mwBGQ">1</span><span class="p" id="mwBGU">);</span> <span class="w" id="mwBGY"> </span><span class="p" id="mwBGc">}</span> <span class="p" id="mwBGg">};</span> <span class="kt" id="mwBGk">long</span><span class="w" id="mwBGo"> </span><span class="n" id="mwBGs">result</span><span class="w" id="mwBGw"> </span><span class="o" id="mwBG0">=</span><span class="w" id="mwBG4"> </span><span class="n" id="mwBG8">Factorial</span><span class="o" id="mwBHA">::</span><span class="n" id="mwBHE">fix</span><span class="p" id="mwBHI">(</span><span class="mi" id="mwBHM">5</span><span class="p" id="mwBHQ">);</span>

Using only lambdas, one can create a fixed-point combinator like so:

<span id="mwBHg"></span><span class="k" id="mwBHk">auto</span><span class="w" id="mwBHo"> </span><span class="n" id="mwBHs">fix</span><span class="w" id="mwBHw"> </span><span class="o" id="mwBH0">=</span><span class="w" id="mwBH4"> </span><span class="p" id="mwBH8">[](</span><span class="k" id="mwBIA">auto</span><span class="w" id="mwBIE"> </span><span class="n" id="mwBII">f</span><span class="p" id="mwBIM">)</span><span class="w" id="mwBIQ"> </span><span class="p" id="mwBIU">{</span> <span class="w" id="mwBIY"> </span><span class="k" id="mwBIc">return</span><span class="w" id="mwBIg"> </span><span class="p" id="mwBIk">[</span><span class="n" id="mwBIo">f</span><span class="p" id="mwBIs">](</span><span class="k" id="mwBIw">auto</span><span class="o" id="mwBI0">&&</span><span class="p" id="mwBI4">...</span><span class="w" id="mwBI8"> </span><span class="n" id="mwBJA">args</span><span class="p" id="mwBJE">)</span><span class="w" id="mwBJI"> </span><span class="o" id="mwBJM">-></span><span class="w" id="mwBJQ"> </span><span class="k" id="mwBJU">decltype</span><span class="p" id="mwBJY">(</span><span class="k" id="mwBJc">auto</span><span class="p" id="mwBJg">)</span><span class="w" id="mwBJk"> </span><span class="p" id="mwBJo">{</span> <span class="w" id="mwBJs"> </span><span class="k" id="mwBJw">return</span><span class="w" id="mwBJ0"> </span><span class="n" id="mwBJ4">f</span><span class="p" id="mwBJ8">(</span><span class="n" id="mwBKA">f</span><span class="p" id="mwBKE">,</span><span class="w" id="mwBKI"> </span><span class="n" id="mwBKM">std</span><span class="o" id="mwBKQ">::</span><span class="n" id="mwBKU">forward</span><span class="o" id="mwBKY"><</span><span class="k" id="mwBKc">decltype</span><span class="p" id="mwBKg">(</span><span class="n" id="mwBKk">args</span><span class="p" id="mwBKo">)</span><span class="o" id="mwBKs">></span><span class="p" id="mwBKw">(</span><span class="n" id="mwBK0">args</span><span class="p" id="mwBK4">)...);</span> <span class="w" id="mwBK8"> </span><span class="p" id="mwBLA">};</span> <span class="p" id="mwBLE">};</span> <span class="k" id="mwBLI">auto</span><span class="w" id="mwBLM"> </span><span class="n" id="mwBLQ">factorial</span><span class="w" id="mwBLU"> </span><span class="o" id="mwBLY">=</span><span class="w" id="mwBLc"> </span><span class="n" id="mwBLg">fix</span><span class="p" id="mwBLk">([](</span><span class="k" id="mwBLo">auto</span><span class="w" id="mwBLs"> </span><span class="n" id="mwBLw">self</span><span class="p" id="mwBL0">,</span><span class="w" id="mwBL4"> </span><span class="kt" id="mwBL8">long</span><span class="w" id="mwBMA"> </span><span class="n" id="mwBME">n</span><span class="p" id="mwBMI">)</span><span class="w" id="mwBMM"> </span><span class="o" id="mwBMQ">-></span><span class="w" id="mwBMU"> </span><span class="kt" id="mwBMY">long</span><span class="w" id="mwBMc"> </span><span class="p" id="mwBMg">{</span> <span class="w" id="mwBMk"> </span><span class="k" id="mwBMo">return</span><span class="w" id="mwBMs"> </span><span class="n" id="mwBMw">n</span><span class="w" id="mwBM0"> </span><span class="o" id="mwBM4">==</span><span class="w" id="mwBM8"> </span><span class="mi" id="mwBNA">0</span><span class="w" id="mwBNE"> </span><span class="o" id="mwBNI">?</span><span class="w" id="mwBNM"> </span><span class="mi" id="mwBNQ">1</span><span class="w" id="mwBNU"> </span><span class="o" id="mwBNY">:</span><span class="w" id="mwBNc"> </span><span class="n" id="mwBNg">n</span><span class="w" id="mwBNk"> </span><span class="o" id="mwBNo">*</span><span class="w" id="mwBNs"> </span><span class="n" id="mwBNw">self</span><span class="p" id="mwBN0">(</span><span class="n" id="mwBN4">self</span><span class="p" id="mwBN8">,</span><span class="w" id="mwBOA"> </span><span class="n" id="mwBOE">n</span><span class="w" id="mwBOI"> </span><span class="o" id="mwBOM">-</span><span class="w" id="mwBOQ"> </span><span class="mi" id="mwBOU">1</span><span class="p" id="mwBOY">);</span> <span class="p" id="mwBOc">});</span> <span class="n" id="mwBOg">std</span><span class="o" id="mwBOk">::</span><span class="n" id="mwBOo">println</span><span class="p" id="mwBOs">(</span><span class="s" id="mwBOw">"5! = {}"</span><span class="p" id="mwBO0">,</span><span class="w" id="mwBO4"> </span><span class="n" id="mwBO8">factorial</span><span class="p" id="mwBPA">(</span><span class="mi" id="mwBPE">5</span><span class="p" id="mwBPI">));</span><span class="w" id="mwBPM"> </span><span class="c1" id="mwBPQ">// prints 120</span>

Another example can be shown to demonstrate SKI combinator calculus (with given bird name from combinatory logic) being used to build up Z combinator to achieve tail call-like behavior through trampolining:

<span id="mwBPs"></span><span class="c1" id="mwBPw">// Combinators</span> <span class="kd" id="mwBP0">const</span><span class="w" id="mwBP4"> </span><span class="nx" id="mwBP8">K</span><span class="w" id="mwBQA"> </span><span class="o" id="mwBQE">=</span><span class="w" id="mwBQI"> </span><span class="o" id="mwBQM"><</span><span class="nx" id="mwBQQ">A</span><span class="p" id="mwBQU">,</span><span class="w" id="mwBQY"> </span><span class="nx" id="mwBQc">B</span><span class="o" id="mwBQg">></span><span class="p" id="mwBQk">(</span><span class="nx" id="mwBQo">a</span><span class="o" id="mwBQs">:</span><span class="w" id="mwBQw"> </span><span class="kt" id="mwBQ0">A</span><span class="p" id="mwBQ4">)</span><span class="w" id="mwBQ8"> </span><span class="p" id="mwBRA">=></span><span class="w" id="mwBRE"> </span><span class="p" id="mwBRI">(</span><span class="nx" id="mwBRM">_b</span><span class="o" id="mwBRQ">:</span><span class="w" id="mwBRU"> </span><span class="kt" id="mwBRY">B</span><span class="p" id="mwBRc">)</span><span class="w" id="mwBRg"> </span><span class="p" id="mwBRk">=></span><span class="w" id="mwBRo"> </span><span class="nx" id="mwBRs">a</span><span class="p" id="mwBRw">;</span><span class="w" id="mwBR0"> </span><span class="c1" id="mwBR4">// Kestrel</span> <span class="kd" id="mwBR8">const</span><span class="w" id="mwBSA"> </span><span class="nx" id="mwBSE">S</span><span class="w" id="mwBSI"> </span><span class="o" id="mwBSM">=</span><span class="w" id="mwBSQ"> </span><span class="o" id="mwBSU"><</span><span class="nx" id="mwBSY">A</span><span class="p" id="mwBSc">,</span><span class="w" id="mwBSg"> </span><span class="nx" id="mwBSk">B</span><span class="p" id="mwBSo">,</span><span class="w" id="mwBSs"> </span><span class="nx" id="mwBSw">C</span><span class="o" id="mwBS0">></span><span class="p" id="mwBS4">(</span><span class="nx" id="mwBS8">a</span><span class="o" id="mwBTA">:</span><span class="w" id="mwBTE"> </span><span class="p" id="mwBTI">(</span><span class="nx" id="mwBTM">x</span><span class="o" id="mwBTQ">:</span><span class="w" id="mwBTU"> </span><span class="kt" id="mwBTY">C</span><span class="p" id="mwBTc">)</span><span class="w" id="mwBTg"> </span><span class="p" id="mwBTk">=></span><span class="w" id="mwBTo"> </span><span class="p" id="mwBTs">(</span><span class="nx" id="mwBTw">y</span><span class="o" id="mwBT0">:</span><span class="w" id="mwBT4"> </span><span class="kt" id="mwBT8">B</span><span class="p" id="mwBUA">)</span><span class="w" id="mwBUE"> </span><span class="p" id="mwBUI">=></span><span class="w" id="mwBUM"> </span><span class="nx" id="mwBUQ">A</span><span class="p" id="mwBUU">)</span><span class="w" id="mwBUY"> </span><span class="p" id="mwBUc">=></span><span class="w" id="mwBUg"> </span><span class="p" id="mwBUk">(</span><span class="nx" id="mwBUo">b</span><span class="o" id="mwBUs">:</span><span class="w" id="mwBUw"> </span><span class="p" id="mwBU0">(</span><span class="nx" id="mwBU4">x</span><span class="o" id="mwBU8">:</span><span class="w" id="mwBVA"> </span><span class="kt" id="mwBVE">C</span><span class="p" id="mwBVI">)</span><span class="w" id="mwBVM"> </span><span class="p" id="mwBVQ">=></span><span class="w" id="mwBVU"> </span><span class="nx" id="mwBVY">B</span><span class="p" id="mwBVc">)</span><span class="w" id="mwBVg"> </span><span class="p" id="mwBVk">=></span><span class="w" id="mwBVo"> </span><span class="p" id="mwBVs">(</span><span class="nx" id="mwBVw">c</span><span class="o" id="mwBV0">:</span><span class="w" id="mwBV4"> </span><span class="kt" id="mwBV8">C</span><span class="p" id="mwBWA">)</span><span class="w" id="mwBWE"> </span><span class="p" id="mwBWI">=></span><span class="w" id="mwBWM"> </span><span class="nx" id="mwBWQ">a</span><span class="p" id="mwBWU">(</span><span class="nx" id="mwBWY">c</span><span class="p" id="mwBWc">)(</span><span class="nx" id="mwBWg">b</span><span class="p" id="mwBWk">(</span><span class="nx" id="mwBWo">c</span><span class="p" id="mwBWs">));</span><span class="w" id="mwBWw"> </span><span class="c1" id="mwBW0">// Starling</span> <span class="c1" id="mwBW4">// Derived combinators</span> <span class="kd" id="mwBW8">const</span><span class="w" id="mwBXA"> </span><span class="nx" id="mwBXE">I</span><span class="w" id="mwBXI"> </span><span class="o" id="mwBXM">=</span><span class="w" id="mwBXQ"> </span><span class="nx" id="mwBXU">S</span><span class="p" id="mwBXY">(</span><span class="nx" id="mwBXc">K</span><span class="p" id="mwBXg">)(</span><span class="nx" id="mwBXk">K</span><span class="p" id="mwBXo">);</span><span class="w" id="mwBXs"> </span><span class="c1" id="mwBXw">// Identity</span> <span class="kd" id="mwBX0">const</span><span class="w" id="mwBX4"> </span><span class="nx" id="mwBX8">B</span><span class="w" id="mwBYA"> </span><span class="o" id="mwBYE">=</span><span class="w" id="mwBYI"> </span><span class="nx" id="mwBYM">S</span><span class="p" id="mwBYQ">(</span><span class="nx" id="mwBYU">K</span><span class="p" id="mwBYY">(</span><span class="nx" id="mwBYc">S</span><span class="p" id="mwBYg">))(</span><span class="nx" id="mwBYk">K</span><span class="p" id="mwBYo">);</span><span class="w" id="mwBYs"> </span><span class="c1" id="mwBYw">// Bluebird</span> <span class="kd" id="mwBY0">const</span><span class="w" id="mwBY4"> </span><span class="nx" id="mwBY8">C</span><span class="w" id="mwBZA"> </span><span class="o" id="mwBZE">=</span><span class="w" id="mwBZI"> </span><span class="nx" id="mwBZM">S</span><span class="p" id="mwBZQ">(</span><span class="nx" id="mwBZU">B</span><span class="p" id="mwBZY">(</span><span class="nx" id="mwBZc">B</span><span class="p" id="mwBZg">)(</span><span class="nx" id="mwBZk">S</span><span class="p" id="mwBZo">))(</span><span class="nx" id="mwBZs">K</span><span class="p" id="mwBZw">(</span><span class="nx" id="mwBZ0">K</span><span class="p" id="mwBZ4">));</span><span class="w" id="mwBZ8"> </span><span class="c1" id="mwBaA">// Cardinal</span> <span class="kd" id="mwBaE">const</span><span class="w" id="mwBaI"> </span><span class="nx" id="mwBaM">W</span><span class="w" id="mwBaQ"> </span><span class="o" id="mwBaU">=</span><span class="w" id="mwBaY"> </span><span class="nx" id="mwBac">C</span><span class="p" id="mwBag">(</span><span class="nx" id="mwBak">S</span><span class="p" id="mwBao">)(</span><span class="nx" id="mwBas">I</span><span class="p" id="mwBaw">);</span><span class="w" id="mwBa0"> </span><span class="c1" id="mwBa4">// Warbler</span> <span class="kd" id="mwBa8">const</span><span class="w" id="mwBbA"> </span><span class="nx" id="mwBbE">T</span><span class="w" id="mwBbI"> </span><span class="o" id="mwBbM">=</span><span class="w" id="mwBbQ"> </span><span class="nx" id="mwBbU">C</span><span class="p" id="mwBbY">(</span><span class="nx" id="mwBbc">I</span><span class="p" id="mwBbg">);</span><span class="w" id="mwBbk"> </span><span class="c1" id="mwBbo">// Thrush</span> <span class="kd" id="mwBbs">const</span><span class="w" id="mwBbw"> </span><span class="nx" id="mwBb0">V</span><span class="w" id="mwBb4"> </span><span class="o" id="mwBb8">=</span><span class="w" id="mwBcA"> </span><span class="nx" id="mwBcE">B</span><span class="p" id="mwBcI">(</span><span class="nx" id="mwBcM">C</span><span class="p" id="mwBcQ">)(</span><span class="nx" id="mwBcU">T</span><span class="p" id="mwBcY">);</span><span class="w" id="mwBcc"> </span><span class="c1" id="mwBcg">// Vireo</span> <span class="kd" id="mwBck">const</span><span class="w" id="mwBco"> </span><span class="nx" id="mwBcs">I1</span><span class="w" id="mwBcw"> </span><span class="o" id="mwBc0">=</span><span class="w" id="mwBc4"> </span><span class="nx" id="mwBc8">C</span><span class="p" id="mwBdA">(</span><span class="nx" id="mwBdE">C</span><span class="p" id="mwBdI">(</span><span class="nx" id="mwBdM">I</span><span class="p" id="mwBdQ">));</span><span class="w" id="mwBdU"> </span><span class="c1" id="mwBdY">// Identity Bird Once Removed; same as C(B(B)(I))(I)</span> <span class="kd" id="mwBdc">const</span><span class="w" id="mwBdg"> </span><span class="nx" id="mwBdk">C1</span><span class="w" id="mwBdo"> </span><span class="o" id="mwBds">=</span><span class="w" id="mwBdw"> </span><span class="nx" id="mwBd0">B</span><span class="p" id="mwBd4">(</span><span class="nx" id="mwBd8">C</span><span class="p" id="mwBeA">);</span><span class="w" id="mwBeE"> </span><span class="c1" id="mwBeI">// Cardinal Once Removed</span> <span class="kd" id="mwBeM">const</span><span class="w" id="mwBeQ"> </span><span class="nx" id="mwBeU">R1</span><span class="w" id="mwBeY"> </span><span class="o" id="mwBec">=</span><span class="w" id="mwBeg"> </span><span class="nx" id="mwBek">C1</span><span class="p" id="mwBeo">(</span><span class="nx" id="mwBes">C1</span><span class="p" id="mwBew">);</span><span class="w" id="mwBe0"> </span><span class="c1" id="mwBe4">// Robin Once Removed</span> <span class="kd" id="mwBe8">const</span><span class="w" id="mwBfA"> </span><span class="nx" id="mwBfE">V1</span><span class="w" id="mwBfI"> </span><span class="o" id="mwBfM">=</span><span class="w" id="mwBfQ"> </span><span class="nx" id="mwBfU">B</span><span class="p" id="mwBfY">(</span><span class="nx" id="mwBfc">R1</span><span class="p" id="mwBfg">)(</span><span class="nx" id="mwBfk">C1</span><span class="p" id="mwBfo">);</span><span class="w" id="mwBfs"> </span><span class="c1" id="mwBfw">// Vireo Once Removed</span> <span class="kd" id="mwBf0">const</span><span class="w" id="mwBf4"> </span><span class="nx" id="mwBf8">I2</span><span class="w" id="mwBgA"> </span><span class="o" id="mwBgE">=</span><span class="w" id="mwBgI"> </span><span class="nx" id="mwBgM">R1</span><span class="p" id="mwBgQ">(</span><span class="nx" id="mwBgU">V</span><span class="p" id="mwBgY">);</span><span class="w" id="mwBgc"> </span><span class="c1" id="mwBgg">// Identity Bird Twice Removed</span> <span class="c1" id="mwBgk">// Z combinators</span> <span class="kd" id="mwBgo">const</span><span class="w" id="mwBgs"> </span><span class="nx" id="mwBgw">Z</span><span class="w" id="mwBg0"> </span><span class="o" id="mwBg4">=</span><span class="w" id="mwBg8"> </span><span class="nx" id="mwBhA">B</span><span class="p" id="mwBhE">(</span><span class="nx" id="mwBhI">W</span><span class="p" id="mwBhM">(</span><span class="nx" id="mwBhQ">I1</span><span class="p" id="mwBhU">))(</span><span class="nx" id="mwBhY">V1</span><span class="p" id="mwBhc">(</span><span class="nx" id="mwBhg">B</span><span class="p" id="mwBhk">)(</span><span class="nx" id="mwBho">W</span><span class="p" id="mwBhs">(</span><span class="nx" id="mwBhw">I2</span><span class="p" id="mwBh0">)));</span> <span class="kd" id="mwBh4">const</span><span class="w" id="mwBh8"> </span><span class="nx" id="mwBiA">Z2</span><span class="w" id="mwBiE"> </span><span class="o" id="mwBiI">=</span><span class="w" id="mwBiM"> </span><span class="nx" id="mwBiQ">S</span><span class="p" id="mwBiU">(</span><span class="nx" id="mwBiY">K</span><span class="p" id="mwBic">(</span><span class="nx" id="mwBig">S</span><span class="p" id="mwBik">(</span><span class="nx" id="mwBio">S</span><span class="p" id="mwBis">(</span><span class="nx" id="mwBiw">K</span><span class="p" id="mwBi0">(</span><span class="nx" id="mwBi4">S</span><span class="p" id="mwBi8">(</span><span class="nx" id="mwBjA">S</span><span class="p" id="mwBjE">(</span><span class="nx" id="mwBjI">K</span><span class="p" id="mwBjM">)(</span><span class="nx" id="mwBjQ">K</span><span class="p" id="mwBjU">))(</span><span class="nx" id="mwBjY">S</span><span class="p" id="mwBjc">(</span><span class="nx" id="mwBjg">K</span><span class="p" id="mwBjk">)(</span><span class="nx" id="mwBjo">K</span><span class="p" id="mwBjs">))))(</span><span class="nx" id="mwBjw">S</span><span class="p" id="mwBj0">(</span><span class="nx" id="mwBj4">K</span><span class="p" id="mwBj8">(</span><span class="nx" id="mwBkA">S</span><span class="p" id="mwBkE">(</span><span class="nx" id="mwBkI">K</span><span class="p" id="mwBkM">(</span><span class="nx" id="mwBkQ">S</span><span class="p" id="mwBkU">))(</span><span class="nx" id="mwBkY">K</span><span class="p" id="mwBkc">)))(</span><span class="nx" id="mwBkg">S</span><span class="p" id="mwBkk">(</span><span class="nx" id="mwBko">K</span><span class="p" id="mwBks">(</span><span class="nx" id="mwBkw">S</span><span class="p" id="mwBk0">(</span><span class="nx" id="mwBk4">S</span><span class="p" id="mwBk8">(</span><span class="nx" id="mwBlA">K</span><span class="p" id="mwBlE">)(</span><span class="nx" id="mwBlI">K</span><span class="p" id="mwBlM">))))(</span><span class="nx" id="mwBlQ">K</span><span class="p" id="mwBlU">))))(</span><span class="nx" id="mwBlY">K</span><span class="p" id="mwBlc">(</span><span class="nx" id="mwBlg">S</span><span class="p" id="mwBlk">(</span><span class="nx" id="mwBlo">S</span><span class="p" id="mwBls">(</span><span class="nx" id="mwBlw">K</span><span class="p" id="mwBl0">))))))(</span><span class="nx" id="mwBl4">S</span><span class="p" id="mwBl8">(</span><span class="nx" id="mwBmA">S</span><span class="p" id="mwBmE">(</span><span class="nx" id="mwBmI">K</span><span class="p" id="mwBmM">(</span><span class="nx" id="mwBmQ">S</span><span class="p" id="mwBmU">(</span><span class="nx" id="mwBmY">S</span><span class="p" id="mwBmc">(</span><span class="nx" id="mwBmg">K</span><span class="p" id="mwBmk">(</span><span class="nx" id="mwBmo">S</span><span class="p" id="mwBms">(</span><span class="nx" id="mwBmw">K</span><span class="p" id="mwBm0">(</span><span class="nx" id="mwBm4">S</span><span class="p" id="mwBm8">))(</span><span class="nx" id="mwBnA">K</span><span class="p" id="mwBnE">)))(</span><span class="nx" id="mwBnI">S</span><span class="p" id="mwBnM">))(</span><span class="nx" id="mwBnQ">K</span><span class="p" id="mwBnU">(</span><span class="nx" id="mwBnY">K</span><span class="p" id="mwBnc">))))(</span><span class="nx" id="mwBng">S</span><span class="p" id="mwBnk">(</span><span class="nx" id="mwBno">K</span><span class="p" id="mwBns">(</span><span class="nx" id="mwBnw">S</span><span class="p" id="mwBn0">(</span><span class="nx" id="mwBn4">S</span><span class="p" id="mwBn8">(</span><span class="nx" id="mwBoA">K</span><span class="p" id="mwBoE">(</span><span class="nx" id="mwBoI">S</span><span class="p" id="mwBoM">(</span><span class="nx" id="mwBoQ">K</span><span class="p" id="mwBoU">(</span><span class="nx" id="mwBoY">S</span><span class="p" id="mwBoc">))(</span><span class="nx" id="mwBog">K</span><span class="p" id="mwBok">)))(</span><span class="nx" id="mwBoo">S</span><span class="p" id="mwBos">))(</span><span class="nx" id="mwBow">K</span><span class="p" id="mwBo0">(</span><span class="nx" id="mwBo4">K</span><span class="p" id="mwBo8">))))(</span><span class="nx" id="mwBpA">S</span><span class="p" id="mwBpE">(</span><span class="nx" id="mwBpI">K</span><span class="p" id="mwBpM">(</span><span class="nx" id="mwBpQ">S</span><span class="p" id="mwBpU">))(</span><span class="nx" id="mwBpY">K</span><span class="p" id="mwBpc">))))(</span><span class="nx" id="mwBpg">K</span><span class="p" id="mwBpk">(</span><span class="nx" id="mwBpo">S</span><span class="p" id="mwBps">(</span><span class="nx" id="mwBpw">S</span><span class="p" id="mwBp0">(</span><span class="nx" id="mwBp4">K</span><span class="p" id="mwBp8">(</span><span class="nx" id="mwBqA">S</span><span class="p" id="mwBqE">(</span><span class="nx" id="mwBqI">S</span><span class="p" id="mwBqM">(</span><span class="nx" id="mwBqQ">K</span><span class="p" id="mwBqU">)(</span><span class="nx" id="mwBqY">K</span><span class="p" id="mwBqc">))(</span><span class="nx" id="mwBqg">S</span><span class="p" id="mwBqk">(</span><span class="nx" id="mwBqo">K</span><span class="p" id="mwBqs">)(</span><span class="nx" id="mwBqw">K</span><span class="p" id="mwBq0">))))(</span><span class="nx" id="mwBq4">S</span><span class="p" id="mwBq8">(</span><span class="nx" id="mwBrA">K</span><span class="p" id="mwBrE">(</span><span class="nx" id="mwBrI">S</span><span class="p" id="mwBrM">(</span><span class="nx" id="mwBrQ">K</span><span class="p" id="mwBrU">(</span><span class="nx" id="mwBrY">S</span><span class="p" id="mwBrc">))(</span><span class="nx" id="mwBrg">K</span><span class="p" id="mwBrk">)))(</span><span class="nx" id="mwBro">S</span><span class="p" id="mwBrs">(</span><span class="nx" id="mwBrw">K</span><span class="p" id="mwBr0">(</span><span class="nx" id="mwBr4">S</span><span class="p" id="mwBr8">(</span><span class="nx" id="mwBsA">S</span><span class="p" id="mwBsE">(</span><span class="nx" id="mwBsI">K</span><span class="p" id="mwBsM">)(</span><span class="nx" id="mwBsQ">K</span><span class="p" id="mwBsU">))))(</span><span class="nx" id="mwBsY">K</span><span class="p" id="mwBsc">))))(</span><span class="nx" id="mwBsg">K</span><span class="p" id="mwBsk">(</span><span class="nx" id="mwBso">S</span><span class="p" id="mwBss">(</span><span class="nx" id="mwBsw">K</span><span class="p" id="mwBs0">(</span><span class="nx" id="mwBs4">S</span><span class="p" id="mwBs8">(</span><span class="nx" id="mwBtA">S</span><span class="p" id="mwBtE">(</span><span class="nx" id="mwBtI">K</span><span class="p" id="mwBtM">(</span><span class="nx" id="mwBtQ">S</span><span class="p" id="mwBtU">(</span><span class="nx" id="mwBtY">S</span><span class="p" id="mwBtc">(</span><span class="nx" id="mwBtg">K</span><span class="p" id="mwBtk">(</span><span class="nx" id="mwBto">S</span><span class="p" id="mwBts">(</span><span class="nx" id="mwBtw">K</span><span class="p" id="mwBt0">(</span><span class="nx" id="mwBt4">S</span><span class="p" id="mwBt8">))(</span><span class="nx" id="mwBuA">K</span><span class="p" id="mwBuE">)))(</span><span class="nx" id="mwBuI">S</span><span class="p" id="mwBuM">))(</span><span class="nx" id="mwBuQ">K</span><span class="p" id="mwBuU">(</span><span class="nx" id="mwBuY">K</span><span class="p" id="mwBuc">))))(</span><span class="nx" id="mwBug">S</span><span class="p" id="mwBuk">(</span><span class="nx" id="mwBuo">K</span><span class="p" id="mwBus">(</span><span class="nx" id="mwBuw">S</span><span class="p" id="mwBu0">(</span><span class="nx" id="mwBu4">S</span><span class="p" id="mwBu8">(</span><span class="nx" id="mwBvA">K</span><span class="p" id="mwBvE">(</span><span class="nx" id="mwBvI">S</span><span class="p" id="mwBvM">(</span><span class="nx" id="mwBvQ">K</span><span class="p" id="mwBvU">(</span><span class="nx" id="mwBvY">S</span><span class="p" id="mwBvc">))(</span><span class="nx" id="mwBvg">K</span><span class="p" id="mwBvk">)))(</span><span class="nx" id="mwBvo">S</span><span class="p" id="mwBvs">))(</span><span class="nx" id="mwBvw">K</span><span class="p" id="mwBv0">(</span><span class="nx" id="mwBv4">K</span><span class="p" id="mwBv8">))))(</span><span class="nx" id="mwBwA">S</span><span class="p" id="mwBwE">(</span><span class="nx" id="mwBwI">K</span><span class="p" id="mwBwM">(</span><span class="nx" id="mwBwQ">S</span><span class="p" id="mwBwU">(</span><span class="nx" id="mwBwY">S</span><span class="p" id="mwBwc">(</span><span class="nx" id="mwBwg">K</span><span class="p" id="mwBwk">)(</span><span class="nx" id="mwBwo">K</span><span class="p" id="mwBws">))))(</span><span class="nx" id="mwBww">K</span><span class="p" id="mwBw0">))))))(</span><span class="nx" id="mwBw4">K</span><span class="p" id="mwBw8">))))));</span> <span class="w" id="mwBxA"> </span><span class="c1" id="mwBxE">// Alternative fully expanded form.</span> <span class="kd" id="mwBxI">const</span><span class="w" id="mwBxM"> </span><span class="nx" id="mwBxQ">Z3</span><span class="w" id="mwBxU"> </span><span class="o" id="mwBxY">=</span><span class="w" id="mwBxc"> </span><span class="nx" id="mwBxg">S</span><span class="p" id="mwBxk">(</span><span class="nx" id="mwBxo">S</span><span class="p" id="mwBxs">(</span><span class="nx" id="mwBxw">K</span><span class="p" id="mwBx0">(</span><span class="nx" id="mwBx4">S</span><span class="p" id="mwBx8">(</span><span class="nx" id="mwByA">S</span><span class="p" id="mwByE">)(</span><span class="nx" id="mwByI">K</span><span class="p" id="mwByM">(</span><span class="nx" id="mwByQ">S</span><span class="p" id="mwByU">(</span><span class="nx" id="mwByY">S</span><span class="p" id="mwByc">(</span><span class="nx" id="mwByg">K</span><span class="p" id="mwByk">)(</span><span class="nx" id="mwByo">K</span><span class="p" id="mwBys">))(</span><span class="nx" id="mwByw">S</span><span class="p" id="mwBy0">(</span><span class="nx" id="mwBy4">K</span><span class="p" id="mwBy8">)(</span><span class="nx" id="mwBzA">K</span><span class="p" id="mwBzE">))))))(</span><span class="nx" id="mwBzI">K</span><span class="p" id="mwBzM">))(</span><span class="nx" id="mwBzQ">S</span><span class="p" id="mwBzU">(</span><span class="nx" id="mwBzY">S</span><span class="p" id="mwBzc">(</span><span class="nx" id="mwBzg">K</span><span class="p" id="mwBzk">(</span><span class="nx" id="mwBzo">S</span><span class="p" id="mwBzs">))(</span><span class="nx" id="mwBzw">K</span><span class="p" id="mwBz0">))(</span><span class="nx" id="mwBz4">K</span><span class="p" id="mwBz8">(</span><span class="nx" id="mwB0A">S</span><span class="p" id="mwB0E">(</span><span class="nx" id="mwB0I">S</span><span class="p" id="mwB0M">(</span><span class="nx" id="mwB0Q">K</span><span class="p" id="mwB0U">(</span><span class="nx" id="mwB0Y">S</span><span class="p" id="mwB0c">))(</span><span class="nx" id="mwB0g">S</span><span class="p" id="mwB0k">(</span><span class="nx" id="mwB0o">K</span><span class="p" id="mwB0s">(</span><span class="nx" id="mwB0w">S</span><span class="p" id="mwB00">(</span><span class="nx" id="mwB04">K</span><span class="p" id="mwB08">(</span><span class="nx" id="mwB1A">S</span><span class="p" id="mwB1E">(</span><span class="nx" id="mwB1I">K</span><span class="p" id="mwB1M">(</span><span class="nx" id="mwB1Q">S</span><span class="p" id="mwB1U">(</span><span class="nx" id="mwB1Y">K</span><span class="p" id="mwB1c">(</span><span class="nx" id="mwB1g">S</span><span class="p" id="mwB1k">(</span><span class="nx" id="mwB1o">S</span><span class="p" id="mwB1s">)(</span><span class="nx" id="mwB1w">K</span><span class="p" id="mwB10">(</span><span class="nx" id="mwB14">K</span><span class="p" id="mwB18">))))(</span><span class="nx" id="mwB2A">K</span><span class="p" id="mwB2E">)))(</span><span class="nx" id="mwB2I">S</span><span class="p" id="mwB2M">)))(</span><span class="nx" id="mwB2Q">S</span><span class="p" id="mwB2U">(</span><span class="nx" id="mwB2Y">S</span><span class="p" id="mwB2c">(</span><span class="nx" id="mwB2g">K</span><span class="p" id="mwB2k">)(</span><span class="nx" id="mwB2o">K</span><span class="p" id="mwB2s">)))))(</span><span class="nx" id="mwB2w">K</span><span class="p" id="mwB20">)))(</span><span class="nx" id="mwB24">K</span><span class="p" id="mwB28">(</span><span class="nx" id="mwB3A">K</span><span class="p" id="mwB3E">(</span><span class="nx" id="mwB3I">S</span><span class="p" id="mwB3M">(</span><span class="nx" id="mwB3Q">S</span><span class="p" id="mwB3U">(</span><span class="nx" id="mwB3Y">K</span><span class="p" id="mwB3c">)(</span><span class="nx" id="mwB3g">K</span><span class="p" id="mwB3k">))(</span><span class="nx" id="mwB3o">S</span><span class="p" id="mwB3s">(</span><span class="nx" id="mwB3w">K</span><span class="p" id="mwB30">)(</span><span class="nx" id="mwB34">K</span><span class="p" id="mwB38">))))))));</span> <span class="w" id="mwB4A"> </span><span class="c1" id="mwB4E">// Another shorter version.</span> <span class="kd" id="mwB4I">const</span><span class="w" id="mwB4M"> </span><span class="nx" id="mwB4Q">trampoline</span><span class="w" id="mwB4U"> </span><span class="o" id="mwB4Y">=</span><span class="w" id="mwB4c"> </span><span class="o" id="mwB4g"><</span><span class="nx" id="mwB4k">T</span><span class="o" id="mwB4o">></span><span class="p" id="mwB4s">(</span><span class="nx" id="mwB4w">fn</span><span class="o" id="mwB40">:</span><span class="w" id="mwB44"> </span><span class="kt" id="mwB48">T</span><span class="w" id="mwB5A"> </span><span class="o" id="mwB5E">|</span><span class="w" id="mwB5I"> </span><span class="p" id="mwB5M">(()</span><span class="w" id="mwB5Q"> </span><span class="p" id="mwB5U">=></span><span class="w" id="mwB5Y"> </span><span class="nx" id="mwB5c">T</span><span class="p" id="mwB5g">))</span><span class="o" id="mwB5k">:</span><span class="w" id="mwB5o"> </span><span class="nx" id="mwB5s">T</span><span class="w" id="mwB5w"> </span><span class="p" id="mwB50">=></span><span class="w" id="mwB54"> </span><span class="p" id="mwB58">{</span> <span class="w" id="mwB6A"> </span><span class="kd" id="mwB6E">let</span><span class="w" id="mwB6I"> </span><span class="nx" id="mwB6M">ctx</span><span class="w" id="mwB6Q"> </span><span class="o" id="mwB6U">=</span><span class="w" id="mwB6Y"> </span><span class="nx" id="mwB6c">fn</span><span class="p" id="mwB6g">;</span> <span class="w" id="mwB6k"> </span><span class="k" id="mwB6o">while</span><span class="w" id="mwB6s"> </span><span class="p" id="mwB6w">(</span><span class="ow" id="mwB60">typeof</span><span class="w" id="mwB64"> </span><span class="nx" id="mwB68">ctx</span><span class="w" id="mwB7A"> </span><span class="o" id="mwB7E">===</span><span class="w" id="mwB7I"> </span><span class="s2" id="mwB7M">"function"</span><span class="p" id="mwB7Q">)</span><span class="w" id="mwB7U"> </span><span class="p" id="mwB7Y">{</span> <span class="w" id="mwB7c"> </span><span class="nx" id="mwB7g">ctx</span><span class="w" id="mwB7k"> </span><span class="o" id="mwB7o">=</span><span class="w" id="mwB7s"> </span><span class="p" id="mwB7w">(</span><span class="nx" id="mwB70">ctx</span><span class="w" id="mwB74"> </span><span class="kr" id="mwB78">as</span><span class="w" id="mwB8A"> </span><span class="p" id="mwB8E">()</span><span class="w" id="mwB8I"> </span><span class="p" id="mwB8M">=></span><span class="w" id="mwB8Q"> </span><span class="nx" id="mwB8U">T</span><span class="p" id="mwB8Y">)();</span> <span class="w" id="mwB8c"> </span><span class="p" id="mwB8g">}</span> <span class="w" id="mwB8k"> </span><span class="k" id="mwB8o">return</span><span class="w" id="mwB8s"> </span><span class="nx" id="mwB8w">ctx</span><span class="p" id="mwB80">;</span> <span class="p" id="mwB84">};</span> <span class="kd" id="mwB88">const</span><span class="w" id="mwB9A"> </span><span class="nx" id="mwB9E">countFn</span><span class="w" id="mwB9I"> </span><span class="o" id="mwB9M">=</span><span class="w" id="mwB9Q"> </span><span class="p" id="mwB9U">(</span><span class="nx" id="mwB9Y">self</span><span class="o" id="mwB9c">:</span><span class="w" id="mwB9g"> </span><span class="p" id="mwB9k">(</span><span class="nx" id="mwB9o">n</span><span class="o" id="mwB9s">:</span><span class="w" id="mwB9w"> </span><span class="kt" id="mwB90">number</span><span class="p" id="mwB94">)</span><span class="w" id="mwB98"> </span><span class="p" id="mwB-A">=></span><span class="w" id="mwB-E"> </span><span class="nx" id="mwB-I">any</span><span class="p" id="mwB-M">)</span><span class="w" id="mwB-Q"> </span><span class="p" id="mwB-U">=></span><span class="w" id="mwB-Y"> </span><span class="p" id="mwB-c">(</span><span class="nx" id="mwB-g">n</span><span class="o" id="mwB-k">:</span><span class="w" id="mwB-o"> </span><span class="kt" id="mwB-s">number</span><span class="p" id="mwB-w">)</span><span class="o" id="mwB-0">:</span><span class="w" id="mwB-4"> </span><span class="nx" id="mwB-8">any</span><span class="w" id="mwB_A"> </span><span class="p" id="mwB_E">=></span> <span class="w" id="mwB_I"> </span><span class="nx" id="mwB_M">n</span><span class="w" id="mwB_Q"> </span><span class="o" id="mwB_U">===</span><span class="w" id="mwB_Y"> </span><span class="mf" id="mwB_c">0</span> <span class="w" id="mwB_g"> </span><span class="o" id="mwB_k">?</span><span class="w" id="mwB_o"> </span><span class="p" id="mwB_s">(</span><span class="nx" id="mwB_w">console</span><span class="p" id="mwB_0">.</span><span class="nx" id="mwB_4">log</span><span class="p" id="mwB_8">(</span><span class="nx" id="mwCAA">n</span><span class="p" id="mwCAE">),</span><span class="w" id="mwCAI"> </span><span class="nx" id="mwCAM">n</span><span class="p" id="mwCAQ">)</span> <span class="w" id="mwCAU"> </span><span class="o" id="mwCAY">:</span><span class="w" id="mwCAc"> </span><span class="p" id="mwCAg">()</span><span class="w" id="mwCAk"> </span><span class="p" id="mwCAo">=></span><span class="w" id="mwCAs"> </span><span class="nx" id="mwCAw">self</span><span class="p" id="mwCA0">(</span><span class="nx" id="mwCA4">n</span><span class="w" id="mwCA8"> </span><span class="o" id="mwCBA">-</span><span class="w" id="mwCBE"> </span><span class="mf" id="mwCBI">1</span><span class="p" id="mwCBM">);</span><span class="w" id="mwCBQ"> </span><span class="c1" id="mwCBU">// Return thunk "() => self(n - 1)" instead.</span> <span class="c1" id="mwCBY">// Examples</span> <span class="nx" id="mwCBc">trampoline</span><span class="p" id="mwCBg">(</span><span class="nx" id="mwCBk">Z</span><span class="p" id="mwCBo">(</span><span class="nx" id="mwCBs">countFn</span><span class="p" id="mwCBw">)(</span><span class="mf" id="mwCB0">10</span><span class="p" id="mwCB4">));</span> <span class="nx" id="mwCB8">trampoline</span><span class="p" id="mwCCA">(</span><span class="nx" id="mwCCE">Z2</span><span class="p" id="mwCCI">(</span><span class="nx" id="mwCCM">countFn</span><span class="p" id="mwCCQ">)(</span><span class="mf" id="mwCCU">10</span><span class="p" id="mwCCY">));</span> <span class="nx" id="mwCCc">trampoline</span><span class="p" id="mwCCg">(</span><span class="nx" id="mwCCk">Z3</span><span class="p" id="mwCCo">(</span><span class="nx" id="mwCCs">countFn</span><span class="p" id="mwCCw">)(</span><span class="mf" id="mwCC0">10</span><span class="p" id="mwCC4">));</span>

Typing

In System F (polymorphic lambda calculus) a polymorphic fixed-point combinator has type

∀a.(a → a) → a

where ${\displaystyle a}$ is a type variable. That is, if the type of ${\displaystyle \mathrm{f}\mathrm{i}\mathrm{x}f}$ fulfilling the equation ${\displaystyle \mathrm{f}\mathrm{i}\mathrm{x}f=f(\mathrm{f}\mathrm{i}\mathrm{x}f)}$ is ${\displaystyle a}$—the most general type—then the type of ${\displaystyle f}$ is ${\displaystyle a\to a}$. So then, ${\displaystyle \mathrm{f}\mathrm{i}\mathrm{x}}$ takes a function that maps ${\displaystyle a}$ to ${\displaystyle a}$ and uses it to return a value of type ${\displaystyle a}$.

In the simply typed lambda calculus extended with recursive data types, fixed-point operators can be written, but the type of a "useful" fixed-point operator (one whose application always returns) may be restricted.

In the simply typed lambda calculus, the fixed-point combinator Y cannot be assigned a type because at some point it would deal with the self-application sub-term ${\displaystyle xx}$ by the application rule:

$\frac{{\displaystyle \mathrm{\Gamma }⊢x:t_1\to t_2\mathrm{\Gamma }⊢x:t_1}}{\mathrm{\Gamma }⊢xx:t_2}$

where ${\displaystyle x}$ has the infinite type ${\displaystyle t_1=t_1\to t_2}$. No fixed-point combinator can in fact be typed; in those systems, any support for recursion must be explicitly added to the language.

Type for the Y combinator

In programming languages that support named recursive data types, the unbounded recursion in ${\displaystyle t:=t\to a}$, which creates the would-be infinite type ${\displaystyle t}$, is broken by naming the type ${\displaystyle t}$ explicitly, as e.g. type ${\displaystyle Ra}$ which is defined so as to be isomorphic to (or just to be a synonym of) the type ${\displaystyle Ra\to a}$. Thus ${\displaystyle Ra:=Ra\to a}$ is recognized as a recursive type. A datum (value) of the type ${\displaystyle Ra}$ is created by simply tagging a value that is a function that has the type ${\displaystyle Ra\to a}$, by the data constructor tag for the type ${\displaystyle Ra}$.

For example, in the following Haskell code, let Rec be that tag name, and thus Rec and app be the names of the two directions of the isomorphism, with types:

<span id="mwCG4"></span><span class="kt" id="mwCG8">Rec</span><span class="w" id="mwCHA"> </span><span class="ow" id="mwCHE">::</span><span class="w" id="mwCHI"> </span><span class="p" id="mwCHM">(</span><span class="kt" id="mwCHQ">R</span><span class="w" id="mwCHU"> </span><span class="n" id="mwCHY">a</span><span class="w" id="mwCHc"> </span><span class="ow" id="mwCHg">-></span><span class="w" id="mwCHk"> </span><span class="n" id="mwCHo">a</span><span class="p" id="mwCHs">)</span><span class="w" id="mwCHw"> </span><span class="ow" id="mwCH0">-></span><span class="w" id="mwCH4"> </span><span class="kt" id="mwCH8">R</span><span class="w" id="mwCIA"> </span><span class="n" id="mwCIE">a</span> <span class="nf" id="mwCII">app</span><span class="w" id="mwCIM"> </span><span class="ow" id="mwCIQ">::</span><span class="w" id="mwCIU"> </span><span class="kt" id="mwCIY">R</span><span class="w" id="mwCIc"> </span><span class="n" id="mwCIg">a</span><span class="w" id="mwCIk"> </span><span class="ow" id="mwCIo">-></span><span class="w" id="mwCIs"> </span><span class="p" id="mwCIw">(</span><span class="kt" id="mwCI0">R</span><span class="w" id="mwCI4"> </span><span class="n" id="mwCI8">a</span><span class="w" id="mwCJA"> </span><span class="ow" id="mwCJE">-></span><span class="w" id="mwCJI"> </span><span class="n" id="mwCJM">a</span><span class="p" id="mwCJQ">)</span>

(where ${\displaystyle ::}$ means "has type"). This lets us write:

<span id="mwCJk"></span><span class="kr" id="mwCJo">newtype</span><span class="w" id="mwCJs"> </span><span class="kt" id="mwCJw">R</span><span class="w" id="mwCJ0"> </span><span class="n" id="mwCJ4">a</span><span class="w" id="mwCJ8"> </span><span class="ow" id="mwCKA">=</span><span class="w" id="mwCKE"> </span><span class="kt" id="mwCKI">Rec</span><span class="w" id="mwCKM"> </span><span class="p" id="mwCKQ">{</span><span class="w" id="mwCKU"> </span><span class="n" id="mwCKY">app</span><span class="w" id="mwCKc"> </span><span class="ow" id="mwCKg">::</span><span class="w" id="mwCKk"> </span><span class="kt" id="mwCKo">R</span><span class="w" id="mwCKs"> </span><span class="n" id="mwCKw">a</span><span class="w" id="mwCK0"> </span><span class="ow" id="mwCK4">-></span><span class="w" id="mwCK8"> </span><span class="n" id="mwCLA">a</span><span class="w" id="mwCLE"> </span><span class="p" id="mwCLI">}</span> <span class="c1" id="mwCLM">-- app (Rec g) = g -- g :: R a -> a</span> <span class="c1" id="mwCLQ">-- Rec g :: R a</span> <span class="c1" id="mwCLU">-- app :: R a -> (R a -> a)</span> <span class="nf" id="mwCLY">y</span><span class="w" id="mwCLc"> </span><span class="ow" id="mwCLg">::</span><span class="w" id="mwCLk"> </span><span class="p" id="mwCLo">(</span><span class="n" id="mwCLs">a</span><span class="w" id="mwCLw"> </span><span class="ow" id="mwCL0">-></span><span class="w" id="mwCL4"> </span><span class="n" id="mwCL8">a</span><span class="p" id="mwCMA">)</span><span class="w" id="mwCME"> </span><span class="ow" id="mwCMI">-></span><span class="w" id="mwCMM"> </span><span class="n" id="mwCMQ">a</span> <span class="nf" id="mwCMU">y</span><span class="w" id="mwCMY"> </span><span class="n" id="mwCMc">f</span><span class="w" id="mwCMg"> </span><span class="ow" id="mwCMk">=</span><span class="w" id="mwCMo"> </span><span class="p" id="mwCMs">(</span><span class="nf" id="mwCMw">\</span><span class="w" id="mwCM0"> </span><span class="n" id="mwCM4">x</span><span class="w" id="mwCM8"> </span><span class="ow" id="mwCNA">-></span><span class="w" id="mwCNE"> </span><span class="n" id="mwCNI">f</span><span class="w" id="mwCNM"> </span><span class="p" id="mwCNQ">(</span><span class="n" id="mwCNU">app</span><span class="w" id="mwCNY"> </span><span class="n" id="mwCNc">x</span><span class="w" id="mwCNg"> </span><span class="n" id="mwCNk">x</span><span class="p" id="mwCNo">))</span><span class="w" id="mwCNs"> </span><span class="p" id="mwCNw">(</span><span class="kt" id="mwCN0">Rec</span><span class="w" id="mwCN4"> </span><span class="p" id="mwCN8">(</span><span class="nf" id="mwCOA">\</span><span class="w" id="mwCOE"> </span><span class="n" id="mwCOI">x</span><span class="w" id="mwCOM"> </span><span class="ow" id="mwCOQ">-></span><span class="w" id="mwCOU"> </span><span class="n" id="mwCOY">f</span><span class="w" id="mwCOc"> </span><span class="p" id="mwCOg">(</span><span class="n" id="mwCOk">app</span><span class="w" id="mwCOo"> </span><span class="n" id="mwCOs">x</span><span class="w" id="mwCOw"> </span><span class="n" id="mwCO0">x</span><span class="p" id="mwCO4">)))</span> <span class="c1" id="mwCO8">-- x :: R a</span> <span class="c1" id="mwCPA">-- app x :: R a -> a</span> <span class="c1" id="mwCPE">-- app x x :: a</span>

The usual lambda-calculus definition ${\displaystyle \mathrm{Y}f=\mathrm{U}(\lambda x.f(\mathrm{U}x))}$ (where ${\displaystyle \mathrm{U}x=xx}$, and thus the term ${\displaystyle \mathrm{U}(\lambda x.f(\mathrm{U}x))}$ witnesses the equivalence ${\displaystyle xx=f(xx)}$) contains at its core the self-application ${\displaystyle xx}$, which is untypeable in the statically typed programming languages. But the expression app x x above is typeable. Equivalently, we can redefine the self-application combinator ${\displaystyle \mathrm{U}}$ and use it as

<span id="mwCP0"></span><span class="kt" id="mwCP4">U'</span><span class="w" id="mwCP8"> </span><span class="n" id="mwCQA">g</span><span class="w" id="mwCQE"> </span><span class="ow" id="mwCQI">=</span><span class="w" id="mwCQM"> </span><span class="n" id="mwCQQ">g</span><span class="w" id="mwCQU"> </span><span class="p" id="mwCQY">(</span><span class="kt" id="mwCQc">Rec</span><span class="w" id="mwCQg"> </span><span class="n" id="mwCQk">g</span><span class="p" id="mwCQo">)</span> <span class="nf" id="mwCQs">y</span><span class="w" id="mwCQw"> </span><span class="n" id="mwCQ0">f</span><span class="w" id="mwCQ4"> </span><span class="ow" id="mwCQ8">=</span><span class="w" id="mwCRA"> </span><span class="kt" id="mwCRE">U'</span><span class="w" id="mwCRI"> </span><span class="p" id="mwCRM">(</span><span class="nf" id="mwCRQ">\</span><span class="w" id="mwCRU"> </span><span class="kt" id="mwCRY">Rec</span><span class="w" id="mwCRc"> </span><span class="n" id="mwCRg">g</span><span class="w" id="mwCRk"> </span><span class="ow" id="mwCRo">-></span><span class="w" id="mwCRs"> </span><span class="n" id="mwCRw">f</span><span class="w" id="mwCR0"> </span><span class="p" id="mwCR4">(</span><span class="kt" id="mwCR8">U'</span><span class="w" id="mwCSA"> </span><span class="n" id="mwCSE">g</span><span class="p" id="mwCSI">))</span> <span class="c1" id="mwCSM">-- g (Rec g) = f (g (Rec g))</span> <span class="kt" id="mwCSQ">U''</span><span class="w" id="mwCSU"> </span><span class="n" id="mwCSY">x</span><span class="w" id="mwCSc"> </span><span class="ow" id="mwCSg">=</span><span class="w" id="mwCSk"> </span><span class="n" id="mwCSo">app</span><span class="w" id="mwCSs"> </span><span class="n" id="mwCSw">x</span><span class="w" id="mwCS0"> </span><span class="n" id="mwCS4">x</span> <span class="nf" id="mwCS8">y</span><span class="w" id="mwCTA"> </span><span class="n" id="mwCTE">f</span><span class="w" id="mwCTI"> </span><span class="ow" id="mwCTM">=</span><span class="w" id="mwCTQ"> </span><span class="kt" id="mwCTU">U''</span><span class="w" id="mwCTY"> </span><span class="p" id="mwCTc">(</span><span class="kt" id="mwCTg">Rec</span><span class="w" id="mwCTk"> </span><span class="p" id="mwCTo">(</span><span class="nf" id="mwCTs">\</span><span class="w" id="mwCTw"> </span><span class="n" id="mwCT0">x</span><span class="w" id="mwCT4"> </span><span class="ow" id="mwCT8">-></span><span class="w" id="mwCUA"> </span><span class="n" id="mwCUE">f</span><span class="w" id="mwCUI"> </span><span class="p" id="mwCUM">(</span><span class="kt" id="mwCUQ">U''</span><span class="w" id="mwCUU"> </span><span class="n" id="mwCUY">x</span><span class="p" id="mwCUc">)))</span> <span class="c1" id="mwCUg">-- app x x = f (app x x)</span>

Or in OCaml:

<span id="mwCUw"></span><span class="k" id="mwCU0">type</span> <span class="k" id="mwCU4">'</span><span class="n" id="mwCU8">a</span> <span class="n" id="mwCVA">recc</span> <span class="o" id="mwCVE">=</span> <span class="nc" id="mwCVI">In</span> <span class="k" id="mwCVM">of</span> <span class="o" id="mwCVQ">(</span><span class="k" id="mwCVU">'</span><span class="n" id="mwCVY">a</span> <span class="n" id="mwCVc">recc</span> <span class="o" id="mwCVg">-></span> <span class="k" id="mwCVk">'</span><span class="n" id="mwCVo">a</span><span class="o" id="mwCVs">)</span> <span class="k" id="mwCVw">let</span> <span class="n" id="mwCV0">out</span> <span class="o" id="mwCV4">(</span><span class="nc" id="mwCV8">In</span> <span class="n" id="mwCWA">x</span><span class="o" id="mwCWE">)</span> <span class="o" id="mwCWI">=</span> <span class="n" id="mwCWM">x</span> <span class="k" id="mwCWQ">let</span> <span class="n" id="mwCWU">y</span> <span class="n" id="mwCWY">f</span> <span class="o" id="mwCWc">=</span> <span class="o" id="mwCWg">(</span><span class="k" id="mwCWk">fun</span> <span class="n" id="mwCWo">x</span> <span class="n" id="mwCWs">a</span> <span class="o" id="mwCWw">-></span> <span class="n" id="mwCW0">f</span> <span class="o" id="mwCW4">(</span><span class="n" id="mwCW8">out</span> <span class="n" id="mwCXA">x</span> <span class="n" id="mwCXE">x</span><span class="o" id="mwCXI">)</span> <span class="n" id="mwCXM">a</span><span class="o" id="mwCXQ">)</span> <span class="o" id="mwCXU">(</span><span class="nc" id="mwCXY">In</span> <span class="o" id="mwCXc">(</span><span class="k" id="mwCXg">fun</span> <span class="n" id="mwCXk">x</span> <span class="n" id="mwCXo">a</span> <span class="o" id="mwCXs">-></span> <span class="n" id="mwCXw">f</span> <span class="o" id="mwCX0">(</span><span class="n" id="mwCX4">out</span> <span class="n" id="mwCX8">x</span> <span class="n" id="mwCYA">x</span><span class="o" id="mwCYE">)</span> <span class="n" id="mwCYI">a</span><span class="o" id="mwCYM">))</span>

Alternatively:

<span id="mwCYc"></span><span class="k" id="mwCYg">let</span> <span class="n" id="mwCYk">y</span> <span class="n" id="mwCYo">f</span> <span class="o" id="mwCYs">=</span> <span class="o" id="mwCYw">(</span><span class="k" id="mwCY0">fun</span> <span class="n" id="mwCY4">x</span> <span class="o" id="mwCY8">-></span> <span class="n" id="mwCZA">f</span> <span class="o" id="mwCZE">(</span><span class="k" id="mwCZI">fun</span> <span class="n" id="mwCZM">z</span> <span class="o" id="mwCZQ">-></span> <span class="n" id="mwCZU">out</span> <span class="n" id="mwCZY">x</span> <span class="n" id="mwCZc">x</span> <span class="n" id="mwCZg">z</span><span class="o" id="mwCZk">))</span> <span class="o" id="mwCZo">(</span><span class="nc" id="mwCZs">In</span> <span class="o" id="mwCZw">(</span><span class="k" id="mwCZ0">fun</span> <span class="n" id="mwCZ4">x</span> <span class="o" id="mwCZ8">-></span> <span class="n" id="mwCaA">f</span> <span class="o" id="mwCaE">(</span><span class="k" id="mwCaI">fun</span> <span class="n" id="mwCaM">z</span> <span class="o" id="mwCaQ">-></span> <span class="n" id="mwCaU">out</span> <span class="n" id="mwCaY">x</span> <span class="n" id="mwCac">x</span> <span class="n" id="mwCag">z</span><span class="o" id="mwCak">)))</span>

Some languages allow for explicitly marking general types as being recursive even without naming them. Doing that also allows for defining the ${\displaystyle \mathrm{Y}}$ combinator in such languages.

General information

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 identity function. Formally:

${\displaystyle \mathrm{\forall }x(fx=x)}$

In contrast to universal quantification over all ${\displaystyle x}$, a fixed-point combinator constructs one value that is a fixed point of ${\displaystyle f}$. The remarkable property of a fixed-point combinator is that it constructs a fixed point for an arbitrary given function ${\displaystyle f}$.

Other functions have the special property that, after being applied once, further applications don't have any effect. More formally:

${\displaystyle \mathrm{\forall }x(f(fx)=fx)}$

Such functions are called idempotent (see also Projection (mathematics)). An example of such a function is the function that returns 0 for all even integers, and 1 for all odd integers.

In lambda calculus, from a computational point of view, applying a fixed-point combinator to an identity function or an idempotent function typically results in non-terminating computation. For example, obtaining

${\displaystyle (\mathrm{Y}\lambda x.x)=(\lambda x.(\lambda x.x)(xx))(\lambda x.(\lambda x.x)(xx))}$

where the resulting term can only reduce to itself and represents an infinite loop.

Fixed-point combinators do not necessarily exist in more restrictive models of computation. For instance, they do not exist in simply typed lambda calculus.

The Y combinator allows recursion to be defined as a set of rewrite rules, without requiring native recursion support in the language.

In programming languages that support anonymous functions, 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.