Introduction

I recently attended the Scalar Conf in Warsaw which featured several interesting speakers and presentations, many of which pertained to hot new features of Scala 3 (which I will probably never use due to overwhelming tech debt) as well as a 'surprise' presentation from Mr. Martin Odersky, where he discussed opportunities to shift away from reliance on monadic semantics in favor of direct styling allowed by the suspended continuation/boundary paradigms.

I sheathed my sneakers at this remark.

The goal of this post is to capture my learnings from Nicolas Rinaudo's wonderfully silly presentation titled Things that are things, but not other things¹ which approached the daunting challenge of grokking category theory abstractions in my preferred format of counter example: ⚔️.

The problem, of course, is that I now have to find something interesting to say about monads. And one thing that I often found frustrating when learning about that family of abstractions is how just about everything is a monad - why even have all these intermediate abstractions if everything is all the things, all the time?

This ties in to one of the ways I learn things: when given a definition of a thing, it helps me just as much to have examples of things that are not the thing as of things that are the thing. I really wished I'd had such examples of things that are things, but not other things, while learning abstractions.

Taxonomy of the Typelevel Heirarchy

First of all – just look at this mess:²

A common issue I encounter is failure to lean on the minimum-necessary type class. Implicit instances of $\sf Applicative$, $\sf Monad$, $\sf Apply$, etc. crop up in the codebase, and transient/impartial recollection of rote definitions of these terms flutter through my head as I fail to intuit why the author of any given method signature chose one type class and not the other. Additionally, I know that I am not alone in this confusion as I overwhelmingly see one of the stronger type classes (i.e. $\sf Monad$), implying that many of my fellow contributors also don't know what the tightest bound on their use case is, just that $\sf Applicative$ or $\sf Monad$ will probably suffice. (Certainly, my observations are biased since much of my work takes place at the level of abstraction where these are in fact the correct type classes to rely upon, but perhaps not all the time...)

Nicolas' presentation helped make at least a portion of the above diagram less scary by breaking each element of the following hierarchy down:

Type Constructor

The first and lowliest category in the hierarchy is the Type Constructor. The narrowest "higher kinded type" –if you could even call it that– which encapsulates the behavior of parameterization e.g.

which alone is not worth breaking.

$\sf Functor$

The $\sf Functor$ is the first category on the list we'll break by demonstrating what it is and what it is not. A $\sf Functor$ is a mapping between categories, usually for us it's a mapping between the category of types. Referencing the overall hierarchy diagram above, we can see that all we need to transform our type constructor into a $\sf Functor$ is an implementation of $\sf\textcolor{maroon}{map}$:

We have some $\sf{\textcolor{blue}{F}[\textcolor{blue}{A}]}$:

which we want to map to an $\sf{\textcolor{blue}{F}[\textcolor{blue}{B}]}$:

which we achieve via the first argument of map which is a function $\sf \textcolor{maroon}f$ from $\sf\textcolor{blue}A$ to $\sf\textcolor{blue}B$:

which is then reinserted into our type constructor $\sf\textcolor{blue}F$ which is the definition of the $\sf\textcolor{maroon}{map}$ itself:

So, how can we break a $\sf Functor$?

Function

Let's examine a practical example where our type constructor maps some $\sf\textcolor{blue}X$ to an $\sf\textcolor{blue}A$; this is the definition of a function

We can verify that this fits the pattern we need to be a $\sf Functor$ by checking it has all the constituent parts including an $\sf fa$

an $\sf\textcolor{maroon}{f}$:

and the desired resultant $\sf{\textcolor{blue}{F}[\textcolor{blue}{B}]}$:

but we're missing the implementation of $\sf \textcolor{maroon}{map}$ to take us from $\sf\textcolor{blue}{X}$ to $\sf\textcolor{blue}{B}$:

well, $\sf\textcolor{maroon}{map}$ has all the pieces we need to just compose:

yielding the correct result:

Breaking Function

To break a function so that it is no longer a $\sf Functor$, we can simply reverse the mapping of our type constructor:

which then breaks our implementation of $\sf\textcolor{maroon}{map}$: since $\sf fa$ and $\sf \textcolor{maroon}{f}$ no longer compose.

Concretely, we might have a function that goes from $\sf\textcolor{blue}{A} ⟹ \textcolor{blue}{Boolean}$:

such a function is called a $\sf\textcolor{blue}{Predicate}$

which is not a $\sf Functor$ :).

Key takeaways

A function parameterised on its:

• output type is a $\sf Functor$
• input type is not a $\sf Functor$

Interlude: Product Types

To break the rest of the higher kinded types, we'll rely on the slightly-more-complex composite type called a $\sf\textcolor{blue}{Product}$. Glossing over many tedious laws of Category Theory, a Product is simply when you cram two types into a box like so:

Given any combination of $\sf\textcolor{blue}{A}$ and $\sf\textcolor{blue}{B}$, we can get a Product via "Product Introduction":

Similarly, from any instance of a Product, we can extract the individual elements comprising it via "Product Elimination":

Products are $\sf Functor$s

Revisiting our previous diagram of $\sf\textcolor{maroon}{map}$:

we still have all the necessary parts to complete the mapping, we must simply perform product elimination in the implementation:

We can get the product $\sf{\textcolor{blue}{A} × \textcolor{blue}{X}}$ by definition of $\sf fa$

from which we can get a $\sf{\textcolor{blue}{B}}$ from the provided $\sf{\textcolor{maroon}{f}}$:

and now we have an $\sf \textcolor{blue}{X}$ and a $\sf \textcolor{blue}{B}$ with which we can construct our $\sf \textcolor{blue}{F}[\textcolor{blue}{B}]$

All we have to do is introduce the product between these two like so:

Key takeaways

A binary parametric product type is:

• a $\sf Functor$

$\sf Functor$ but not $\sf Apply$

Advancing along the hierarchy diagram, we can now use our knowledge of Product types to break the $\sf Apply$ type class. An $\sf Apply$.³ An $\sf Apply$ is anything that lets us take the product of three types in any order isomorphically. This necessitates another map which takes two arguments in the second list rather than one – $\sf\textcolor{maroon}{map2}$:

Breaking the signature down, observe that we start with a product of two type constructors over $\sf \textcolor{blue}{A}$ and $\sf \textcolor{blue}{B}$:

We want an $\sf \textcolor{blue}{F}[\textcolor{blue}{C}]$

and we will produce this $\sf \textcolor{blue}{F}[\textcolor{blue}{C}]$ by way of the provided mapping $\sf \textcolor{maroon}{f}$:

and all together this gives us the definition of $\sf\textcolor{maroon}{map2}$:

Implementing $\sf\textcolor{maroon}{map2}$ for $\sf Product$

Let's take a look at how we would go about implementing $\sf\textcolor{maroon}{map2}$. For starters, we have our (for the time being) trusty $\sf Product$ and the method signature:

We're also given $\sf fa$ and $\sf fb$ so by product elimination we get $\sf \textcolor{blue}{F}[\textcolor{blue}{A}]$ and $\sf \textcolor{blue}{F}[\textcolor{blue}{B}]$ individually from our initial product:

We know we want an $\sf \textcolor{blue}{F}[\textcolor{blue}{C}]$, so we can pencil that in as our target type:

Next, we can perform product introduction via $\sf fa$ and $\sf fb$ to yield $\sf \textcolor{blue}{X} \times \textcolor{blue}{X}$ and $\sf \textcolor{blue}{A} \times \textcolor{blue}{B}$:

and we can use the provided $\sf \textcolor{maroon}{f}$ on our new product of $\sf \textcolor{blue}{A} \times \textcolor{blue}{B}$ to get a $\sf \textcolor{blue}{C}$:

Lastly, we just need to combine our product of $\sf \textcolor{blue}{X}$s into a single $\sf \textcolor{blue}{X}$, and drop it into our type constructor to get an $\sf \textcolor{blue}{F}[\textcolor{blue}{C}]$:

To combine our $\sf x1$ and $\sf x2$ we do literally need a $\sf \textcolor{maroon}{combine}$ method, but its implementation is entirely arbitrary at this abstract level. If the types are numeric it could arithmetically combine them, or perhaps concatenate them if they're strings or some binary bytestream, we could also just select the first, or just the second, flip a coin to pick which one to select, etc – it does not matter:

and now we have a single $\sf \textcolor{blue}{X}$ as well as a $\sf \textcolor{blue}{C}$ to yield our desired $\sf \textcolor{blue}{F}[\textcolor{blue}{C}]$, thus completing the implementation of $\sf \textcolor{maroon}{map2}$

Breaking $\sf Product$

The simplest way for us to illustrate something that is a $\sf Product$ and therefore a $\sf Functor$ but is not an $\sf Apply$ is to semantically constrain our $\sf Product$.

The humorous example Nicolas provided was working with Jira labels. We can define our $\sf Product$ to be an Enum which is perfectly valid:

and use this as our $\sf \textcolor{blue}{X}$:

However, there is no longer a valid abstract definition of $\sf \textcolor{maroon}{combine}$ since $\sf \textcolor{blue}{Label}$ is closed... That is – there is no valid definition of a ticket which pertains to both the $\sf \textcolor{blue}{FrontEnd}$ and the $\sf \textcolor{blue}{BackEnd}$ for example, and so we can no longer guarantee that this kind of product can be combined:

Thus, the whole implementation falls apart as we cannot introduce a product between our $\sf c$ and $\sf x3$ since we cannot get an $\sf x3$ without somehow combining our $\sf x1$ and $\sf x2$

Key takeways

A binary parametric product type:

• is a $\sf Functor$
• is not an $\sf Apply$ if the other member is not a $\sf Semigroup$
  • $\sf \textcolor{blue}{Label}$ is not a $\sf Semigroup$ because the $\sf \textcolor{maroon}{combine}$ operation is not closed on its members

$\sf Apply$ but not $\sf Applicative$

For something to be $\sf Applicative$ it must already be an $\sf Apply$ and have an implementation of $\sf \textcolor{maroon}{pure}$. All $\sf \textcolor{maroon}{pure}$ does is wrap a value into the given (higher kinded) type constructor:

Let's take a look at how this might look for a $\sf \textcolor{blue}{Product}$:

We can see that $\sf \textcolor{maroon}{pure}$ only takes an $\sf \textcolor{blue}{A}$, so we need an aribtrary way to introduce an $\sf \textcolor{blue}{X}$. We do this by way of a method called $\sf \textcolor{maroon}{empty}$

Breaking Product

Once again, the easiest way to break $\sf Applicative$ is by way of $\sf Product$ by defining it in such a way that there is no valid implementation of $\sf \textcolor{maroon}{empty}$, e.g. replacing the arbitrary type $\sf \textcolor{blue}{X}$ with $\sf \textcolor{blue}{PosInt}$:

There is no reasonable notion of emptiness for the set of positive integers, so we cannot implement $\sf \textcolor{maroon}{empty}$ – which in turn breaks the rest of our implementation:

Key takeways

A binary parametric product type:

• is a $\sf Functor$
• is not an $\sf Apply$ if the other member is not a $\sf Semigroup$
• is not an $\sf Applicative$ if the other member is not a $\sf Monoid$
  • a $\sf Monoid$ has an associative operation and an identity element

$\sf Apply$ but not $\sf Flatmap$

$\sf FlatMap$

Given an $\sf \textcolor{blue}{F}[\textcolor{blue}{A}]$ and wanting an $\sf \textcolor{blue}{F}[\textcolor{blue}{B}]$, a $\sf FlatMap$ takes a function $\sf \textcolor{maroon}{f}$ from $\sf\textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}]$:

Deriving the implementation of $\sf \textcolor{maroon}{flatMap}$ for a $\sf \textcolor{blue}{Product}$ should be a familiar process by now. We start with our target product $\sf \textcolor{blue}{F}[\textcolor{blue}{B}]$ and work backwards:

First, leveraging our $\sf fa$, we introduce an $\sf \textcolor{blue}{X}$:

Then we map to our $\sf \textcolor{blue}{F}[\textcolor{blue}{B}]$ via $\sf \textcolor{maroon}{f}$ and perform product elimination to get a product of $\sf \textcolor{blue}{X}$s: