Y combinator

The Y combinator or Y constructor is a formula in lambda calculus which allows the definition of recursive functions in that formalism.

Church invented the Y combinator:

Y = (\h . (\x. h (x x)) (\x. h (x x)))

which has the cute property that it reproduces whatever argument we give it:

  Y A   ===> A (Y A)

        ===> A (A (Y A))

        ===> A (A (A (Y A)))

        ===> A (A (A (A (Y A))))

        ===> ...