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
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.
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!
Let’s see how to use this species with the library:
> take 10 $ labelled 0
> take 10 $ unlabelled 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.)
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
> take 10 $ labelled octopi
> take 10 $ labelled (lists + octopi)
> generate (lists + octopi) ([1,2] :: [Int])
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])
> generate (0 + subsets) ([1..3] :: [Int])
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.
Algebra.Differential.C constraint also implies a
Algebra.Ring.C constraint, which requires a multiplication operation
(*) and identity element
So, what is the species ? It puts a singleton structure on the empty set of labels, but no structures on any nonempty label sets:
> take 10 $ labelled 1
> take 10 $ unlabelled 1
> generate 1 ( :: [Int])
> 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).
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])
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.