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

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

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).
About these ads
This entry was posted in combinatorics, haskell, math and tagged , , . Bookmark the permalink.

One Response to Species operations: differentiation

  1. Pingback: And now, back to your regularly scheduled combinatorial species | blog :: Brent -> [String]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s