Madeleines

Tiny pieces of delightful ideas

© 2017 Xgfd with Jekyll.
All rights reserved.

Y combinator from λ to Javascript

28 Jan 2016

The Y combinator, discovered by Haskell B. Curry, is defined as:

Y = λf. (λx. f (x x))(λx. f (x x))

Y combinator enables recursion without a function explicitly referring to itself. For a pseudo-recursive function f in the form f = λg. ...g..., we have f (Y f) = Y f. Let g = Y f then we have g = f g = ...g... which is recursive. Thus we achieve recursion without self-reference. A Brief and Informal Introduction to the Lambda Calculus is a good article to give a bit more background on lambda calculus and Y combinator.

This form is easy to remember and can be used to derive Y combinator in a functional programming language, like Javascript.

The lambda expression translates to JS as:

However the function body leads to an infinite call loop:

Y(f) is a fixed-point of f, or Y gives a fixed-point of f.

Notice that the two inner functions are the same, so it’s equivalent to:

Now there’s only one x => f(x(x)) so let’s focus on that.

Recall that f expects a (recursive) function. To prevent immediately evaluating x(x) (and thus to prevent the infinite loop), we wrap x(x) in a function that returns the same result for an input n, only when needed.

An example of using Y combinator to construct a recursive function is shown below. Note that ALL functions in the example can be anonymous.

Related Posts