# Digest: Things that are things, but not other things

- Published on
- ∘ 36 min read ∘ ––– views

## Previous Article

## Next Article

# 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*^{1} 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

notthe 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:^{2}

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":

### $\sf Functor$s

Products areRevisiting 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$.^{3} 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}$:

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

ImplementingLet'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}$

## $\sf Product$

BreakingThe 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*

- a $\sf Monoid$ has an associative operation

## $\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:

We use a handy-dandy $\sf\textcolor{maroon}{combine}$ to go from our $\sf \textcolor{blue}{X} × \textcolor{blue}{X}$ product to a single $\sf \textcolor{blue}{X}$:

And finally, complete the implementation by returning the target product $\sf b × x3$:

### Breaking Product

Our point of entry here is the target type $\sf \textcolor{blue}{B}$

Working backwards from here, we see that we derive $\sf b$ from $\sf fa$ and $\sf fa$ from our type $\sf \textcolor{blue}{F}[\textcolor{blue}{A}]$. Well, what if we did something dastardly and decided that our type $\sf \textcolor{blue}{F}[\textcolor{blue}{A}]$ was no longer a product and instead just

This feels like cheating, but such a type is legal and exists. They're called "Phantom Types." A practical example might again use the $\sf \textcolor{blue}{PosInt}$ in place of $\sf \textcolor{blue}{X}$ and thus our type $\sf \textcolor{blue}{F}[\textcolor{blue}{A}]$ might be thought of instead as $\sf \textcolor{blue}{Weight}$ causing the $\sf FlatMap$ to break down accordingly:

### 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$
- is not a $\sf FlatMap$ if the $\sf Apply$ is of a Phantom Type

## $\sf Applicative$ but not $\sf Monad$

We've introduced all the fundamental operations of a $\sf Monad$ at this point, so all that's left to do is devise clever scenarios for which these operations are invalid for our chosen type. For an $\sf Applicative$ to be a $\sf Monad$, it must implement $\sf \textcolor{maroon}{flatMap}$, so let's make that impossible.

A perfectly valid and even common pattern we might encounter would be the product of some data as well as a boolean flag to indicate some state:

Our implementation of $\sf \textcolor{maroon}{flatMap}$ then becomes:

And once again abusing Phantom Types, suppose we stripped our type constructor of is Product nature, reducing it to just a $\sf \textcolor{blue}{Boolean}$:

Backtracking from $\sf \textcolor{blue}{B}$ again, we get the following:

which breaks $\sf \textcolor{maroon}{flatMap}$ and leaves us with just our type which is now more of a $\sf \textcolor{blue}{Flag}$ rather than a $\sf \textcolor{blue}{Flagged}$ since it has nothing *to flag* anymore.

### 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$
- is not a $\sf FlatMap$ if the $\sf Apply$ is of a Phantom Type
- is not a $\sf Monad$ if the $\sf Applicative$ is of a Phantom Type

## $\sf FlatMap$ but not $\sf Monad$

And finally, the last leg of the journey requires illustrating how a thing which is pretty much everything else cannot be a $\sf Monad$.

We've broken $\sf \textcolor{maroon}{pure}$ already, so we'll just do that again here by swapping out our $\sf \textcolor{blue}{Flagged}$ type with something we know cannot be $\sf \textcolor{maroon}{combine}$d since it has no $\sf \textcolor{maroon}{empty}$ such as $\sf \textcolor{blue}{Weighted}$:

Right away, this breaks $\sf \textcolor{maroon}{pure}$ and we have no way to lift an $\sf \textcolor{blue}{A}$ into a Monoidal $\sf \textcolor{blue}{Weighted}$:

### 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$
- is not a $\sf FlatMap$ if the $\sf Apply$ is of a Phantom Type
- is not a $\sf Monad$ if the $\sf Applicative$ is of a Phantom Type
- is not a $\sf Monad$ if a $\sf FlatMap$ if the other member is not a $\sf Monoid$.

## Conclusion

And there we have it – a detailed breakdown of why some things are things but not other things – chock-full of hopefully-not-too-contrived counter examples!

## Footnotes

If it wasn't obvious how dreadful the documentation surrounding the cats abstractions are from the very first Typelevel diagram – they define $\sf Apply$ as a just "$\sf Applicative$ modulo pure." This definition should make sense by the end of this post, but without that comprehensive knowledge just yet, it SUCKS. ↩