Natural Transformations in Category Theory Explained

[00:00:05]so today we will finally talk about natural transformations this is like a triad of things that are the most important foundations of category theory one is the definition of a category the second is the definition of a functor the third one is the definition of natural transformation these are like three most important things and in fact some mathematicians say that categories and farm tours are just necessary in order to define natural transformations natural transformation the most important part okay and so let me quickly summarize category is about structure right it sort of defines what structure means right factors are these mappings between categories that these are the structure and thumb towards also intuition from the intuition about founders is that that they take a category and embed it in another category so it's like searching for a pattern inside a category or or modeling the category inside another cup sometimes called models um but now what if we have two ways of modeling a category inside another category two different factors right what are the images of this category how are they related right it could be two factors that just you know not a category inside another category and they sort of do the same thing it's like these two images are almost then right the differences between them are sort of insignificant right or maybe they map it in two completely different things right so we would like to be able to compare some how the image is given by functors right so for that we need like if we want to compare things we need to map them if we can map one thing into another we have some kind of comparison right so natural transformations are defined as mappings between frontiers and of course these mappings between functors they have to preserve strategy right so since functors go between categories right so they have to take into account the fact that the source category has some structure and that the target category has some strong so they have to like take into account these two structures and try to preserve and that imposes certain conditions on on on the natural transformation so let's start with the definition the two categories the nd now we have to functors between these these categories that we want to compare so let's concentrate first on a single object in this category see who's supposed to give an object a right now one bump door let's call it f map this object into FN second factor G not the same object some object G so if we want to map one cut one factor to another factor we need a matting between these two right that would be the natural thing to do right so it's sort of respect to the fact that this category has object and then these objects are not into this category so the most natural thing here would be to say well and a transformation between two functors will have two math please - right but now do we want to introduce like an arbitrary mapping between objects in this category D this category D already has structure right it has mappings between these mappings between objects are morphisms right so a natural transformation would be picking a morphism between these two objects right in general we have you know between these two options we have a whole bunch of of morphisms well zero or more morphisms right they they form the home set so a natural transformation is a way of picking one morphism from this handsome now this has to be done I I did it only for one object these two factors map every object in this category so for every object in the category I do the same thing right so I find the two images of this object right and pick and morph is a meeting right so in this way I'm creating a whole family of morphisms right and these these morphisms individual morphisms are called called the components of the natural transformation so this is a component of the natural translate if we call this natural transformation alpha say then this is our 5a it's a component of alpha at object but notice that object a is in the category C but its component the morphism here is the category D okay so all these components taken together form a family of morphisms and this family of morphism is the natural transformation but wait this is not really yet the natural transformation because we haven't talked about morphisms in category C right now we want to talk about the structuring in category C we want this structure to the sama preserve and so far we only talked about objects you can see that we talked about morphisms indeed we talk about mortises see so for that we need to take another object that's a B right and and map it right so we'll map this object B into FB and map it into G okay now I have to like extend my category so first of all since we have this family of morphisms that the natural transformation right here we will have a component here alpha and B so we have this more for than alpha a alpha it be now what about either dismorphism F here well first of all this morphism will be mapped by the func doors right so f will be mapped by capital F as a morphism between FA and FB so this is F acting on little m and the factor G will map F into this arrow this is G now what we want to do is compare these two functor some right so we would like to have some kind of condition that says both functors map this morphism F in some kind of compatible way right so it's not like really arbitrary I mean if this factor maps F in in some weird way and this one max max in a completely different weird way then these two factors seem to be unrelated right so we would like to be some kind of relationship between this fun this morphism and this morphisms so that we can say that these factors really are similar in some way right because having a natural transformation between two factors means that they are somehow somewhat similar right because notice for instance a natural transformation doesn't have to exist at all between two arbitrary factors right I mean I said okay we have to pick a morphism between f ing a what if there is no more fitting between fi da right there are categories in which there are objects that are not connected at all you know this this counter F might be like mapping this whole category into one continent inside D and the factor G not sit into a completely different continent and there is no ships going between these two continents right no more physics then there is no relationship between these two functors there is no natural transformation between so having a natural transformation between factors means that they are somehow related so the relation between these four morphisms here there has to be something a relation beginning that tells us that these two factors are related and of course you have if you look at this you have a diagram right so these two morphisms are composable and these two morphisms are composable right we can have alpha be after at F that's one way of composing them and the other way is gf after a right now compatibility between these two factors means that these two should be okay and that's that's called the natural T condition and this diagram is called the natural t-square it doesn't look like a square just imagine it it's a little distorted okay so naturally t-square now how difficult it is to I mean how strong how strong a condition is naturality is in that depends depends very much on on the structure of the category right I mean it's in some categories there are lots of morphisms between objects like set is probably the example of a category in which morphisms are so abundant there is like a morphism between any two objects bunch of morphism between any two objects instead with the exception of the empty set right there are no more physics going to the angles so this is a very morphism rich category right so the categories is is rich then there is a lot of choice to pick these these morphisms and and make them work together right on the other hand there are a lot of squares that have to work right so it it can be a very very strong condition and in particular you said if you think about it let's like draw these as sets okay so we have let's say this is X a this is FB this is GA this is GP all right so normally in category theory we don't look inside objects right but now to get some intuition let's let's imagine that these are set and we are in the category of set and let's look inside of these things so what does it mean suppose that we have alpha a and we have these two functions given know by our function so we have F F and we have G now how much of the Alpha B is determined by these and the morality condition so suppose that we have that we have an element here so we have some element X so under F F it goes here under alpha it goes here right now gf we'll take this guy here right now naturally condition tells us that this guy has to go into this guy right so this is like alpha P at least on this element is already fixed right now of course it doesn't mean that alpha B is totally fixed because under this FF we will really map possibly into a subset of this all right so there is still anyway in mapping these elements that are outside of this image right so so it's not totally completely determined alpha B is not completely determined from alpha a and these two but you can see how close we are to determining out of it right so in a way you know if this were invertible right if it were as and an isomorphism FF we're nice and morphism then this would be completely determined all right so that's it that's a very strong condition naturality is a very can be a very strong condition at least in set and in fact we'll see that in set natural transformations are really restrictive and that there is that they can be transported from one place to another almost mechanically okay another way that mathematicians talk about natural transformation is by saying that the natural transformation Maps object to more physics right that's obvious component of a natural transformation takes an object and maps it into a morphism so there is a morphism that's parametrized by the object but they also say that a natural transformation Maps morphisms in this category seed to commuting diagonals is like if you take a particular morphism here what you get here is a commuting diagram the naturality condition for this particular morph is in half and this is a very strong statement because it what it allows us to do is remember in many of these constructions that we did previously like constructing product for product we talked a lot about commuting diagrams like in a product we had this using triangle factorizing one projection using another projection right so all these commuting diagrams I see a lot of constructions in category theory started with muting data but having natural transformation allows us to get a little bit of a higher-level language about commuting diagrams so you might think of specifying commuting diagrams as being sort of assembly language of category theory okay and we often would like to talk in a higher-level language inside category theory I mean category theory already is a high-level language right but within category theory there are still rotations like well this is really assembly language of category theory this is higher especially if you have like families of of commuting diagrams like we did when when we were constructing products all over a category right like in a Cartesian category then we have a bunch of commuting diagrams as whole families right then it makes sense to two to replace this talked about commuting diagrams with just one statement it says well there is a natural transformation between some founders okay and you just say natural transformation and that automatically tells you that there is a bunch of commuting diagrams these naturality squares right and in fact this is what happens with many of these constructions whoa well my I don't know if you get to it making the second half course right we'll talk about limits and Kohl image so limits are defined in terms can be defined in terms of natural transformations they can be defined in terms of commuting diagrams and so on but they can be translated into natural transformations and then we have this high-level language description and then we find out that well they're a special case of limits and Coulomb it's are just products in Co products so all this stuff about products and Co products that I talked in assembly language right from drawing these computing diagrams I will be able to translate into just saying oh there is a natural transformation between this and this and you know and then if we talk about the junctions at some point you know and the junctions are also these natural transformations these are involved in the junction so when you have a natural transformation between two flank doors right components of a natural transformation are our morphisms and remember morphisms are can be lost they lose information right so like if you map one factor into another factor using a natural transformation it means that there is a bunch of morphisms and they might lose information then might collapse stuff together they might not cover the whole thing and so on right so so when when there is a natural transformation from one factor to another it usually means that this other functor is sort of lower resolution right it's like you know there you have one factor that gives you a high-resolution image right and then there's another factor that gives you a low resolution image of your category inside another category right and then actual transformation just does the down sampling of this image and of course once you down sample something you cannot go back right usual like I'm like in Hollywood movies worth it look at this license plates are like in hands of now can read the license plates of the car that is a few miles away but there are some natural transformations that are invertible right and sec having having a having this idea of mapping functors you know gives us this this possibility of also defining isomorphism right what is to two factors that are isomorphic that's a great thing to be able to say that two functions are isomorphic that they're for all intents and purposes they are the same functor right well the image of under the sponsor is it's like the same thing see the same thing here in this category and the same thing here right what does it mean it means that there is a natural transformation between these images right that's invertible that means work that that's the meaning of its own it's the same thing right so what what what's a natural invertible natural transformations called the natural isomorphism right a natural isomorphism since since every natural transformation is just a bunch of morphisms it means that the natural isomorphism will be a bunch of isomorphisms right so so a natural charm isomorphism will just have these components that are invertible all the components are isomorphisms that's a natural I suppose natural isomorphisms are very important like all the a junctions will be defined in terms of okay so this is what this is in categories here right and now you are asking me the question probably but what does it have to do with programming right okay so in programming we already know what the functor is right essentially we mostly talk about endo factors right so we know what an endo factor is so a natural transformation would be a it's a family of morphisms between two endo farm tours right family of morphism morphisms here are our functions right so it's a family of functions so a family of functions that parameterize by a tie is called a polymorphic function right so natural transformation is a polymorphic function so suppose that we have two factors to end those parameters right so a natural transformation will go from F a 2 to GA right so it will be like if we define let's say alpha would be function that goes we have two factors F a and G so it's a function from F A to G right now if a is is a lowercase letter for for a type right that means it's polymorphic in this time but in Haskell we can actually say for all for all a and T 2 G a it's it's it's not mandatory right we can write a polymorphic function without for all but if we want to stress the fact that this is defined for all types a right we can do this there is an extension help me as an extension that's called explicit for all okay views this extension exclusive for all then then you can write the definition of a natural transformation between two functions f and sheep in this form it's just a polymorphic now there is a subtle difference between this definition and our categorical definition the subtle difference is that in this form in Haskell when we write something in this form we are assuming parametric amorphous meaning if we want to define this function well we will have to use one single formula for all a ok we cannot say well do this thing for integers and the different thing for bullying's right we cannot do that when we use parametric polymorphism we could just add hot polymorphs but then we would have to go to type classes right but in this form this means parametric polymorphism that means one single formula for all okay and this is much stronger than the categorical definition why is it so much stronger because we haven't we haven't talked yet about naturality condition right that's relevant way what would that view it would mean that what word is FF that's a lifting of a function in Haskell there will be a lifting of the function f using the factor capital F right the lifting of a function is done through f so this formula translates into if we call this alpha then this is alpha after F mouth F must be equal to s naught F after all okay so this is this formula written in Haskell and in Haskell I don't have to specify that this is outside and B and this is alpha hey right I could for destination do this right these two F maps are different ethnics right this is an F map for the factor F which could be completely different than the best map for the factor G right and instead of talking about this you know I'll give you an example in a moment right but what I want to say is that because of parametric polymorphism this is automatic this is a theorem for free okay I don't have to check it I never have to check the naturality condition if I define a function of this type that's parametrically polymorphic it's automatically a natural transformation okay so let's let's do an example let's erase this let me leave not all the condition here so let's pick two factors let's pick a fact or the list functor and they may be factored this is like a the best example we've actually seen transformations between list hunter and maybe factor right we talked about safe tail right now let's talk about safe head right so head is a function that takes a list and returns the first element of the list right and it's a bad function because it's not total yes if the list is empty it just blows up okay but we can define a safe head so safe and it will be a function that takes a list of a's and you set up returning a it returns and maybe of that and it's defined on an empty list it will return nothing and non-empty list or return just right so this function is total safe right but this is a function that works for every a right for every time I don't care whether it's a list of integers and stuff doubles the list of lists is the trees mr. foresters I don't care you will always work right so it is parametrically polymorphic because it's given by one formula for all times all right so it is automatically natural but just to convince you all right let's prove it let's do equation of reasoning on right so so we want to show this we want to show this on both empty list and non-empty list so let's let's apply f map first on an empty list F map F or M Jews right let's map F on an empty list it's just an empty list right now we want to follow this with safe head safe head-on an empty list okay what is it say don't be oh it's nothing okay so that's one side of the equation the other side of the equation is first apply safe head when two days safe head on an empty list there's nothing okay and then let's let it like F up F on it on another thing and that's my pep of nothing it's nothing right okay so when acting on an empty list both sides of the natural tea condition give the same result which is nothing okay let's do the same for the other case all right so let's replace an empty list with some X exists right so f naught F acting on a list like this will actually give us F X right side entreprise F X and F naught X right remember how F map acts on on a list it applies the function to the head and then to the tag and is applied well if not F right now we are acting with same help on this so we'll just pick FX so you have one justice right they've had acting on a list like this just takes the first element of the list and puts it inside just okay now the other way around first applies egghead to to X X is like that will give us just X right now we are s mapping F over just X now this F map now is the F up for maybe that's a different name all right let's map for for maybe when acting on just applies F 2 X so we'll get the result will be just have tanks okay same thing so naturality condition is automatically well I just have I proven that this is satisfied right although I didn't have to because it is automatically sucks No okay now this is this is an example I like this example because this is an example which actually shows you that category theory can be used in programming in a very practical way if you look at this it's actually an optimization if the compiler knows about naturality condition right it can do a clever thing applying an F mop to a list right is expensive right so being able to read to do the naturally D thing and apply safe head first and then F mop is cheaper okay of course not in Haskell because Haskell is lazy that's good like but but but in in in many cases you know these kind of transformations that have basis in in category theory can actually be used to optimize code and there are examples I mean head word command is is really good about using these these are complex categorical constructions to optimize Haskell code right to replace one implementation of data structure with another implementation that makes sense categorically and then show that it's actually more optimal and um now let's go back to this intuition that I told you about functors being containers right and zendo factors sort of generalizing containers so if if functors are containers right and f mob acting on a container modifies the contents of the container right it never changes the shape of the content it just modifies the content right it never shrinks a layer I never you know rearranges the list all it does it applies it to intuit content right the replaces apples with oranges a natural transformation is completely orthogonal to this the natural transformation never modifies the contents of the container what it does it repackages the container takes a container in this case for instance a list and repackages its contents into a maybe now when you are repackaging a content the content of a container you are not allowed to modify the content because this content is polymorphic so there are no ways of modifying polymorphic content there is no way to say you know add 1/2 to the content because what if the content is something that does not support having one you cannot create new elements because you don't know how to generically create a new element of an arbitrary type you can delete a right because that's a generic thing like removing elements like here we remove the whole page and it's okay removing stuff is okay but never modify okay so the natural transformation is a way of repackaging containers a functor gives you this F map it lets you change the contents of a container natural transformation repackages the contents into a different container okay and naturality condition just tells you that it really doesn't matter if you first change the contents and then repackage or first repackage and then change it so it's almost like associate they'll be like reversing the order and okay so now the question the interesting question is how ubiquitous are natural transformations in program right week we use polymorphic functions a lot in program all are are all polymorphic functions some kind of natural transformations or not and turns out a little a lot of them are okay because a lot of polymorphic functions they just you know map one type of container to another type of container right now some polymorphic functions actually not a type into a container or a container into a type but a function that say takes takes an A and pops it into a list of days that's actually a natural transformation because a is just identity factory F acting on a right so this is really identity right that's equivalent we've got there are also these these functions that take a polymorphic object and say return the number right like length of a list it takes a list arbitrary type of list and returns its length so so the right hand side of this mapping is not really doesn't depend on on a right it's just a number but that's also a factor right remember the cons functors right the constant factor ignores its type argument so even this case can be thought of as a natural transformation from a list to a constant okay so in general if you have a polymorphic function from an algebraic data type to another algebraic data type including Const Bank tours and it's a natural transformation because algebraic data types as I showed you or funk tours right so a lot of polymorphic functions are natural transformations now of course not all of them are natural transformations because we also have these contravariant functors and we have these other you know like a mixed functors that are contravariant in one argument and covariant in another argument as you want so if we have a polymorphic function that operate on something that's not covariant but contravariant turns it to Kovarian or work or does some some kind of weird stuff then it will not be a natural transformation however at some point you know you might learn about generalizations of natural transformations die natural we operate on these things that have mixed covariance so there are generalization but in general you know most polymorphic functions that you will use will be natural transformations and sometimes they aren't and that's okay okay now there is one more I told you this this example here okay if you look at this example here it's a mapping of type a into a list of a in general remember the Kleiss new category in the Class E category we have these flies the arrows that were like arrows that were going from some type a to some funk tour I don't know did I call it FA or did I call it ma people have often called em because it Simona really right so but it's a functor right and there was this in particular there is this Punk'd or there is this identity Kleiss the arrow right okay so in general I see I was a 2 MB but there is this identity closely at all that in hospitals called return and return was a function from a to MA okay today was our identity and the thing is see look at this this is really a function from functor identity functor to M it's a natural transformation from the identity function to Han and when we talk about no not in category theory this thing will be defined as a natural transformation so a classy category really has to take into account that these transformations are natural this transformation is natural and the other transformation that has to be natural is the associative associativity condition order the composition also has to be the composition has to be natural okay ah how much time do we should we stop here let's stop here okay and then continue