defmodule Quark.FixedPoint do
@moduledoc ~S"""
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
...> factorial = y(fac)
...> factorial.(9)
362880
The resulting function will always be curried
iex> import Quark.SKI, only: [s: 3]
...> one_run = y(&s/3)
...> {_, arity} = :erlang.fun_info(one_run, :arity)
...> arity
1
"""
import Quark.Partial
import Quark.Curry, only: [curry: 1]
defdelegate fix(), to: __MODULE__, as: :y
defdelegate fix(a), to: __MODULE__, as: :y
@doc ~S"""
The famous Y-combinator. The resulting function will always be curried.
## Examples
iex> fac = fn fac ->
...> fn
...> 0 -> 0
...> 1 -> 1
...> n -> n * fac.(n - 1)
...> end
...> end
...> factorial = y(fac)
...> factorial.(9)
362880
"""
@spec y(fun) :: fun
defpartial y(fun) do
(fn x -> x.(x) end).(fn y ->
curry(fun).(fn arg -> y.(y).(arg) end)
end)
end
@doc ~S"""
Alan Turing's fix-point combinator. This is the call-by-value formulation.
## Examples
iex> fac = fn fac ->
...> fn
...> 0 -> 0
...> 1 -> 1
...> n -> n * fac.(n - 1)
...> end
...> end
...> factorial = turing(fac)
...> factorial.(9)
362880
"""
@spec turing(fun) :: fun
defpartial turing(fun), do: turing_inner().(turing_inner()).(fun)
defpartialp turing_inner(x, y) do
_phony = fn ->
turing_inner(x)
turing_inner(x, y)
end
cx = curry(x)
cy = curry(y)
cy.(&(cx.(cx).(cy).(&1)))
end
@doc ~S"""
A [normal order](https://wikipedia.org/wiki/Evaluation_strategy#Normal_order)
fixed point.
## Examples
iex> fac = fn fac ->
...> fn
...> 0 -> 0
...> 1 -> 1
...> n -> n * fac.(n - 1)
...> end
...> end
...> factorial = z(fac)
...> factorial.(9)
362880
"""
@spec z(fun, any) :: fun
defpartial z(g, v), do: g.(z(g)).(v)
end