Source code for snippets ⋅ Twitter discussion ⋅ Reddit discussion ⋅ Linkedin discussion ⋅ Facebook discussion
Disclaimer: this article requires symbolical thinking along with prior experience in programming with abstractions.
This order is not accidental - functors start making sence in context of natural transformations and categories are rarely interesting without reasoning in terms of mappings between them i.e. functors.
To dive in, we are going to use abstract concepts like objects and morphisms so that morphisms relate objects:
We will start with an example that every software engineer would understand. Imagine morphisms like these:
I intentionally don't specify source and target morphisms, we will fill the gap for intuition a bit later.
Having those morphisms available, how can we compose them so that we can achieve this?
I bet many of you already know the answer, but I would like to articulate on it for a while.
To ease the further perception, let's substitute source and target morphisms with Arrow:
Now we have the luxury to involve some intuition - having List of files, we need to know the name of the one listed first:
We can say that we have two ways to compose plain morphisms - left-to-right and right-to-left:
If we would have another morphism - it turns full name into a base name, we could compose them in following ways:
As you can see, we can reach the same result using different ways - exactly in this case the difference is rather syntactical.
If we look at another morphism, we notice that objects there have a parameter i:
It means that we can specialise this i with any other object, let's use those we already familiar with:
But due to parametricity we cannot just substitute i with different objects:
Let's focus on objects instead. There is a way to map morphisms inside these parametric objects:
See this morphism in between? We can substitute it with we the one we already have - name:
By composing operators mentioned above we have following solutions:
Here is the point - if these two ways are equivalent i.e. give you the same result - this transformation is called natural!
Even without fully understanding of what do these operators do you can track objects - we either apply head and map name over Maybe or we map name morphism over List and apply head. Take your time to grasp this diagram below:
In essence natural transformations are mappings between functors - in our case between List and Maybe. What are functors then?
In turn functors are mappings between categories so that they preserve some properties of morphisms that come from categories.
Composition of morphisms - we can either compose morphisms inside functor or compose functor mappings of morphisms:
Alternatively you can compose morphisms in reverse, but property remains the same:
Identity of morphisms - you can either map identity inside functor or apply identity to functor itself:
Challenge: check List and Maybe on satisfying properties above.
Finally it's time for categories, this is where composition and identity come from with a set of properties to check.
To check associativity we need third plain morphism, let it be a hash function:
So that these parentheses arrangements give you the same result:
And final property is identity:
What makes it identity is not stating "giving back the same object" but rather how it relates to other morphisms:
Alright, we are all set! So now we are aware how natural transformations, functors and categories are connected to each other.
This article has started with abstract morphisms named source and target, and then in order to build intuition with some code we switched to Arrow. It also has been said that functors are mappings between categories and we used only Arrow for both source and target which makes these functors endofunctors. We are about to introduce other categories and explore functors between them - this is where the real fun begins.
Let's think on what File object could be and how we could get Name from it. The first thing to assume is that Name is a part of File object i.e. Product, in turn let Name object being Product as well:
We can define File object this way:
There are plenty of ways to implement name Arrow morphism:
Result should be the following:
Implementation for base Arrow morphism is similar to name - the only difference is positioning.
Now we can compose these morphisms to get base name of some File:
Okay, another morphism is head - in natural transformations it plays a role of a component. Here is a type signature for component of Arrow - due to parametricity object argument is ommitted:
The idea is that you can pull their implementation from type system this way:
According to First behaviour We will get some value only if List is not empty:
Components of Arrow are trivial - provide an input and receive an output. But what about components of other categories?
Both Event semicategory and Scope category are subtypes of Arrow:
Therefore you can use them as the latter and get the same results:
You can think of Event semicategory and Scope category as upgraded Arrow that give you some additional abilities. To grasp these abilities let's practice reading this code out loud involving intuition.
Retrieve Maybe First item from List statefully i.e. return Product of popped out Maybe First item and this List without First item:
As a result of this Event component we are left with non empty List only if we have at least two items.
So as you could notice, this transfering of modified domain object into a codomain one is the essense of stateful morphisms. We even can build one of them from scratch using Arrow and Product:
Here we just copy domain object as it is though:
Well, it is possible to modify File object as Event morphism but if we continue using bare Arrow and Product the code would look clunky since we are enreaching expressibility of basic primitives and we need more advanced one called Scope.
If objects of Product are distinguishable i.e. they have different types then we can use special expression for it:
Needless to say that these morphisms of Scope are composable:
Having Scope morphisms we can retrieve and update objects within other objects:
The same intuition could be applied to a Scope component:
Concentrate on Maybe First item in List i.e. return Product of Maybe First item and instruction on how it should be updated:
Above only retrieving part of Scope components was demonstrated, let's grasp updating part case by case:
So that if an item we are focusing on does Exist then we can either pop it out from List or replace with another value.
But if if an item we are focusing on is Empty then we cannot bring it into existence whatever value we provide!
These code examples above is not how Scope usually involved, more commonly it's coupled with Event.
Sometimes we want to treat morphisms as functors where 1st argument is contravariant and 2nd one is covariant, see Arrows:
For this kind of argument arrangement (1st argument is contravariant and 2nd one is covariant) we have operator aliases called Hom-functors so that information about position (either 1st or 2nd) is omitted:
Same Hom-functors operators you can use for Scope and Event:
These operators do look like composition but in fact they are functors. The reason is that composition operators from literature on category theory is not composable enough! If you look at these declarations above, you'll notice that we map from Scope and Event morphisms into Arrow.
I've distracted you from explaining Scope morphisms and components to show how it could be coupled with Event:
So that we can contravariantly map 1st parameter of Event from Scope into Arrow. Okay... what's the intuition behind it? Before answering this question we need some time to explore how to work with raw Event morphisms first, there are only two of them:
The first one looks like identity but in fact it's not - laws just don't hold. Anyway, it's still usefull to construct an empty Event - nothing really happens since state propagates without any changes and copied into result:
Another raw morphism let us update state to a new one and get old one back as a result:
Here is the thing - we can restrict Scope i.e. zoom in First item of List without touching Event:
Challenge: use Swap instead of Pull on code snippet above.
If you try to replace First item in empty List using Swap - you will not suceed. If you still want to do it you need to use another label called Fresh:
Checkpoint: check your intuition, what's the difference between these components? What do they do?