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 \(0\) is the Scrooge of the species world: it refuses to create a single structure, no matter how many labels you give it!

[caption id=“attachment_220” align=“aligncenter” width=“400” caption=“The species 0”][/caption]

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. \(0\) 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 \((F+G)\)-structure is either an \(F\)-structure or a \(G\)-structure, along with a tag so you know which it is. If you have \(m\) \(F\)-structures and \(n\) \(G\)-structures, then you have \(m + n\) \((F+G)\)-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 \(0\) species is the identity element for species sum? If you have a structure of the species \(0 + F\), it must be either a \(0\)-structure, or an \(F\)-structure: but there are no \(0\)-structures! Now, you may complain that \(0\) 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 \(F\), \(0 + F\), and \(F + 0\) are clearly all isomorphic for any species \(F\), 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 \(1\)? It puts a singleton structure on the empty set of labels, but no structures on any nonempty label sets:

[caption id=“attachment_223” align=“aligncenter” width=“400” caption=“The species 1”][/caption]

> 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, \(1\) generates a single structure which is also called 1 (although it could be called anything, really).

Species product

And species product? An \((F*G)\)-structure on a set of labels is a pair consisting of an \(F\)-structure on a subset of the labels, and a \(G\)-structure on whatever labels are left over. In other words, to form all \((F*G)\)-structures on a set of labels \(U\), we first partition \(U\) into an ordered pair of subsets in all possible ways, and for each pair, take all possible combinations of an \(F\)-structure on the first subset, and a \(G\)-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 \(1\) is the identity element for this operation? The only partition of the label set that will produce any \((1*F)\)-structures is \((\emptyset, U)\): in any other case, \(1\) produces no structures. But a \(1\)-structure paired with an \(F\)-structure on \(U\) is really just an \(F\)-structure on \(U\), since there is only one \(1\)-structure.

As an exercise, can you figure out what the species \(2\), \(3\), … 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.