An Introduction to Function Fixed Points with the Y-Combinator

Searching for the essence of recursion

The Y-combinator is a function that lets us do something neat: it allows us to encapsulate recursion in functions. This article shows how this is done, and how this encapsulation is related to the mathematical concept of fixed points. The focus here is on recursion rather than on combinatorial logic, so we won’t cover more advanced, non-recursive implementations of the Y-combinator. If you are trying to use the Y-combinator as a method for introducing recursion into a language, this article will likely be more useful to you.

The Y-combinator

In this article, the Y-combinator does not refer to an orange website, but to the original, a function in Alonzo Church’s lambda calculus. A combinator, for those unfamiliar with the term, is a way of combining functions into a new function. Specifically, it is a function which takes one or more pure functions as inputs, and returns a new function as output, which calls no other functions besides those provided as input to the combinator. Church’s lambda calculus is a way to express any program as a series of combinators, and “Y” is the name he chose for the combinator which provides recursion.

function fibonacci(n : number) : number {
if (n < 3) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
n => {
if (n < 3) return 1;
// Problem: we have no name for ourselves that we can use here
return ???(n - 1) + ???(n - 2);
}
function fibonacciFactory(fib : number => number) : number => number {
return (n : number) => {
if (n < 3) return 1;
return fib(n - 1) + fib(n - 2);
}
}
const fibonacci = fibonacciFactory(?)
const fibonacci = fibonacciFactory(fibonacciFactory(?));
fibonacciFactory(fibonacciFactory(fibonacciFactory(?))
const fibonacci = y(fibonacciFactory);fibonacci(7); // returns 13
function y<A, B>(fn: (A => B) => (A => B)) : A => B {
function result (arg : A) : B {
const completeFunction : A => B = fn(result);
return completeFunction(arg);
};
return result;
}

Fixed points of functions

Having y allows us to explain the title of this post, “fixed points.” Fixed points come from math, where a fixed point of a function f is a value for which f(x) = x. For example, the squareRoot function has two fixed points, 0 and 1, because squareRoot(0) = 0 and squareRoot(1) = 1. The function x => (x — 3) * 2 has one fixed point, 6, (because (6 — 3) * 2 = 6) and the function x => x + 1 has no fixed points, because there is no value x for which x = x + 1. The identity function, x => x, has an infinite number of fixed points, because identity(x) = x for all values of x.

const fibonacci = fibonacciFactory(fibonacciFactory(?));
// Quick-and-dirty test function to verify that things
// are working the way we expect
function testFib(fib : number => number) {
console.log([1, 2, 3, 4, 5, 6, 7].map(fib));
}
testFib(fibonacci); // prints [ 1, 1, 2, 3, 5, 8, 13 ]const fibonacci2 = fibonacciFactory(fibonacci);
testFib(fibonacci2); // prints [ 1, 1, 2, 3, 5, 8, 13 ]
const fibonacci3 = fibonacciFactory(fibonacciFactory(fibonacci));
testFib(fibonacci3); // prints [ 1, 1, 2, 3, 5, 8, 13 ]
// etc.

The connection between recursion and fixed points

We saw how to implement a recursive function without explicit self-reference. First, we changed it into a higher-order function, which took another function as an argument. The argument function was tasked with performing the next step of the recursive computation, so when our originally-recursive function would have called itself, it could call the argument function instead. However, this left us with a problem. When we tried to use our new self-referential function, we ended up having to pass it its own output, which we could only get by calling it, which we could only get by passing it its own output… etc. This trapped us in an infinite chain of nested function calls: fibonacciFactory(fibonacciFactory(fibonacciFactory(...))).

JavaScript developer with a focus on typed functional programming. He/him. https://jnkr.tech