https://abuseofnotation.github.io/category-theory-illustrated/11_natural_transformations/ [logo] < instead of $a$, as customary. function alpha(a: F) : G { } Generic types work by replacing the with some concrete type, like string, int etc. Specifically, the natural transformation from the identity functor to the list functor that puts each value in a singleton list looks like this $alpha :: \forall\ a. a \to List\ a$. Or in TypeScript: function array(a: A) : Array { return [a] } Some examples of natural transformations Once we rid ourselves of the feeling of confusion, that such an excessive amount of new terminology and concepts impose upon us (which can take years, by the way), we realize that there are, of course, many polymorphic functions/natural transformations that programmers use. For example, in the previous chapter, we discussed one natural transformation/polymorphic function the function $\forall a.a \to [a] $ which puts every value in a singleton list. This function is a natural transformation between the identity functor and the list functor. Natural transformation, defining a pointed functor in Set This is pretty much the only one that is useful with this signature (the others being $a \to [a, a]$, $a \to [a, a, a]$ etc.), but there are many examples with signature $list\ a \to list\ a$, such as the function to reverse a list. The natural transformation, for reversing a list in Set ...or take1 that retrieves the first element of a list The natural transformation, for taking the first element of a list in Set or flatten a list of lists of things to a regular list of things (the signature of this one is a little different, it's $list\ list\ a \to list\ a$). The natural transformation, for flattening a list in Set --------------------------------------------------------------------- Task 3: Draw example naturality squares of the $reverse$ natural transformation. The natural transformation, for reversing a list in Set Do the same for the rest of the transformations. --------------------------------------------------------------------- The naturality condition Before, we said that we shouldn't worry too much about naturality, as it is satisfied every time. Statistically, however, this is not true -- as far as I am concerned, about 99.999 percent of transformations aren't really natural (I wonder if you can compute that percentage properly?). But at the same time, it just so happens (my favourite phrase when writing about maths) that all transformations that we care about are natural. So, what does the naturality condition entail, in programming? To understand this, we construct some naturality squares of the transformations that we presented. We choose two types that play the role of $a$, in our case $string$ and $num$ and one natural transformation, like the transformation between the identity functor and the list functor. Pointed functor in Set The diagram commute when for all functions $f$, applying the $Ff$, the mapped/lifted version of $f$ with one functor (in our case this is just $F f : string \to num$ cause it is the identity functor), followed by ($alpha :: F b \to G\ b$), is equivalent to applying ($alpha:: F a \to G\ a$), and then the mapped version of $f$ with the other functor (in our case $G f :: List\ a \to List\ b$) i.e. \[\alpha \circ F\ f \cong G\ f \circ \alpha\] (in the programming world, you would also see it as something like $\ alpha (map\ f x) = map\ f (\alpha x)$, but note that here $map$ function means two different things on the two sides, Haskell is just smart enough to deduce which $fmap$ to use). And in TypeScript, when we are talking specifically about the identity functor and the list functor, the equality is expressed as: [x].map(f) == [f(x)] So, is this equation true in our case? To verify it, we take one last peak at the world of values. We acquire an $f$, that is, we a function that acts on simple values (not lists), such as the function $length : string \to num$, which returns the number of characters a string has and convert it, (or lift it, as the terminology goes) to a function that acts on more complex values, using the list functor, (and the higher-order function $map$). A lifted function Then, we take the input and output types for this function (in this case $string$ and $num$), and the two morphisms of a natural transformation (e.g the abstract function $\forall a.a \to [a]$) that correspond to those two types. Pointed functor in Set When we compose these two pairs of morphisms we observe that they indeed commute -- we get two morphisms that are actually one and the same function. Pointed functor in Set The above square shows the transformation $\forall a.a \to [a]$ (which is between the identity functor and the list functor, here is another one, this time between the list functor and itself ($\forall a.[a] \to [a]$) -- $reverse$ Pointed functor in Set (and you can see that this would work not just for $length$, but for any other function). So, why does this happen? Why do these particular transformations make up a commuting square for each and every morphism? The answer is simple, at least in our specific case: the original, unlifted function $f :: a \to b$ (like our $length :: string \to num$) can only work on the individual values (not with structure), while the natural transformation functions, i.e. ones with signature $list :: a \to list\ a$ only alter the structure, and not individual values. The naturality condition just says that these two types of functions can be applied in any order that we please, without changing the end result. This means that if you have a sequence of natural transformations that you want to apply, (such as $reverse$ , $take$, $flatten$ etc) and some lifted functions ($F f$, $F g$), you can mix and match between the two sequences in any way you like and you will get the same result e.g. \[take1 \circ reverse \circ F\ f \circ F\ g\] is the same as \[take1 \circ F\ f \circ reverse \circ F\ g\] ...or... \[F\ f \circ F\ g \circ take1 \circ reverse\] ...or any other such sequence (the only thing that isn't permitted is to flip the members of the two sequences -- ($take1 \circ reverse$ is of course different from $reverse \circ take1$and if you have $F\ f \ circ F\ g$, then $F\ g \circ F\ f$ won't be permitted at all due to the different type signatures). Task 4: Prove the above results, using the formula of the naturality condition. Non-natural transformations "Unnatural", or "non-natural" transformations (let's call them just transformations) are mentioned so rarely, that we might be inclined to ask if they exist. The answer is "yes and no". Why yes? On one hand, transformations, consist of an innumerable amount of morphisms, forming an ever more innumerable amount of squares and obviously nothing stops some of these squares to be non-commuting. For example, if we substitute one morphism from the family of morphisms that make up the natural transformation with some other random morphism that has the same signature, all squares that have this morphism as a component would stop commuting. Unnatural transformation This would result in something like an "almost-natural" transformation (e.g. an abstract function that reverses all lists, except lists of integers). And in the category of sets, where morphisms are functions i.e. mappings between values, it is enough to move just one arrow of just one of those values in order to make the transformation "unnatural" (e.g. a function which reverses all lists, but one specific list). Unnatural transformation in set --- like reverse, but one arrow is off Finally, if can just gather a bunch of random morphisms, one for each object, that fit the criteria, we get what I would call a "perfectly unnatural transformation" (but this is my terminology). But, although they do exist, it is very hard to define non-natural transformations. For example, for categories that are infinite, there is no way to specify such "perfectly unnatural transformation" (ones where none of the squares commute) without resorting to randomness. And even transformations on finite categories, or the "semi-natural" transformations which we described above (the ones that include a single condition for a single value or type), are not possible to specify in some languages e.g. you can define such a transformation in Typescript, but not in Haskell. To see why, let's see what the type of a natural transformation is. \[\forall\ a.\ F a \to G a\] The key is that the definition should be valid for all types a. For this reason, there is no way for us to specify a different arrows for different types, without resorting to type downcasting, which is not permitted in languages like Haskell (as it breaks the principle of parametricity). Natural transformations again Now, after we saw the definition of natural transformations, it is time to see the definition of natural transformations (and if you feel that the quality of the humour in this book is deteriorating, that's only because things are getting serious). Let's review again the commuting diagram that represents a natural transformation. Two functors This diagram might prompt us into viewing natural transformations as some kind of "two-arrow functors" that have not one but two arrows coming from each of their morphisms -- this notion, can be formalized, by using product categories. Oh wait, I just realized we never covered product categories... but don't worry, we will cover them now. Product groups and product categories We haven't covered product categories, however some pages ago, when we covered monoids and groups, we talked about the concept of a product group. The good news is that product categories are a generalization of product groups... The bad news is that you probably don't remember much about product groups, as covered them briefly. But don't worry, we will do a more in-depth treatment now: Product groups Given two groups $G$ and $H$, whose sets of elements can also be denoted $G$ and $H$... The Klein four as a product group (in this example we use two boolean groups, which we visualize as the groups of horizontal and vertical rotation of a square) ...the product group of these two groups is a group that has the cartesian product of these two sets $G \times H$ as its set of elements. The Klein four as a product group And what can the group operation of such a group be? Well, I would say that out of the few possible groups operations for this set that exist, this is the only operation that is natural (I didn't intend to involve natural transformation at this section, but they really do appear everywhere). So, let's try to derive the operation of this group. We know what a group operation is, in principle: A group operation combines two elements from the group into a third element i.e. it is a function with the following type signature: \[\circ : (A, A) \to A\] or equivalently \[\circ : A \to A \to A\] And for product groups, we said that the underlying set of the group (which we dubbed $A$ above) is a cartesian product of some other two sets which we dubbed $G$ and $H$. So, when we swap $A$ for $G \times H$ the definition becomes: \[\circ : G \times H \to G \times H \to G \times H\] i.e. the group operation takes one pair of elements from $G$ and $H$ and another pair of elements from $G$ and $H$, only to return -- guess what -- a pair of elements $G$ and $H$. Let's take an example. To avoid confusion, we take two totally different groups -- the color-mixing group and the group of integers under addition. That would mean that a value of $G \times H$ would be a pair, containing a random color and a random number, and the operation would combine two combine two such pairs and produce another one. Equations of the product of numbers and colors Now, the operation must produce a pair, containing a number and a color. Furthermore, it would be good if it produces a number by using those two numbers, not just picking one at random, and likewise for colors. And furthermore, we want it to work not just for monoids of numbers and colors, but all other monoids that can be given to us. It is obvious that there is only one solution, to get the elements of the new pair by combining the elements of the pairs given. Solutions of the product of numbers and colors And the operation of the product group of the two boolean groups which we presented earlier is the combination of the two operations The Klein four as a product group So, the general definition of the operation is the following ($g1$, $g2$ are elements of $G$ and $h1$ and $h2$ elements of $H$). \[(g1, h1) \circ (g2, h2) = ( (g1 \circ g2), (h1 \circ h2))\] And that are product groups. Product categories We are back at tackling product categories. Since we know what product groups are, and we know that groups are nothing but categories with just one object (and the group objects are the category's morphisms, remember?), we are already almost there. Here is a way to make a product category. Take any two categories: Product category - components Then take the set of all possible pairs of the objects of these categories. Product category - objects And, finally, we make a category out of that set by taking all morphisms coming from any of the two categories and replicate them to all pairs that feature some objects from their type signature, in the same way as we did for product groups (in this example, only one of the categories has morphisms). Product category This is the product category of the two categories. Natural transformations as functors of product categories In this section we are interested with the products of one particular category, namely the category we called $2$, containing two objects and one morphism (stylishly represented in black and white). The category 2 This category is the key to constructing a functor that is equivalent to a natural transformation: * Because it has two objects, it produces two copies of the source category. * because the two objects are connected, the two copies are connected in the same way as the two "images" in the target category are connected. So, given a product category of $2$ and some other category $C$... The category 2 ...there exist a natural transformation between $C$ and the product category $2\times C$. Product category Furthermore, this connection is two-way: any natural transformation from $C$ to some other category (call it $D$, as it is customary) can be represented as a functor $2 \times C \to D$. That is, if we have a natural transformations $\alpha : F \Rightarrow G$ (where $F: C \to D$ and $G: C \to D$), then, we also have a functor $2 \times C \to D$, such that if we take the subcategory of $2 \times C$ comprised of just those objects that have the $0$ object as part of the pair, and the morphisms between them, we get a functor that is equivalent to $F$, and if we consider the subcategory that contains $1$, then the functor is equivalent to $G$ (we write $\alpha (-,0)=F$ and $\alpha(-,1)=G$). Et voila! Task 5: Show that the two definitions are equivalent. This perspective helps us realize that a natural transformation can be viewed as a collection of commuting squares. The source functor defines the left-hand side of each square, the target functor -- the right-hand side, and the transformation morphisms join these two sides. Notation for natural transformation We can even retrieve the structure of the source category of these functors, which (as categories are by definition structure and nothing more) is equivalent to retrieving the category itself. Composing natural transformations Natural transformations are surely a different beast than normal morphisms and functors and so they don't compose in the same way. However, they do compose and here we will show how. The identity natural transformation Let's first get one trivial definition out of the way: for each functor, we have the identity natural transformation (actually a natural isomorphism) between it and itself. The identity natural transformation Horizontal composition The setup for composing natural transformations may look complicated the first time you see it: we need three categories $C$, $D$ and $E$ (just as composition of morphisms requires three objects). We need a total of four functors, distributed on two pairs, one pair of functors that goes from $C$ to $D$ and one that goes from $D$ to $E$ (so we can compose these two pairs of functors together, to get a new pair of functors that go $C \to E$). However, we will try to keep it simple and we will treat the natural transformation as a map from a morphism to a commuting square. As we showed above, this mapping already contains the two functors in itself. So, let's say that we have the natural transformation $\alpha$ involving the $C \to D$ functors (which we usually call $F$ and $G$). Notation for natural transformation So, what will happen if we have one more transformation $\bar\alpha$ involving the functors that go $D \to E$ (which are labelled $F'$ and $G'$)? Well, since a natural transformation maps each morphism to a square, and a square contains four morphisms (two projections by the two functors and two components of the transformation), a square would be mapped to four squares. Let's start by drawing two of them for each projection of the morphism in $C$. Horizontal composition of natural transformation We have to have two more squares, corresponding to the two morphisms that are the components of the $\alpha$ natural transformation. However, these morphisms connect the objects that are the target of the two functors, objects that we already have on our diagram, so we just have to draw the connections between them. Horizontal composition of natural transformation The result is an interesting structure which is sometimes visualized as a cube. Horizontal composition of natural transformation More interestingly, when we compose the commuting squares from the sides of the cube horizontally, we see that it contains not one, but two bigger commuting squares (they look like rectangles in this diagram), visualized in grey and red. Both of them connect morphisms $F'Ff$ and $G'Gf$. Horizontal composition of natural transformation So, there is a natural transformation between the composite functor $F' \circ F : C \to E$ and $G' \circ G : C \to E$ -- a natural transformation that is usually marked $\bar\alpha \bullet \alpha$ (with a black dot). Task 6: Show that natural transformations indeed compose i.e. that if you have natural transformations $F'Ff \Rightarrow F'Gf$ and $F'Gf \ Rightarrow G'Gf$ you have $F'Ff \Rightarrow G'Gf$. Whiskering And an interesting special case of horizontal composition is horizontal composition involving the identity natural transformation: given a natural transformation $\bar\alpha$ involving functors with signature $D \to E$ and some functor with signature $F : C \to D$, we can take $\alpha$ to be the identity natural transformation between functor $F$ and itself and compose it with $\bar\alpha$. Horizontal composition of natural transformation We get a new natural transformation $\bar\alpha \bullet \alpha$, that is practically the same as the one we started with (i.e. the same as $\bar\alpha$) so what's the deal? We just found a way to extend natural transformations, using functors: i.e we can use a functor with signature $C \to D$ to extend a $D \to E$ natural transformation and make it $C \to E$. Task 7: Try to extend the natural transformation in the other direction (by taking $\bar\alpha$ to be identity). So, this is how you compose natural transformations. It's too bad that this is form of composition is different from the standard categorical composition. So, I guess natural transformations do not form a category, like we hoped they would... Well, OK, there is actually another way of composing categories, which might actually work. Vertical composition Recall that categorical composition involves three objects and two successive arrows between them. For vertical composition of natural transformations, we will need three (or more) functors with the same type signature, say $F, G, H: C \to D$ i.e. (same source and target category) and two successive natural transformations between those functors i.e. $\alpha: F \to G$ and $\beta: G \to H$. Vertical composition of natural transformations We can combine each morphism of the natural transformation $\alpha$ (e.g. $a: F \to G$) and the corresponding morphism of the natural transformation $\beta$ (say $b:G \to H$) to get a new morphism, which we call $b \circ a : F \to H$ (the composition operator is the usual white circle, as opposed to the black one, which denotes horizontal composition). And the set of all such morphisms are precisely the components of a new natural transformation: $\beta \circ \alpha : F \ to H$. Categories of functors Now, we are approaching the end of the chapter, we will introduce our category and call it quits. To do that, we first introduce a more compressed notation for vertical composition of natural transformations (where they do indeed look vertical). We started this chapter by looking at category of sets and using internal diagrams, displaying the set elements as points and the sets /objects as collections. Vertical composition of natural transformations - internal diagram Task 8: identify the function, the three functors, and the two natural transformations used in this diagram. Then, we quickly passed to normal external diagrams, where objects are points and categories are collections. Vertical composition of natural transformations And now we go one more level further, and show the category of categories, where categories are points and functors are morphisms. Vertical composition of natural transformations in Cat In this notation, we display natural transformations as (double) arrows between morphisms. Vertical composition of natural transformations in Cat And you can already see the new category that is formed: For each two categories (like $C$ and $D$ in this case), there exists a category which has functors for objects and natural transformations as morphisms. Vertical composition of natural transformations in Cat Natural transformations compose with vertical compositions, and, of course, the identity natural transformation is the identity morphism. Interchange law Vertical and horizontal composition of natural transformations are related to each other in the following way: If we have (as we had) two successive natural transformations, in the vertical sense, like $\alpha: F \to G$ and $\beta: G \to H$. The interchange law -- horizontal component And two successive ones, this time in horizontal sense e.g. $\bar\ alpha: F' \to G'$ and $\bar\beta: G' \to H'$. (note that $\alpha$ has nothing to do with $\bar\alpha$ as $\beta$ has nothing to do with $\ bar\beta$, we just call them that way to avoid using too many letters) The interchange law -- vertical component And if the two pairs of natural transformations both start from the same category and the same functor, then the compositions of the two pairs of natural transformations obey the following law \[(b \circ a) \bullet (\bar b \circ \bar a) = (b \bullet \bar b) \ circ (a \bullet \bar a)\] --------------------------------------------------------------------- Task 9: Draw the paths of the two compositions of the transformations (on the two sides of the equation) and ensure that they indeed lead to the same place. The interchange law --------------------------------------------------------------------- 2-Categories At this point you might be wondering the following (although statistically you are more likely to wonder what the heck is all this about): We know that all categories are objects of $Cat$, the category of small categories, in which functors play the role of morphisms. But, functors between given categories also form a category, under vertical composition. Which means that $Cat$ not only has (as any other category) morphisms between objects, but also has morphisms between morphisms. And furthermore, those two types of morphisms compose in this very interesting way. So, what does that make of $Cat$? I don't know, perhaps we can call natural transformations "2-morphisms" and $Cat$ is some kind of "2-category"? But wait, actually it's way too early for you to find out. We haven't even covered limits... <