Before we come to concrete combinatorial species, we define which operations a species should export. Therefore, we start by defining a category. Clearly, for a combinatorial species F, we want to be able to construct for each set U the set F[U]. As explained above, we restrict the elements of U to belong to a type L. Looking at (2), we require an Aldor function structures (see below) that should be of type
but our design usesSetSpecies L -> Generator %
Note that CombinatorialSpecies and SetSpecies should be defined in the same file since they mutually depend on each other.
We have chosen Generator instead of the probably more natural Set as the result type, since, first, we expect that sets F[U] become so big that they might waste more computer memory than being interesting. And, second, we want to do ranking and unranking and thus must have a certain order on the generated elements so that they could be deterministically mapped to natural numbers.
As for the input, our first implementation really used Set, but in Set there is no order of elements and thus we cannot guarantee that the resulting generator generates structures always in the same order for identical input sets.
The problem with Set is that sets like and are mathematically identical and they are also considered equal as elements of Set, but not so in computer memory. Often sets are internally implemented as lists with the assertion that the elements are different. No order is assumed. And it cannot be assumed since the argument of the Set constructor is a type L that need not export an ordering function. So internally, the above sets are represented as the lists [1,2] and [2,1], respectively.
We would like the function structures return identical output for identical input. In other words, the resulting generator would have to generate the elements in the same order no matter whether it would be given the set or the set since
Placing the labels of the n-th structure differently, gives a different structure. However, without an ordering function we cannot bring the internal representation of and into a canonical form. That is the reason why we decided to introduce SetSpecies.
The domain SetSpecies is like Set, but with the additional assumption that for a list a of type List(L) with all distinct elements taken from L and with b defined by
b := (set(a) $ SetSpecies(L)) :: List(L)
In order to make the function structures deterministic, we say, if x and y of type SetSpecies(L) are two equal sets (equal in the sense of SetSpecies) and if furthermore
(x :: List L) = (y :: List L)
Since nothing is said about the (internal) order of elements in Set, we cannot use Set instead of SetSpecies.
If, for example,
x: SetSpecies Integer := set [1,2];
y: SetSpecies Integer := set [2,1];
The function structures is the reason for putting the type L already in the category CombinatorialSpecies.
Usage
L == String;
Foo(L): CombinatorialSpecies(L) with {...} == add {...}
Parameters
The type of objects that are used as labels.
Description
The category combinatorial species.
CombinatorialSpecies is the category of types that provide operations on combinatorial species.
An instance of a CombinatorialSpecies provides a way to generate and count labelled and unlabelled structures.
Remarks
Exports of CombinatorialSpecies
generatingSeries: ExponentialGeneratingSeries Returns the exponential generating series of the species.
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries Returns the type generating series.
cycleIndexSeries: CycleIndexSeries Returns the cycle index series.
structures: SetSpecies L -> Generator % Generates all structures for a given set of labels.
isomorphismTypes: SetSpecies L -> Generator % Generates all isomorphism types.
expression: SpeciesExpression Returns an expression for the species.
What do we want to express with that category? Of course, an Aldor category expresses the operations that are allowed for combinatorial species. Naturally, to each combinatorial species there are associated three series, namely
Export of CombinatorialSpecies
generatingSeries: ExponentialGeneratingSeries
Usage
L == Integer;
X == SingletonSpecies L;
gs: ExponentialGeneratingSeries := generatingSeries $ X;
import from Integer;
l: List Integer := [coefficient(gs, n) for n in 0..3];
e: List Integer := [0, 1, 0, 0];
assert(l = e);
Description
Returns the exponential generating series of the species.
Export of CombinatorialSpecies
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries
Usage
L == Integer;
X == EmptySetSpecies L;
gs: OrdinaryGeneratingSeries := generatingSeries $ X;
import from Integer;
l: List Integer := [coefficient(gs, n) for n in 0..3];
e: List Integer := [1, 0, 0, 0];
assert(l = e);
Description
Returns the type generating series.
Export of CombinatorialSpecies
cycleIndexSeries: CycleIndexSeries
Description
Returns the cycle index series.
Let us carry out an example that illustrates the notions of structures and isomorphismtypes. Consider the combinatorial species L of linear orders. I.e., given a set U of cardinality n, the species L produces all n! different linear orders of U. A bijection σ : UV is simply a relabelling of a structure. For example, if we take U = , L produces the structures L[] = .
The bijection σ =
1 | 2 | 3 |
2 | 3 | 1 |
Now consider the species S of permutations. To make it more obvious that a species takes an arbitrary set, without inherent order, set U = . The structures produced by S when applied to this set are then
|
The bijection σ =
1 | a | ∗ |
a | ∗ | 1 |
1 | a | ∗ |
1 | ∗ | a |
a | ∗ | 1 |
a | 1 | ∗ |
1 | a | ∗ |
∗ | a | 1 |
1 | a | ∗ |
1 | a | ∗ |
Export of CombinatorialSpecies
structures: SetSpecies L -> Generator %
Usage
s: List L := ...
for e in structures(s) repeat ...
Parameters
A set of labels.
Description
Generates all structures for a given set of labels.
In terms of [BLL98], this function generates the set F[U] for a species F and a finite set U. In the Aldor implementation we have the restriction that the elements of U must be of the same type L.
Instead of returning a Set structure, we just require being able to generate the structures. Using Generator, we do not need to store a huge amount of data in memory.
Export of CombinatorialSpecies
isomorphismTypes: SetSpecies L -> Generator %
Description
Generates all isomorphism types.
We want to be able to use combinatorial species as labels.
Export of CombinatorialSpecies
expression: SpeciesExpression
Description
Returns an expression for the species.
expression returns an expression for the species, where the species itself is denoted with the string ”Self”.