Quark v1.0.1 Quark.FixedPoint

Fixed point combinators generalize the idea of a recursive function. This can be used to great effect, simplifying many definitions.

For example, here is the factorial function written in terms of y/1:


iex> fac = fn fac ->
...>   fn
...>     0 -> 0
...>     1 -> 1
...>     n -> n * fac.(n - 1)
...>   end
...> end
iex> factorial = y fac
iex> factorial.(9)
362880

The resulting functions will always be curried


iex> import Quark.SKI, only: [s: 3]
iex> one_run = y(&s/3)
iex> {_, arity} = :erlang.fun_info(one_run, :arity)
iex> arity
1

Summary

Functions

fix()

See Quark.FixedPoint.y/0

fix(a)

See Quark.FixedPoint.y/1

turing()

Alan Turing’s fix-point combinator. This is the call-by-value formulation

turing(fun)

y()

The famous Y-combinator. The resulting function will always be curried

y(fun)

z()

A normal order fixed point

z(g)

z(g, v)

Functions

fix()

See Quark.FixedPoint.y/0.

fix(a)

See Quark.FixedPoint.y/1.

turing()

Alan Turing’s fix-point combinator. This is the call-by-value formulation.


iex> fac = fn fac ->
...>   fn
...>     0 -> 0
...>     1 -> 1
...>     n -> n * fac.(n - 1)
...>   end
...> end
iex> factorial = turing(fac)
iex> factorial.(9)
362880

turing(fun)

Specs

turing((... -> any)) :: (any -> any)

y()

The famous Y-combinator. The resulting function will always be curried.


iex> fac = fn fac ->
...>   fn
...>     0 -> 0
...>     1 -> 1
...>     n -> n * fac.(n - 1)
...>   end
...> end
iex> factorial = y(fac)
iex> factorial.(9)
362880

y(fun)

Specs

y((... -> any)) :: (any -> any)

z()

A normal order fixed point


iex> fac = fn fac ->
...>   fn
...>     0 -> 0
...>     1 -> 1
...>     n -> n * fac.(n - 1)
...>   end
...> end
iex> factorial = z(fac)
iex> factorial.(9)
362880

z(g)

z(g, v)

Specs

z((... -> any), any) :: (any -> any)