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

(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):

1. Describe the species .
2. Describe the species .
3. Describe the species .
4. 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.
5. Describe the species .
6. Describe the species (i.e. the nth derivative of the species of cycles).

Primitive species and species operations, part II

In my previous post, I began describing the primitive species and species operations supported by my combinatorial species library; we looked at the ring structure on species, that is, the primitive species and , and the operations of species sum and product. Today we’ll continue by looking at a few more primitive species: singletons, sets, and cycles.

[By the way, all the diagrams for this post and the previous one were generated programmatically using my diagrams library. I'll probably put the code up as an example on the diagrams website sometime in the near future.]

X

The species , also known as the species of singletons, is picky in a way similar to the species . Whereas only puts a structure on the empty set of labels, X only puts a (single) structure on singleton label sets. If you give it more than one label, or none, it turns up its nose and refuses to do anything.

The species X of singletons


> take 10 $ labelled singleton
[0,1,0,0,0,0,0,0,0,0]
> generate singleton (['a'] :: [Char])
['a']
> generate singleton ("abc" :: [Char])
[]


A few exercises: try to work them out yourself, then use the species library to check if you are correct!

1. Describe the species . Show that it is isomorphic to the species .
2. Describe the species .

E

The species of sets, on the other hand, isn’t picky at all: it will happily put a singleton structure on any label set. Usually we identify this structure with the label set itself; that is, the only -structure on a label set is itself.

The species E of sets


> take 10 $ labelled sets
[1,1,1,1,1,1,1,1,1,1]
> take 10 $ unlabelled sets
[1,1,1,1,1,1,1,1,1,1]
> generate set ([1..3] :: [Int])
[{1,2,3}]
> generate set ([] :: [Int])
[{}]


We can now also describe the derived species of elements, also known as the species of pointed sets. The only way to get any structures is by partitioning the label set into a singleton and all the rest, in which case we get exactly one structure; so there is one structure for each element of .


> take 10 $ labelled (x * set)
[0,1,2,3,4,5,6,7,8,9]
> take 10 $ unlabelled (x * set)
[0,1,1,1,1,1,1,1,1,1]
> generate (x * set) ([1..3] :: [Int])
[(1,{2,3}),(2,{1,3}),(3,{1,2})]


(x is just a synonym for singleton.) Noteworthy is the fact that this is the first species we’ve looked at which has different numbers of labelled and unlabelled structures! This makes sense: there are labelled -structures on a size set; but if we can’t tell the difference between the labels, any one of them is just as good as any other, so we only get one unlabelled structure (unless the label set is empty, when we don’t get any structures: the still requires us to have at least one element!). Note also that element is a special synonym for x * set with a special semantics under generate: if we really want to pick elements of the label set, then we probably don’t want to actually see each element paired with a set of the leftover elements, we just want to see the element itself:


> generate elements ([1..3]::[Int])
[1,2,3]


C

The final primitive species—and the only one so far that doesn’t feel quite so utterly trivial—is the species of cycles. puts no structures on an empty label set, but given any non-empty label set, generates the set of all cyclical orderings of the labels.

The species C of cycles

Of course, the above diagram only shows six of the cycle structures on five labels; the ellipsis is meant to suggest the others not shown. So… how many labelled cycle structures are there on five labels, or generally on labels? (Of course there is only one unlabelled -cycle.) I’ll leave it as a (hopefully easy) exercise; and of course you know how to check your answer!


> generate cycles ([1..4] :: [Int])
[<1,2,3,4>,<1,2,4,3>,<1,3,2,4>,<1,3,4,2>,<1,4,2,3>,<1,4,3,2>]


As you can see, cycles are indicated with angle brackets; it is understood that <1,2,3,4>, <2,3,4,1>, <3,4,1,2>, and <4,1,2,3> are all equivalent.

At this point, you’re probably thinking about a certain species and wondering why I haven’t mentioned it yet—it seems pretty fundamental and primitive. Are you thinking of… the species of lists? It turns out that we don’t have to take lists as primitive—we can define the species of lists as the derivative of the species of cycles! The derivative of a regular type is its type of one-hole… but I’m getting ahead of myself. We’ll look at species differentiation (along with several other operations on species) in the next post!

Primitive species and species operations

In this second post about my new combinatorial species library, I plan to begin writing about the species DSL itself: what are the primitive combinatorial species and the primitive operations on species? (The first post described the concept of combinatorial species in general. Also, for those following along at home, I’ve just uploaded version 0.2.1 of the species library, which is a vast improvement over 0.1, with many new features and a few bug fixes; just cabal update && cabal upgrade species. Also also, note that it currently only builds on ghc 6.10.x.)

The Species type class

The central point of the combinatorial species formalism is that there is a deep and fruitful analogy between species and certain types of generating functions: every species corresponds to (several different types of) generating functions, and every species operation corresponds, in a fairly natural way, to operations on generating functions. For example, “adding” two species has the combinatorial interpretation of disjoint sum, but also corresponds to generating function addition—that is, the generating function of a sum of species is the sum of their generating functions. Like every good generating function, these generating functions encode various sorts of information about species (such as counting labelled or unlabelled structures), so once we have written down a description of a combinatorial structure using primitive species and species operations, we can use the generating function analogy to compute various properties of the species.

So, how to represent combinatorial species in our library? With a Species type class, of course! The type class mechanism is perfectly suited to this situation—we have an abstract algebraic structure (species and species operations) which can be interpreted in several ways. So we can write down an expression of type Species s => s, and then choose to compute certain things about it simply by choosing what type it should be. Without further ado, let’s see (an idealized version of) the type class itself, defined in Math.Combinatorics.Species.Class:

class (Algebra.Differential.C s) => Species s where
  singleton :: s
  set       :: s
  cycle     :: s

  o         :: s -> s -> s
  cartesian :: s -> s -> s
  fcomp     :: s -> s -> s
  ofSize    :: s -> (Integer -> Bool) -> s

(I’ve actually left out a few methods, but they all share the property that they have default implementations in terms of the other methods, and are only in the class so they can be given specialized implementations in certain instances. I’ve left them out for now to simplify the discussion.)

So we can now write expressions like

(set `ofSize` (>3)) `fcomp` (cycle `o` singleton) :: Species s => s

but what does it mean? (Actually, this particular example is pretty meaningless. =) And what’s that Algebra.Differential.C constraint? Let’s start at the beginning.

0

The Algebra.Differential.C constraint requires any instance of Species to be a differentiable ring. In particular, it (transitively) implies the constraint Algebra.Additive.C, which means that instances of Species must form an additive group: there must be a species operation (+), and a species 0 which is the identity for (+). (It also requires an operation negate which produces additive inverses, but that isn’t implemented yet!) Let’s see what these correspond to.

The species is the Scrooge of the species world: it refuses to create a single structure, no matter how many labels you give it!

The species 0

Let’s see how to use this species with the library:

> take 10 $ labelled 0
[0,0,0,0,0,0,0,0,0,0]
> take 10 $ unlabelled 0
[0,0,0,0,0,0,0,0,0,0]
> generate 0 ([1..3] :: [Int])
[]


Pretty boring, huh? Well, it’s supposed to be. doesn’t get explicitly used very much, but it’s nice to know it’s there.

(Also, remember that to follow along, you’ll have to start ghci with the -XNoImplicitPrelude flag, then remove the loaded Prelude module with :m -Prelude, and then load MyPrelude (from the NumericPrelude library) and the species library: :m +MyPrelude Math.Combinatorics.Species.)

Species sum

And what about species addition? Addition just corresponds to disjoint (i.e. tagged) union: an -structure is either an -structure or a -structure, along with a tag so you know which it is. If you have -structures and -structures, then you have -structures.


> take 10 $ labelled lists
[1,1,2,6,24,120,720,5040,40320,362880]
> take 10 $ labelled octopi
[0,1,3,14,90,744,7560,91440,1285200,20603520]
> take 10 $ labelled (lists + octopi)
[1,2,5,20,114,864,8280,96480,1325520,20966400]
> generate (lists + octopi) ([1,2] :: [Int])
[inl([1,2]),inl([2,1]),inr(<[1,2]>),inr(<[2,1]>),
inr(<[1],[2]>)]


Do you see why the species is the identity element for species sum? If you have a structure of the species , it must be either a -structure, or an -structure: but there are no -structures! Now, you may complain that is not really an identity, since the addition still introduces an extra tag:


> generate subsets ([1..3] :: [Int])
[{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}]
> generate (0 + subsets) ([1..3] :: [Int])
[inr({1,2,3}),inr({1,2}),inr({1,3}),inr({1}),
inr({2,3}),inr({2}),inr({3}),inr({})]


That’s true, but we really only care about species identity up to isomorphism, and the species , , and are clearly all isomorphic for any species , even if they are not identical.

1

The Algebra.Differential.C constraint also implies a Algebra.Ring.C constraint, which requires a multiplication operation (*) and identity element 1.

So, what is the species ? It puts a singleton structure on the empty set of labels, but no structures on any nonempty label sets:

The species 1


> take 10 $ labelled 1
[1,0,0,0,0,0,0,0,0,0]
> take 10 $ unlabelled 1
[1,0,0,0,0,0,0,0,0,0]
> generate 1 ([] :: [Int])
[1]
> generate 1 ([1..3] :: [Int])
[]


So you can see that on the empty set, generates a single structure which is also called 1 (although it could be called anything, really).

Species product

And species product? An -structure on a set of labels is a pair consisting of an -structure on a subset of the labels, and a -structure on whatever labels are left over. In other words, to form all -structures on a set of labels , we first partition into an ordered pair of subsets in all possible ways, and for each pair, take all possible combinations of an -structure on the first subset, and a -structure on the second subset. For example:


> generate (list * list) ([1..3] :: [Int])
[([1,2,3],[]),([1,3,2],[]),([2,1,3],[]),([2,3,1],[]),([3,1,2],[]),([3,2,1],[]),([1,2],[3]),([2,1],[3]),([1,3],[2]),([3,1],[2]),([1],[2,3]),([1],[3,2]),([2,3],[1]),([3,2],[1]),([2],[1,3]),([2],[3,1]),([3],[1,2]),([3],[2,1]),([],[1,2,3]),([],[1,3,2]),([],[2,1,3]),([],[2,3,1]),([],[3,1,2]),([],[3,2,1])]


Can you see why is the identity element for this operation? The only partition of the label set that will produce any -structures is : in any other case, produces no structures. But a -structure paired with an -structure on is really just an -structure on , since there is only one -structure.

As an exercise, can you figure out what the species , , … ought to be?

I think I’ll stop there for now. In my next post, I’ll talk about the other primitive species in the Species type class: singletons, sets, and cycles.