Lists Are Geometric Series

Introduction

Functional programmers get a lot of flack for being too theoretically-minded. “Real” programmers think of them as being passionate, perhaps even noble idealists, but ultimately best left to their corner of the woods, away from those actually getting stuff done. The functional programmers, on the other hand, high up in their ivory tower, don’t think about the rest of us at all. Instead, they spend their days writing about category theory, arranging languages into blocks, and, on occasion, discovering pearls.

This article will explain one simple, lovely fact from the PL world. It’s unlikely to inform how you actually program, but if you don’t have one already, it might give you a taste for what the whole PL/FP fuss is all about, anyway.

Algebraic Data Types

Before we get to the pearl, we have to briefly discuss Algebraic Data Types (ADTs). These are just datatypes which we can combine to form new types. Specifically, we do this with sum and product types:

These names are especially intuitive if we think of these as sets: If \(A\) has \(n\) elements, and \(B\) has \(m\) elements, then \(A \times B\) has \(n * m\) elements and \(A+B\) has \(n+m\) elements. Extending this logic, we get an exponential type, as well as unit and a void type, with one and zero elements respectively:

This analogy extends to our familiar high-school algebra identities (up to isomorphism):

\[ \begin{align} A + 0 &\cong A \\ B + A &\cong B + A \\ (A + B) + C &\cong A + (B + C) \\ \\ A \times 0 &\cong 0 \\ A \times 1 &\cong A \\ A \times B &\cong B \times A \\ (A \times B) \times C &\cong A \times (B \times C) \\ \\ 1^A &\cong 1 \\ A^0 &\cong 1 \\ A^1 &\cong A \\ A^{B + C} &\cong A^B \times A^C \\ (A^B)^C &\cong A^{B \times C} \\ \\ (A + B) \times C &\cong (A \times C) + (B \times C) \\ (A \times B)^C &\cong A^C \times B^C \end{align} \]

The Pearl

Armed with this notation, we can turn our attention to (linked) lists:

Rewriting this in our new notation, we can expand this out into an infinite, non-recursive definition:

\[ \begin{align} L &= 1 + a \times L \\ &= 1 + a (1 + a \times L) \\ &= 1 + a + a^2 \times L \\ &= \cdots \\ &= 1 + a + a^2 + a^3 + a^4 + \cdots \end{align} \]

What’s the intuition here? What this tells us is that a List a is either: zero as, one a, two as, etc.

That’s exactly what a list is! But this correspondance doesn’t end here. For example, consider these two types:

These become:

\[ \begin{align} T &= 1 + a \times T^2 \\ &= 1 + a (1 + a \times T^2)^2 \\ &= 1 + a + 2 a^2 \times T^2 + a T^4 \\ &= \cdots \\ &= 1 + a + 2 a^2 + 5 a^3 + 14 a^4 + \cdots \\ \\ F &= a + F^2 \\ &= a + (a^2 + 2 a F^2 + F^4) \\ &= \cdots \\ &= a + a^2 + 2 a^3 + 5 a^4 + 14 a^4 + \cdots \end{align} \]

These are the Catalan Numbers, and indeed, there is one empty Tree, one Tree with one element, 2 Trees with 2 elements, and so on. The pattern’s holding! ¹

Moreover, we can see that \(F \cong A \times T\)! These two data structures, one with all its data on its leaves, and all its leaves bare, are actually (almost) the same!

But what about going the other way? Starting from a series and deriving a data structure? We’ll use a simple example, where the coefficients just count up:

\[ \begin{align} 1 + 2 a + 3 a^2 + \cdots = 1 + a + &a^2 + a^3 + \cdots \\ + a + &a^2 + a^3 + \cdots \\ + &a^2 + a^3 + \cdots \\ & \quad \vdots \end{align} \]

This is just \(L^2\)! And, as we now expect, there are 3 ways a pair of List as can have 2 elements, 4 ways it can have 3 elements, and so on. ²

By now, you can probably guess, for example, what might happen if we introduced several variables:

If you’d like more of a challenge, why not try coming up with a data structure corresponding to the Fibbonacci sequence:

\[ F = 1 + a + 2a^2 + 3a^3 + 5a^4 + 8 a^5 + \cdots \]

Further Reading

There’s more to be said about these expansions, but I find the fact that they exist cool enough as it is. If you’re interested in this, maybe check out:

• This StackOverflow question, from someone discovering these patterns themselves.
• This blog post, from the Recurse Center.
• This post, about extending this correspondance to derivatives.