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
(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 
-structure on the underlying set 
consists of an 
-structure on 
, where 
is a distinguished element distinct from all the elements of . 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 -structure on 
is an -structure on 
.
And how about the law 
? Does this make combinatorial sense? (You may want to stop and think about it before reading on!)
By definition, an 
-structure on is an 
-structure on , which is a pair of an -structure and a 
-structure on a splitting (a two-partition) of . The distinguished label must end up on one side or the other, so an 
-structure can arise in one of two ways: it is either an -structure paired with a -structure, or an -structure paired with a 
-structure, depending on where the ends up. But this is precisely saying that !
Where does species differentiation show up? The most well-known place is in defining the species 
of lists (linear orderings). In fact,
,
that is, the species is the derivative of the species 
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):
- Describe the species
.
- Describe the species
.
- Describe the species
.
- Does differentiation distribute over addition? That is, is it true that
for any species and ? Give a combinatorial interpretation of this identity, or say why it does not hold.
- Describe the species
.
- Describe the species
(i.e. the nth derivative of the species of cycles).
Posted by Brent 
Posted by Brent 
Posted by Brent 