Page 278 - Artificial Intelligence for the Internet of Everything

256 Artificial Intelligence for the Internet of Everything

4. There is a canonical algebra T, called the term algebra, whose elements are
constructed iteratively from the operations of the signature.
5. Structural recursion allows us to interpret a term t 2 T relative to any alge-
bra X, defining a unique F-algebra homomorphism T ! X.
F-algebras provide a uniform framework for representing the operations of
an algebraic theory; however, they are not sufficient to capture the axioms
that govern these operations. These, too, can be incorporated into the cat-
egorical formalism, using more sophisticated structures called monads. The
topic is beyond the scope of this chapter, but see Awodey (2010) for details.

13.5 COALGEBRA AND INFINITE DATATYPES

In the previous section we introduced a fairly elaborate categorical frame-
work for governing compositional (algebraic) structures. One of the advan-
tages of the categorical approach is that it helps to identify potential
extensions and generalizations of our naive intuition. One particularly fertile
avenue for such generalizations is to “turn the arrows around.”
In CT, “co-” means “reversed.” Any categorical concept can be dualized
to define a related coconcept; just turn around all the arrows. Proofs can also
be reversed, allowing us to port any theorem in the original context to a dual
theorem for the new structures. A typical example involves the Cartesian
product and the coproduct (disjoint union), mentioned informally in the last
section. Formally, these can be defined in terms of dual construction prin-
ciples for arrows into (out of ) the (co)product:

Product f : Z ! X Y equivalent f 1 : Z ! X

f 2 : Z ! Y

equivalent
Coproduct g : X + Y ! Z g 1 : X ! Z
g 2 : Y ! Z
We can use the same sort of reasoning to identify the theory of coalgebras
and coinductive data structures. As before, the theory of coalgebra is parame-
terized by a functor F which describes a signature. We will use the same set of
examples asabove to show howthingschangewhen wefliparoundthe arrows.
If an algebra is a function α: FX ! X, then a coalgebra should be a func-
tion κ: X ! FX. When FX ¼ 1+ X, it is not hard to show that a coalgebra is
p
the same as a partial function X S!X. To translate between the two
viewpoints we let κ equal p wherever p is defined, and send everything else
to c 2 1.