y.md

The Y Combinator

In most functional languages, you can write something like:

let rec fac = function
  | 0 -> 1
  | n -> n * fac (n - 1)

However, what if recursion were disallowed? In that case, we have to write something like

let fac = fun other_fac -> function
  | 0 -> 1
  | n -> n * other_fac (n - 1)

How do we get a copy of other_fac in this case? Let's pretend we have a function fix that fixes this issue as such:

type fn = 'a -> 'b
type non_recursive_fn = fn -> 'a -> 'b
let fix = ???
fix : non_recursive_fn -> fn

(* such that *)
let fac' = fix fac
fac' : int -> int

Note that fix's definition does not require recursion.

In fact, in Haskell, the built-in fix does just this! It is relatively easy to implement fix in any functional language. The typical form of fix is the Y combinator, written in lambda calculus as λf.(λx.f (x x)) (λx.f (x x)).

See here for more details.