8.10 Addition of Species

Definition 8.9. [BLL98, chp. 1.3] Let F and G be two species of structures. The species F + G called the sum of F and G, is defined as

(F + G)[U ] = F[U ]+ G [U ]  (disjoint union)
(35)
for any finite set U.

The transport along a bijection σ : U V is carried out by setting, for any (F + G)-structure s on U,

              {
(F + G)[σ](s) = F [σ ](s) if s ∈ F [U ],
               G [σ](s) if s ∈ G [U ].
(36)

Note that structures from F and G are by definition never isomorphic as structures of F + G - even if F and G are identical. For example, if F and G are both singletons, (F + G)[{1}] produces two non-isomorphic copies of {1}.

Type Constructor

Plus

Description

Sum of combinatorial species.

166adom: Plus 166a  (55)
Plus(
    F: SPECIES,
    G: SPECIES
)(L: LabelType): CombinatorialSpecies(L) == add {
        Rep == Union(left: F L, right: G L);
        import from Rep;
        implementation: Plus 166b
}

Defines:
Plus, used in chunks 194, 442, 455, 641–48, 650, 652, 658, 719, 721, 731, and 732.

Uses CombinatorialSpecies 71, LabelType 62, and SPECIES 55.
166bimplementation: Plus 166b  (166a)  166c
(tw: TextWriter) << (x: %): TextWriter == {
        rep x case left => tw << rep(x).left;
        tw << rep(x).right;
}
166cimplementation: Plus 166b+   (166a)  166b  169a
(x: %) = (y: %): Boolean == {
        macro {X == rep x; Y == rep y}
        X case left  and Y case left  => X.left  = Y.left;
        X case right and Y case right => X.right = Y.right;
        false;
}

We have to create the objects generatingSeries, isomorphismTypeGeneratingSeries and expression first, before we start initialization. For example, the following variant would lead to a runtime error when a species is defined recursively:

generatingSeries: ExponentialGeneratingSeries == new();
set!(generatingSeries $ %, generatingSeries$F(L) + generatingSeries$G(L));
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == new();
set!(isomorphismTypeGeneratingSeries $ %,
    isomorphismTypeGeneratingSeries $ F(L) +
    isomorphismTypeGeneratingSeries $ G(L));

Suppose now we define a species as follows:

macro {
  I == EmptySetSpecies;
  X == SingletonSpecies;
  + == Plus;
  * == Times;
}


A(L: LabelType): CombinatorialSpecies L == (X + A*A)(L) add;

Seeing the first set! instruction, in the second line of the variant above, Aldor would descend to the initialization of F(L) and G(L) before initializing isomorphismTypeGeneratingSeries. However, the initialization of F(L) depends on an already initialized isomorphismTypeGeneratingSeries.

The same situation occurs in the Times constructor.

ToDo 25
mrx 1 11-Dec-2006: Provide a more detailed description on what is going on.
mrx 2 28-Dec-2006: The code for expression is incorrect, if either of the two species expressions is only implicit, i.e., contains the special expression "Self". For example, if F has expression X+Self*Self, and G has expression X, then we obtain for F+G the expression X+X+Self*Self, which corresponds to a different species, really.

The same is true for the code in Times and Compose. I probably need to change the type of expression to be a list of SpeciesExpressions.

169aimplementation: Plus 166b+   (166a)  166c  169b
generatingSeries: ExponentialGeneratingSeries == new();
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == new();
cycleIndexSeries: CycleIndexSeries == new();
expression: SpeciesExpression == new();
local init(): () == {
        set!(
            generatingSeries $ %,
            generatingSeries $ F(L) + generatingSeries $ G(L)
        );
        set!(
            isomorphismTypeGeneratingSeries $ %,
            isomorphismTypeGeneratingSeries $ F(L) +
            isomorphismTypeGeneratingSeries $ G(L)
        );
        set!(
            cycleIndexSeries $ %,
            cycleIndexSeries $ F(L) + cycleIndexSeries $ G(L)
        );
        set!(expression$%,  expression$F(L) + expression$G(L));
}
init();

Uses CycleIndexSeries 330, ExponentialGeneratingSeries 316, OrdinaryGeneratingSeries 311, and SpeciesExpression 430.
169bimplementation: Plus 166b+   (166a)  169a  170
structures(s: SetSpecies L): Generator % == generate {
        for f in structures(s)$F(L) repeat yield per union f;
        for g in structures(s)$G(L) repeat yield per union g;
}

Uses Generator 617 and SetSpecies 117.
170implementation: Plus 166b+   (166a)  169b
isomorphismTypes(s: SetSpecies L): Generator % == generate {
        for f in isomorphismTypes(s)$F(L) repeat yield per union f;
        for g in isomorphismTypes(s)$G(L) repeat yield per union g;
}

Uses Generator 617 and SetSpecies 117.