Page 277 - Artificial Intelligence for the Internet of Everything

Compositional Models for Complex Systems 255

Of course, there are many other sorts of trees, and all of these can be real-
ized as term algebras. A tree with ternary branching is associated with the
3
functor FX ¼ 1+ X . One that allows either binary or ternary branching
2 3
corresponds to FX ¼ 1+ X + X . One allowing arbitrary branching
corresponds to the functor FX ¼ List(X), which can be described not as a
2
polynomial but as an infinite series FX ¼ 1+ X + X + ⋯.
We can also introduce labeling on our trees. In order to label the leaves of
2
a binary tree, replace the unit type 1 by a label set A: FX ¼ A + X . To add a
different set of labels to the nodes, add a coefficient to the quadratic term of
2
the polynomial: FX ¼ A + B X . For example, arithmetic terms (arbitrary
numeric constants but no variables) form the inductive data structure asso-
2
ciated with the functor FX ¼  + f +, g X . This encodes the familiar
representation of algebraic terms as trees:

×

× +

5 + 13 0

4 7

(5 × (4 + 7)) × (13 + 0)

Though we usually think of this term as the description of a number, it
makes just as much sense in other contexts like polynomials and matrices
where we can interpret the 0, 1, +, and . This is the content of structural
recursion for the signature of arithmetic.
The general pattern demonstrated in these examples is captured in the
following sequence of abstract definitions.

Definition 13.2
1. An algebraic signature is a functor F: Sets !Sets.
2. An algebra for F is a set X together with a function α: FX ! X.
3. An F-algebra homomorphism hX, αi!hY, βi is a function h: X ! Y mak-
ing the following square commute:
F (h)
FX FY

α β
X Y
h