Introducing Math.Combinatorics.Species!

Posted on July 24, 2009
Tagged combinatorial species

I have just uploaded to Hackage version 0.1 of the species package, a Haskell library for computing with combinatorial species. Much like David Amos’s great series of posts introducing his Haskell for Maths library, I plan to write a series of posts over the next week or two introducing the library, explaining how it works, and showing off some interesting examples.

But, first things first: if you’d like to install the library and play along, just

cabal update; cabal install species

(Man, do I ever love cabal-install! But I digress.)

Combinatorial what?

So, what are combinatorial species? Intuitively, a species describes a certain combinatorial structure: given an underlying set of labels, it specifies a set of structures which can be built using those labels. For example, $L$, the species of lists, when applied to an underlying set of labels $U$ yields the set of all linear orderings of the elements of $U$. So in general a species can be viewed as a function which takes any set (the labels) and produces another set (of structures built out of those labels).

[caption id=“attachment_182” align=“aligncenter” width=“364” caption=“The species L of lists.”][/caption]

Actually, this isn’t quite enough to capture our intuition about what a species ought to be: we want a species to work “independently” of the underlying set; which labels we use shouldn’t matter at all when it comes to describing structures. So, additionally, we require that if $F$ is a species, any bijection $\sigma : U \to T$ between two sets of labels can be “lifted” to a bijection between sets of $F$-structures, $F[\sigma] : F[U] \to F[T]$, in a way that respects composition of bijections. (Of course, the categorists ought to be jumping out of their seats right now: all this just amounts to saying that a species is an endofunctor $F : \mathbb{B} \to \mathbb{B}$ on the category of sets with bijections.) Importantly, it is not too hard to see that this requirement means that for any species $F$, the size of $F[U]$ depends only on the size of $U$, and not on the actual elements of $U$.

Counting labelled structures

So, let’s see some examples already! What sorts of things might we want to compute about species?

First, we of course want to be able to count how many structures are generated by a species. As a first example, consider again the species $L$ of lists. Given an underlying set $U$ of size $n$, how many lists $L[U]$ are there? That’s easy: $n!$.

[brent@euclid:~]$ ghci -XNoImplicitPrelude > :m +Math.Combinatorics.Species > take 10 $ labelled lists [1,1,2,6,24,120,720,5040,40320,362880]

The function labelled takes a combinatorial species $F$ as an argument, and computes an infinite list where the entry at index $n$ is the number of labelled $F$-structures on an underlying set of size $n$.

(This is also a good time to mention that the species library depends on the Numeric Prelude, an alternative Haskell Prelude with a mathematically sane hierarchy of numeric types; hence we must pass ghci the -XNoImplicitPrelude flag so we don’t get lots of horrible name clashes. I’ll write some additional thoughts on the Numeric Prelude in a future post.)

Now, so far this is nothing new: Dan Piponi wrote a blog post about a Haskell DSL for counting labelled structures back in 2007, and in fact, that post was part of my inspiration for this library. Counting labelled structures works by associating exponential generating functions to species. (More on this in a future post.) But we can do more than that!

Counting unlabelled structures

For one, we can also count unlabelled structures. What’s an unlabelled structure? Intuitively, it’s a structure where you can’t tell the difference between the elements of the underlying set; formally, it’s an equivalence class of labelled structures, where two labelled structures are equivalent if one can be transformed into the other by permuting the labels.

So, how about unlabelled lists?

> take 10 $ unlabelled lists [1,1,1,1,1,1,1,1,1,1]

Boring! This makes sense, though: there’s only one way to make a list out of n identical objects.

[caption id=“attachment_189” align=“aligncenter” width=“350” caption=“The species of lists on indistinguishable labels”][/caption]

But how about something a bit less trivial?

> take 10 $ labelled partitions [1,1,2,5,15,52,203,877,4140,21147] > take 10 $ unlabelled partitions [1,1,2,3,5,7,11,15,22,30] > :m +Math.OEIS > description fmap (lookupSequence . take 10 $ labelled partitions) Just “Bell or exponential numbers: ways of placing n labeled balls into n indistinguishable boxes.” > description fmap (lookupSequence . take 10 $ unlabelled partitions) Just “a(n) = number of partitions of n (the partition numbers).”

[caption id=“attachment_191” align=“aligncenter” width=“350” caption=“Unlabelled partitions”][/caption]

(I couldn’t resist sneaking in a little plug for my Math.OEIS module there too. =) So, how does this work? Well… it’s a bit more complicated! But I’ll explain it in a future post, too.

Generating structures

But that’s not all! Not only can we count structures, we can generate them, too:

> generate lists ([1..3] :: [Int]) [{,1,2,3},{,1,3,2},{,2,1,3},{,2,3,1},{,3,1,2},{,3,2,1}] > generate partitions ([1..3] :: [Int]) [[[1,2,3]],[[1,2],[3]],[[1,3],[2]],[[1],[2,3]],[[1],[2],[3]]]

This is a bit magical, and of course I will… explain it in a future post. For now, I leave you with this challenge: can you figure out what the asterisks are doing there? (Hint: the curly brackets denote a cycle…)

Of course, no DSL would be complete without operations with which to build up more complicated structures from simpler ones; in my next post I’ll talk about operations on combinatorial species.

Introducing Math.Combinatorics.Species!

Combinatorial what?

Counting labelled structures

Counting unlabelled structures

Generating structures

Further reading