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
| (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,
| (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)[] produces two non-isomorphic copies of
.
Type Constructor
Plus
Description
Sum of combinatorial species.
166a⟨dom: 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.
166b⟨implementation: Plus 166b⟩≡ (166a) 166c ⊳
(tw: TextWriter) << (x: %): TextWriter == {
rep x case left => tw << rep(x).left;
tw << rep(x).right;
}
166c⟨implementation: 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.
169a⟨implementation: 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.
169b⟨implementation: 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.
170⟨implementation: 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.