A functor is among other things a graph homomorphism, so a natural trans-formation between two functors is a natural transtrans-formation of the corre-sponding graph homomorphisms. The following proposition is an immediate consequence of 4.2.12.
4.3.1 Proposition If C andD are categories, the functors fromC toD form a category with natural transformations as arrows.
We denote this category by Func(C,D). Other common notations for it areDC and [C,D]. Tennent [1986] provides an exposition of the use of functor categories for programming language semantics.
Of course, thegraph homomorphisms fromC toD, which do not neces-sarily preserve the composition of arrows inC, also form a categoryMod(C,D) (see 4.2.14), of whichFunc(C,D) is a full subcategory.
A natural transformation from one functor to another is a special case of a natural transformation from one graph homomorphism to another, so the ideas we have presented concerning natural transformations between graph homomorphisms apply to natural transformations between functors as well.
In particular, Theorems 4.2.12 and 4.2.20 are true of natural transformations of functors.
IfC is not a small category (see 2.1.5), thenFunc(C,D) may not be locally small (see 2.1.7). This is a rather esoteric question that will not concern us in this book since we will have no occasion to form functor categories of that sort.
We motivated the concept of natural transformation by considering models of graphs, and most of the discussion in the rest of this section concerns that point of view. Historically, the concept first arose for functors and not from the point of view of models.
4.3.2 Examples We have already described some examples of natural trans-formations, as summed up in the following propositions.
In 3.1.14, we defined the graph homomorphism ηG : G −→ U(F(G)) which includes a graph G into U(F(G)), the underlying graph of the free categoryF(G).
4.3.3 Proposition The family of arrowsηG form a natural transforma-tion from the identity functor onGrf to U ◦F, where U is the underlying graph functor fromCat toGrf.
The proof is left as an exercise.
In 3.4.2, we defined the concept of equivalence of categories.
4.3.4 Proposition A functor F :C −→D is an equivalence of categories with pseudo-inverseG:D−→C if and only ifG◦F is naturally isomorphic toidC andF◦Gis naturally isomorphic toidD.
Proof. Conditions E–2 and E–3 of 3.4.2 can be recast as the statement that G(F(f))◦ uC =uC0 ◦f and that F(G(g))◦vD =vD0 ◦g, in other words that the following diagrams commute:
C0 -G(F(C0)) uC0
C uC-G(F(C))
? f
? G(F(f))
D0 -F(G(D0)) vD0
D vD-F(G(D))
? g
? F(G(g))
In this form, they are the statements thatuis a natural transformation from idC toG◦F and thatvis a natural transformation from idD−→F ◦G. Since each component ofuand each component of v is an isomorphism,uandv are natural equivalences.
4.3.5 Example Letα:M×S −→S andβ :M ×T −→T be two actions by a monoidM (see 3.2.1). Letφ:S−→T be an equivariant map. IfF and Gare the functors corresponding toαandβ, as defined in 3.2.3, thenφis the (only) component of a natural transformation fromF toG. Conversely, the only component of any natural transformation fromF toGis an equivariant map between the corresponding actions.
4.3.6 Example LetU :Mon−→Setbe the underlying functor from the category of monoids. DefineU×U :Mon−→Setas follows:
(i) For a monoidM, (U×U)(M) =U(M)×U(M).
(ii) For a monoid homomorphismh:M −→N,
(U×U)(h)(m, n) = (h(m), h(n))
Then monoid multiplication is a natural transformation fromU×UtoU. Formally: Letµ:U×U −→U be the family of maps whose value at a monoid M is the function µM :U(M)×U(M)−→U(M) defined byµM(m, m0) = mm0, the product ofm andm0 in M. Thenµ is a natural transformation.
(The functionµM is not in general a monoid homomorphism, unless M is commutative.)
It is instructive to see whyµis a natural transformation. Leth:M −→N be a monoid homomorphism. We must show that the following diagram
4.3 Natural transformations between functors 111 commutes:
(U×U)(N) -U(N) µN
(U×U)(M) µM-U(M)
? (U×U)(h)
?
h (4.25)
The top route takes an element (m, m0)∈(U×U)(M) toh(mm0). The lower route takes it toh(m)h(m0). The commutativity of the diagram then follows from the fact thathis a homomorphism.
4.3.7 Example The bijection of Exercise 4 of Section 1.2 can be seen to be a natural isomorphism, this time between contravariant functors.
Let B be a fixed set. We define a functor R :Setop −→Set such that for a setA,R(A) = Rel(A, B) as defined in the exercise. For a set function F :A0−→Aand relation α∈Rel(A, B), define R(F)(α) to be the relation α0∈Rel(A0, B) defined bya0α0b if and only ifF(a0)αb. It is easy to see that this makesR:Setop−→Set a functor. (Note thatR(A) =Rel(A, B), but Risnot HomRel(−, B).)
For each A, let φA: Rel(A, B)−→Hom(A,PB) be the bijection of the exercise. If we check that the functionsφA are the components of a natural transformation fromR to Hom(A,PB), the transformation will automati-cally be a natural isomorphism by Theorem 4.2.20. To show that it is natural, letα∈Rel(A, B) anda0∈A0. Then
Hom(F,PB)¡φA(α)(a0)¢=φA(α)¡F(a0)¢={b|F(a0)αb}
={b|a0α0b}=φA0¡
R(F)(a0)¢ as required.
This natural isomorphism can be taken to be the defining property of a topos (Section 15.2.2).
4.3.8 Natural transformations involving lists Many of the operations on lists available in functional programming languages can be seen as natu-ral transformations involving the Kleene closure or list functor (3.1.12). For example, one can apply the Kleene closure twice to get the list of lists functor that takes a setAtoA∗∗. An element ofA∗∗is a list of lists. For example, if A={a, b}, one of the elements ofA∗∗isw= ((a, b),(b, b, a),(),(a)). If f :A
−→Bis a function,f∗∗takeswto ((f(a), f(b)),(f(b), f(b), f(a)),(),(f(a))).
The operation of flattening a list simply concatenates the lists in the list; for example, flatten(w) = (a, b, b, b, a, a). Of course, flatten is a distinct
function for each setA; if we write flattenA:A∗∗−→A∗for each setA, then flatten is a natural transformation from∗∗to∗, as you can see by checking that this diagram commutes for each functionf :A−→B:
B∗∗ -B∗ flattenB A∗∗ flattenA-A∗
? f∗∗
?
f∗ (4.26)
Another operation in functional programming languages consists of applying a binary operation to a list. This is calledreduce,applyorfold. We shall consider only the case when the binary operation is associative. (When it is not associative, some choice is made about how to associate the list.) This gives a natural transformation from F ◦ U to idMon, where F :Set
−→Monis the free monoid functor and U :Mon−→Set is the underlying set functor. For example, ifM is a monoid with elementsk, mandn, then reduce(k, k, n, m) =k2nm, the product of the list using the operation ofM. In this case, naturality means that for any monoid homomorphismh:M
−→N,h◦reduceM = reduceN ◦F(U(h)), which is easily checked.
Note that although both reduce and flatten take lists as arguments, reduceM is a monoid homomorphism with domain F(U(M)) (whose ele-ments are lists), whereas flattenAis a set function with domainA∗∗. This is reflected by the fact that, when implemented in a programming language, reduce takes an operation as well as a list as argument, but flatten takes only a list.
These and other list operations can often be generalized to sets of expres-sions instead of sets of lists. In particular, flatten in this more general sense is one of the fundamental constituents of triples (Section 14.3), namelyµ.
More about these ideas may be found in [Bird, 1986] and [Spivey, 1989].
4.3.9 Natural transformations of graphs We now consider some nat-ural transformations involving the categoryGrf of graphs and homomorph-isms of graphs.
4.3.10 Example In 3.1.9, we defined the functorN:Grf−→Set. It takes a graphG to its setG0of nodes and a homomorphismφtoφ0. Now pick a graph with one node∗and no arrows and call itE. LetV = HomGrf(E,−).
A graph homomorphism from the graphE to an arbitrary graphG is evi-dently determined by the image ofE and that can be any node ofG. In other words, nodes ofG are ‘essentially the same thing’ as graph homomorphisms fromE toG, that is, as the elements of the setV(G).
4.3 Natural transformations between functors 113 We can define a natural transformationα:V −→N by defining
αG(f) =f0(∗)
where G is a graph and f :E −→G is a graph homomorphism (arrow of Grf). There must be a naturality diagram (4.20) for each arrow of the source category, which in this case isGrf. Thus to see thatαis natural, we require that for each graph homomorphismg:G1−→G2, the diagram
NG1 -NG2
N g VG1 V g-VG2
? αG1
? αG2
commutes. NowN gisg0(the node map ofg) by definition, and the value of V (which is a hom functor) at a homomorphismg composesg with a graph homomorphism from the graphE. Then we have, for a homomorphismf :E
−→G1(i.e., an element of the upper left corner of the diagram), (αG2◦V g)(f) =αG2(g◦f) = (g◦f)0(∗) while
(N g◦αG1)(f) =N g(f0(∗)) =g0(f0(∗))
and these are equal from the definition of composition of graph homomorph-isms.
The natural transformation α is in fact a natural isomorphism (Ex-ercise 9). This shows that N is naturally isomorphic to a hom functor.
Such functors are called ‘representable’, and are considered in greater de-tail in 4.5.1.
4.3.11 Connected components A node a can be connected to the nodebof a graph G if it is possible to get from atob following a sequence of arrows ofG in either direction. In order to state this more precisely, let us say that an arrowa ‘has’ a node n ifn is the domain or the codomain (or both) of a. Then a is connected to b means that there is a sequence (c0, c1, . . . , cn) of arrows ofG with the property thatais a node (either the source or the target) ofc0, b is a node ofcn, and for i= 1, . . . , n, ci−1 and ci have a node in common. We call such a sequence an undirected path betweenaandb.
It is a good exercise to see that ‘being connected to’ is an equivalence re-lation. (For reflexivity: a node is connected to itself by the empty sequence.)
An equivalence class of nodes with respect to this relation is called a con-nected componentof the graphG, and the set of connected components is calledWG.
Connected components can be defined for categories in the same way as for graphs. In that case, each connected component is a full subcategory.
Iff :G −→H is a graph homomorphism and if two nodesaandbare in the same component ofG, then f(a) andf(b) are in the same component of H; this is because f takes an undirected path between a and b to an undirected path betweenf(a) andf(b). Thus the arrowf induces a function W f :WG −→WH, namely the one which takes the component ofato the component off(a); and this makesW a functor fromGrf toSet.
For a graph G, let βG :NG −→WG be the set function which takes a node ofG to the component ofG that contains that node. (The component is the value of βG at the node, not the codomain.) Thenβ :N −→W is a natural transformation. It is instructive to check the commutativity of the requisite diagram.
4.3.12 Example In 3.5.9, we described a functor Σ which provided a meaning inSet for each program in the programming languageL of 2.2.5.
A person more oriented to machine language might have preferred to give the meaning of all the data in terms of numbers, in particular the integers between 0 and 2K for some fixed numberK≥7 (the constraint is to accom-modate the ASCII codes).
Thus one could define a functor Σ0for which
(i) Σ0(NAT) is the set of integers between 0 and 2K−1. Then the constant 0 would be the number 0, but Σ0(succ) would have to calculate the successor modulo 2K.
(ii) Σ0(BOOLEAN) is the set{0,1}, withtrue= 1 andfalse= 0.
(iii) For each character c, Σ0(c) is the ASCII code for c. Then we would have to take Σ0(CHAR) to be the setA={n∈N|0≤n≤127}. For each of the three typesTin our language, we have a way of rewriting each datum in Σ(T) to become the corresponding datum in Σ0(T). This rewriting becomes a functionβT : Σ(T)−→Σ0(T):
(i) β(NAT)(n) isnmodulo 2K.
(ii) β(BOOLEAN)(true) = 1 andβ(BOOLEAN)(false) = 0.
(iii) β(CHAR)(c) is the ASCII code ofc for each characterc.
In order to preserve the intended meaning, Σ0(succ) would have to be the successor function modulo 2K, Σ0(ord) would have to be the inclusion ofA into Σ0(NAT) and Σ0(chr) would have to be the function from Σ0(NAT) to A which takes the remainder modulo 128.
4.3 Natural transformations between functors 115 Preserving the meaning of ord (an informal idea) means formally that this diagram must commute, as it does with the definitions given of Σ(ord) and Σ0(ord):
Similar remarks apply to the preservation of the other operations. This is a special case of a general principle that, given two functorsGand G0 which are semantics in some sense, a natural transformation β :G−→G0 can be said to preserve the meaning of the operations.
The natural transformationβ was constructed for the given data types.
The only constructor inL, namely composition, does not destroy the natural transformation property: if the given β gives the naturality property for primitive operations, it does so for all their composites, as well. This is an instance of the following proposition.
4.3.13 Proposition Let F, G:C −→D be functors. Let S be a (possibly empty) set of arrows of C with the property that every arrow of C is a composite of arrows ofS and let βC:F(C)−→G(C) be an arrow ofD for
Thenβ is a natural transformation.
Proof. iff :A−→Bandg:B−→Care arrows ofS, then the outer rectangle below commutes because the two squares do:
G(A) -G(B)
The naturality diagram for the casef = id (that is, the empty composite) is automatic. The proof follows from these facts by induction.
4.3.14 Exercises
1. Prove Proposition 4.3.3.
2. Show that the familyβG of arrows taking a node to its component defined in 4.3.11 is indeed a natural transformation.
3. LetC be a category. Asubfunctorof a functorF :C −→Setis a functor G:C −→Setwith the property that for each objectC ofC,G(C)⊆F(C) and such that for each arrowf :C−→C0and each elementx∈GC, we have that Gf(x) =F f(x). Show that the inclusion function iC :G(C)−→F(C) is a natural transformation.
4. Show that the map which takes an arrow of a graph to its source is a natural transformation fromA to N. (See 3.1.9.) Do the same for targets.
(Actually, every operation in any multisorted algebraic structure gives a nat-ural transformation. Example 4.3.6 was another example of this. See [Linton, 1969b], [Linton, 1969a].)
5.† Show that ifC is a discrete category with set of objectsC0(hence essen-tially a set), thenFunc(C,Set) is equivalent to the slice categorySet/C0. (See 2.6.10.)
6. For each setS, let{}S:S−→PSbe the function which takes an element xofS to the singleton subset{x}.
a.Show that{}is a natural transformation from the identity functor on Setto the direct image powerset functorP. (See 3.1.16.)
b.Show that{}is not a natural transformation from the identity functor onSetto the universal image powerset functor. (See 3.1.19.)
c.Explain why it does not even make sense to ask whether it is a natural transformation to the inverse image powerset functor.
7. Verify the claims in 4.3.5.
8. Show that the results of Exercise 7 of Section 4.2 are still true if we replace the graphG by a categoryD.
9. Show that the natural transformation of 4.3.10 is a natural isomorphism.
10. a. Show that for any integerk, the set of paths of lengthkof a graph is the object part of a functorPk:Grf−→Set. (See 2.1.2.)
b. Show thatP0 is naturally isomorphic to the node functorN defined in 3.1.9.
c. Show thatP1is naturally isomorphic to the arrow functorAof 3.1.9.
4.4 Godement calculus 117