Я ☞ Articles ☞ Natural transformations as a basis of control

Introduction

How do you approach learning a new foreign language? Starting with an alphabet, looking for grammar books at local shops or insulting native speakers with your distorted pronunciation? I bet there would a plenty of opinions. My approach is to put your efforts into a limited set of words and memorize the way they form valid combinations (however I’m not sure it’s going to work for Russian).

We are going to grasp some definitions of category theory in a very limited form - they are going to be defined through functors and natural transformations. There would be no full definitions of it - I’m not a mathematician and I definetely don’t know it on a decent level. Nevertheless it doesn’t really stop me using these great universal constructions in order to forge extremely composable programming language called Я.

Naturality

Did you know that mathematicians used the term natural transformation before it was ever defined? Even before categories and functors - things that are suppose to show up earlier in chronological order. For people involved in abstract algebra those days things seemed “natural” without giving any definition of “naturality” - especially when they observe commutative diagrams. Actually you can perceive “naturality” as a synonymous of “the obvious choice” or “the only one”.

The history is going to repeat itself - we will start with natural transformations, then we quickly explore functor varieties and try to express other things without even touching the foundations - categories, sets, etc. Probably true math bros are going to be outraged by these crumpled musings but this is the way (I’m not gonna lie) I perceive these definitions avoiding stepping into academia territory.

Real world first

Let’s say we have a list of users. We want to get a top user’s age.

As you can see, it doesn’t really matter if we:

First map a List in order to transform User elements to Integer and then try to top it
First get a topmost User and then map an age function in Maybe

users `yo` age `yi` top `q__` users `yi` top `yo` age

Or in case if you want to write it in point-free style, it’s a perfect illustration of the difference between the regular composition operator and the opposite one (ha/ho):

top `ha'yo` age `q__` top `ho'yo` age

Generalizing

Let’s take a look at this commutative diagram that generalizes the latter above:

Instead of top morphism we have η (which is called a component of a natural transformation)
List and Maybe are substituted with T and TT functor placeholders respectively
User and Integer are replaces with contravariant a and covariant o type variables

Natural Transformation is a mapping between functors such that:

TT[f] ∘ η[a] ≡ η[o] ∘ T[f]

So as you can see on the commutative diagram above, it doesn’t really matter which way we are going to choose, they are equivalent.

Natural Transformation is a basic building block of control flow in Я. Actually everything is deriving from this term, even Category and Functor (which is definetely a noncense from theoretical point of view, but this design choice let us to use these definitions interchangeably in Haskell type system).

Functors

And as we already started to talk about functors… they are just mappings between categories:

You can see that this morphism from a to o is moved pretty accurately to another side of this double arrow called map. This is how Functor looks like schematically and this is how I imagine it in my head when I do code.

But what does + symbol is doing there? Oh, I forgot to notice - when people talk about functors they usually mean covariant ones. These “usual” functors map morphisms as it is.

List, Maybe, State - most of the functors in Я are covariant ones.

Contravariant functors are weird - they flip morphisms. Compare this diagram to the one above:

What if I tell you that there is a contravariant functor that you work on a day-to-day basis? Functions!

Actually, functions are bifunctors (bi means “two” here) - they are contravariant by a first argument and covariant by a second one!

So… how all this theoretical stuff is related to a language itself? Operators!

Operators

In Я all operarator names on bifunctors with a function-like parameter arrangement (T[-,+]) start with h token - which means Hom Functor: ho, ha, hu, hv.

We can define map expression like this, so you can spot the difference between a covariant map (+) and a contravariant one (-):

map[+]: from a o `AR_` into (t a) (t o)
map[-]: from o a `AR_` into (t a) (t o)

In the beginning of this article you should stumble upon this piece of code:

users `yo` age `yi` top `q__` users `yi` top `yo` age

Since both List and Maybe are covariant functors we use a circle with a bullet point inside (yo).

`yo` (yo): t a `AR_` into (from a o) (t o)

Yoneda lemma

But wait… aren’t these definitions are different?

map[+]: from a o `AR_` into (t a) (t o)
   `yo` : t a `AR_` into (from a o) (t o)

What if I tell you that these definitions are kinda… the same? “Kinda”, because they are naturally isomorphic. This is one of most significant theoretical result of reasoning on functors and natural transformations - Yoneda lemma.

We will talk about it next time.

Continue: Using Yoneda lemma for flipping notation

In case if you want to go deeper into this topic:

Murat Kasimov 🎲

Explorer

Backlinks