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!

Advertisement