Algebraic Datatypes, Combinatorial Structures, and Generating Functions

This is structured as a preliminary article on the ideas that connect algebraic datatypes, combinatorial structures, and generating functions. I have attempted to keep this post minimal in its prerequisites as there are a handful of ideas in computer science and mathematics that you have to weave through to understand the ideas here. I have attempted to navigate through these ideas without getting (too much) into the intricacies of advanced ideas like combinatorial species, analytic functors, and differentiation as zippers. I have also attempted to make it maximally visual and intuitive for a person who might be coming across this nexus of ideas for the first time. This article was penned in response to this tweet.

If you have any feedback / further ideas or if you spot any errors/omissions in the narrative or the equations, feel free to reach out to me on X or via email.

The Combinatorics $left right arrow$ Algebra Transit

The key idea of this article is that algebra of datatypes can be interpreted as transformations on the combinatorial objects they track. We will start with some algebraic manipulations to obtain a few “forms” of the same algebraic data type and then relate them to their combinatorial interpretations. Then we will discuss a bit on what differentiation/integration operators on these structures mean. An annotated bibliography is present at the bottom which briefly recounts the evolution of these ideas and locates various papers, blogposts, and dissertations in which many brilliant authors have written about these and other adjacent ideas. The summary of the ideas I describe in this article can be captured in this image, details of which will be unpacked in the prose below.

Representing Lists in Algebra

Inner / Outer View

We can represent the type of a list in a typed programming language as:

List(X) := Nil | Cons a List(X)

If this is your first time coming across the concept of algebraic types and want to understand what they are, I recommend this lucidly written series of articles by Chris Taylor. There is also a nice talk by him on the same topic.

This can be algebraized as $List of x$ = $1 plus x$ $bullet List of x$

Here, $1$ represents Nil and $x bullet$ $List of x$ stands for Cons a List(X)

The $bullet$ operator in the equational algebra is the equivalent of Cons operator in the type algebra. It is mathematically more accurate to think of these as linear orders. A linear order can be thought of as a list without any duplicate elements from the sampling set.

Now, let us proceed to do some equational manipulation with it. By shifting the $x bullet$ $List of x$ to the left hand side and factoring out $List of x$ , we get:

$open paren 1 minus x close paren$ $bullet List of x$ = $1$

which can be transformed further to:

$List of x equals the fraction with numerator 1 and denominator open paren 1 minus x close paren$

Let us call this the Outer View or Closed Form Equation.

Now, there's another equational manipulation we can do by repeatedly substituting the left hand side of $List of x$ = $1 plus x$ $bullet List of x$ into right hand side.

This will give us $List of x equals 1 plus x$ $bullet open paren 1 plus x bullet List of x close paren$ in the first iteration.

Iterating this indefinitely gives us the generating series function:

$List of x$ = $x to the 0 power plus x to the first power plus x squared plus x cubed plus dot dot dot plus x to the n-th power$

Let us call this the Inner view or the Series Form.

Together, these manipulations gives us the following two ways of representing $List of x$ :

The closed form $the fraction with numerator 1 and denominator open paren 1 minus x close paren$ and it's expanded form $x to the 0 power plus x to the first power plus x squared plus x cubed plus dot dot dot plus x$

Let us summarize this as:

$List of x equals the fraction with numerator 1 and denominator open paren 1 minus x close paren$ = $x to the 0 power plus x to the first power plus x squared plus x cubed plus dot dot dot plus x to the n-th power$

Turns out, it is not just lists, but many such algebraic data type representations have such equivalent forms and there are some fun combinatorial interpretations of these!

Family of Structures

To give the generating functions a combinatorial interpretation, we need to familiarize ourselves with some ideas from combinatorics. Given a finite set of labels, we can think of the family of structures that can be constructed from them.

We do this in a way that are considered to be the same under permutation of the labels we give them. These are called F-structures.

An important thing to notice in connection to F-structures is that these labels in themselves are not data but rather location in which data can be stored. As such, they represent the "form" in which data can be stored not its contents. That is when we say [a, b, c] denotes a list / linear order, we are saying that they are place holders named a, b, c, in which any data can be stored.

An F-structure can be viewed as taking in a set of labels and constructing another set of structures from it. We also need the detail of making it independent of the underlying labelling set, so it is defined in such a way that all such structures which can be generated by permuting the labels are considered to be the same. If you are interested in how this “lifting” is performed, I refer you to Brent Yorgey’s accessible paper on the idea.

Here are the different ways in which we can reassign labels to a 3 element set.

Corresponding to each of these permutation, we can locate a linear order in the family of structures generated above. We can think of the F-structures as a family that remains invariant under permutation of labels. This perspective will grant us a neat way to interpret the algebraic series as tracking these very combinatorial structures!

Labelled vs. Unlabelled structures

It is important to mention here that there are two kinds of structures here, unlabelled ones and labelled ones.

Notice, that we can assign labels in $n factorial$ ways to a given structure, which is the number of bijections from the domain of labels to the codomain of locations in the structure. Conversely, if we quotient the labelled structures by the number of their permutations, we acquire unlabelled structures. Quotienting by the number of ways to assign labelling shifting between the labelled $left right arrow$ unlabelled interpretation will play an important role in the ordinary vs. exponential generating function interpretation that follows. The significant takeaway here is that, labelling leads to a variety of structures which is equal to n! times the unlabelled ones.

Ordinary and Exponential Generating Functions

Now, we will proceed to give an interpretation of these F-structures in terms of generating functions. Keep in mind that every F-structure may correspond to several generating functions, not just a single one. Here, we will make use of two different families of generating functions to interpret our list expansions.

First is the ordinary generating function defined as:

$A of x equals the sum over k is greater than over equals 0 of open paren a sub n x to the n-th power close paren$

These are used when we want to count the number of unlabelled objects. Using this interpretation, if we look at the coefficients of $x to the n-th power$ , we can interpret it's coefficient as tracking the number of structures with the cardinality $n$ . That is, say the index of $x to the fourth power$ tracks the number of structures $open paren a sub n close paren$ with exactly 4 elements in it. With this, let us look at what $List of x$ is telling us:

$List of x equals x to the 0 power plus x to the first power plus x squared plus x cubed plus dot dot dot$

Since $a sub k$ for each of the powers here is equal to 1, it is telling us that there is 1 way each to create an empty list, a 1 element list, a 2 element list and a 3 element list. The coefficients index the number of lists and the exponents index the length of the corresponding lists. This coefficient extraction trick, while rather simplistic in the unlabelled list case, becomes really helpful when we start composing these structures to build up more complex combinatorial objects like binary trees. Check the bibliography in particular Chris Taylor's blogposts and its mention of binary trees for an interesting example.

Second one is the exponential generating function. Using this, we can interpret the coefficient as tracking combinatorial structures.

$A of x equals the sum over n is greater than over equals 0 of open paren a sub n close paren times the fraction with numerator x to the n-th power and denominator n factorial$

These are used when we want to count the labelled objects, that is, when the order in which they appear are significant. Here, $a sub n$ tracks the number of labelled objects with $n$ elements in it. That is, $the fraction with numerator x to the fourth power and denominator 4 factorial$ has $open paren a sub n close paren$ structures with exactly 4 elements in it.

As noted above in the family of structures section, look at how the OGF for unlabelled case and EGF for the labelled case vary by a factor of $the fraction with numerator 1 and denominator n factorial$ .

We can construct a table of linear orders / lists here that summarizes our findings.

This study is extended to a full blown theory under the name of Combinatorial Species and the dissertation of Brent Yorgey linked in the bibliography acts as a good introduction. As an added bonus, it has a lot of pretty pictures to aid the intuition!

Integration and Differentiation

Now, let us think about what integration and differentiation means on these series. If we think about the anti-derivative of our list, we can see that:

$triangle of open paren the log of open paren the fraction with numerator 1 and denominator 1 minus x close paren close paren equals the fraction with numerator 1 and denominator 1 minus x$

or conversely

$the sum of open paren the fraction with numerator 1 and denominator 1 minus x close paren equals the log of open paren the fraction with numerator 1 and denominator 1 minus x close paren$

This gives us a new closed form equation, $the log of open paren the fraction with numerator 1 and denominator 1 minus x close paren$ of which the series form turns out to be:

$the fraction with numerator x to the first power and denominator 1 plus the fraction with numerator x squared and denominator 2 plus the fraction with numerator x cubed and denominator 3 plus dot dot dot plus the fraction with numerator x to the n-th power and denominator n$

Using the exponential generating function interpretation that tracks labelled structures, we can see that this corresponds to (n-1)!, which is the number of cycles for n labelled elements.

Here are the counts for unlabelled and labelled cycles.

So in a sense, what we have derived here is, differentiation of cycles is linear orders / lists:

$Diff of Cycle of x asymptotically equals List of x$

or conversely, integrating cycles gives us linear orders.

$Int of List of x asymptotically equals Cycle of x$

Is there a combinatorial interpretation that we can assign to this transformation? Turns out, we can indeed! The idea of derivative is analogous to creating an hole in the data structure. Here in the example pictured above, 1-holed data structure of a 3 cycle is isomorphic to a linear order with 3 elements!

The differentiated F structure gives you the original F-structure unioned with a distinguished element. We can think of it as a “hole” which helps align this with the literature about differentiation on data types you can find in the annotated bibliography below.

So with that idea we can construct a more elaborate table recapitulating the set of ideas described here.

This is only a small sample of the fascinating ideas in this field, there are some really intriguing connections and deep results which are well worth perusing if the above ideas intrigued you. I have added an annotated bibliography with some brilliant material below which I hope will be helpful for the curious.

Open Questions

What does the outer view mean in terms of fraction and negative types? Hints in Sabry's work The Two Dualities of Computation: Negative and Fractional Types and Yorgey's blogpost on Virtual Species: Species subtraction made simple
What about the ordinary generating functions interpretation of the cycles? What does $one oneth comma one half comma one third comma dot dot dot$ represent?
What is the intuition behind representing combinatorial objects using the Taylor-MacLaurin series? Can we get a better intuition that algebraic manipulation into this?
What is the intuition behind employing these two series in OGF and EGF to track unlabelled and labelled objects? How does each term act as a primitive for the coefficients?
If differentiation means data structures with a hole in it, what does integration mean? Hint by Tali here: https://news.ycombinator.com/item?id=41058125
How can we distinguish lists with duplicates from the lists described above? It is perhaps better to call them linear orders rather than lists because there is no repetition of elements involved, a list on [a, b, c] can have $3 cubed$ elements rather than $3 factorial$ because we allow for repetition of elements in a list giving us [a, a, a], [a, a, b], $dot dot dot$ but in a linear order, we only allow for distinct permutations as mentioned in the article above. It might be better to give an account of linear orders with multiplicities to clarify this distinction.

Annotated Bibliography

The ideas here have a long history going back to the Symbolic Method that developed through the last few centuries. In programming, algebraic data types were brought in and this connection to the underlying calculus of these ideas started finding prominence in the papers by Abbott, Altenkirch, Conor McBride, Ghani et. al. which got linked with the combinatorial species work of André Joyal. In another line of development, Flajolet and Sedgewick invented the Analytic Combinatorics which has a rich theoretic background. There are some other related ideas, which if you are curious can find in a tweet threads of mine:

$1$ / https://x.com/prathyvsh/status/1431712326496006147

$2$ / https://x.com/prathyvsh/status/1821949561491120517