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”.

[caption id=“attachment_271” align=“aligncenter” width=“400” caption=“Species differentiation”][/caption]

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!

[caption id=“attachment_274” align=“aligncenter” width=“400” caption=“Differentiating a cycle to get a list”][/caption]

> 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.

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).