Species operations: differentiation

Continuing my series describing my new combinatorial species library, today we’ll take a look at the operation of differentiation.

You may remember that the Species type class has an Algebra.Differential constraint, which, as I previously explained, transitively implies an Algebra.Ring constraint. But we haven’t yet talked about the Differential contraint itself, which requires a method differentiate :: Species s => s -> s (which I will abbreviate using the standard “prime” notation), which should satisfy $(x * y)' \equiv x' * y + x * y'$

(up to isomorphism). Okay, this is just the normal product rule for differentiation, from calculus—but what on earth could such a thing mean combinatorially?

There is actually a nice, simple answer: an $F'$-structure on the underlying set $U$ consists of an $F$-structure on $U \cup \{*\}$, where $*$ is a distinguished element distinct from all the elements of $U$. To make the connection to data type differentiation, we can also think of $*$ as a “hole”. Species differentiation

The above diagram illustrates the situation: an $F'$-structure on $\{1,2,3,4,5\}$ is an $F$-structure on $\{1,2,3,4,5,*\}$.

And how about the law $(F * G)' \equiv F' * G + F * G'$? Does this make combinatorial sense? (You may want to stop and think about it before reading on!)

By definition, an $(F * G)'$-structure on $U$ is an $(F*G)$-structure on $U \cup \{*\}$, which is a pair of an $F$-structure and a $G$-structure on a splitting (a two-partition) of $U \cup \{*\}$. The distinguished $*$ label must end up on one side or the other, so an $(F*G)'$-structure can arise in one of two ways: it is either an $F'$-structure paired with a $G$-structure, or an $F$-structure paired with a $G'$-structure, depending on where the $*$ ends up. But this is precisely saying that $(F * G)' \equiv F' * G + F * G'$!

Where does species differentiation show up? The most well-known place is in defining the species $L$ of lists (linear orderings). In fact, $L = C'$,

that is, the species $L$ is the derivative of the species $C$ of cycles. A cycle defines an ordering, but there is no distinguished beginning or end; by making a cycle out of some elements with a distinguished extra element $*$, we uniquely identify a beginning/end of the ordering on the original elements: a list! Differentiating a cycle to get a list

> take 10 . labelled $lists [1,1,2,6,24,120,720,5040,40320,362880] > take 10 . labelled$ oneHole cycles
[1,1,2,6,24,120,720,5040,40320,362880]
> generate lists ([1..3] :: [Int])
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
> generate (oneHole cycles) ([1..3] :: [Int])
[<*,1,2,3>,<*,1,3,2>,<*,2,1,3>,<*,2,3,1>,<*,3,1,2>,<*,3,2,1>]

Here’s an example of differentiation in action. In the species library, the function oneHole is provided as a synonym for differentiate. The session above shows that there are the same number of labelled lists as labelled one-hole cycles: this isn’t surprising given the discussion above, and in fact, list is actually implemented as oneHole cycle. Actually, this is a tiny lie, as the rest of the session shows: since lists are such a common combinatorial structure, there is a special case for them in the generation code. But we can explicitly generate one-hole cycles as above; it’s easy to see that they are in one-to-one correspondence with the lists.

To finish off this post, a few exercises for you (you can check your answers with the species library):

1. Describe the species $1'$.
2. Describe the species $X'$.
3. Describe the species $E'$.
4. Does differentiation distribute over addition? That is, is it true that $(F + G)' \equiv F' + G'$ for any species $F$ and $G$? Give a combinatorial interpretation of this identity, or say why it does not hold.
5. Describe the species $L'$.
6. Describe the species $C^{(n)}$ (i.e. the nth derivative of the species of cycles). 1. abc def says:
Thanks for this article. Your example of $C’ = L$ helps understand this stuff.