projectsblogpscoaboutreading list

48 | Digest: Things that are things, but not other things

26 March, 2023 - 28 min read

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 things1 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:2

A common issue I encounter is failure to lean on the minimum-necessary type class. Implicit instances of Applicative\sf Applicative, Monad\sf Monad, Apply\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. Monad\sf Monad), implying that many of my fellow contributors also don't know what the tightest bound on their use case is, just that Applicative\sf Applicative or Monad\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:

Overview

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.

List[A]\sf{\textcolor{blue}{List}[\textcolor{blue}{A}]}

which alone is not worth breaking.

Functor\sf Functor

The Functor\sf Functor is the first category on the list we'll break by demonstrating what it is and what it is not. A Functor\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 Functor\sf Functor is an implementation of map\sf\textcolor{maroon}{map}:

def  map[A,B](f:A    B)(fa:F[A]):F[B]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} \implies \textcolor{blue}{B}) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] }

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

def  map[A,B](f:A    B)(fa: F[A]):F[B]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} \implies \textcolor{blue}{B}) (\colorbox{yellow}{fa: \textcolor{blue}{F}[\textcolor{blue}{A}]}): \textcolor{blue}{F}[\textcolor{blue}{B}] }

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

def  map[A,B](f:A    B)(fa:F[A]):F[B]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} \implies \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \colorbox{yellow}{\textcolor{blue}{F}[\textcolor{blue}{B}]} }

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

def  map[A,B]( f: A ⟹ B )(fa:F[A]):F[B]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\colorbox{yellow}{ \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B} } ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] }

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

def  map[A,B](f:AB)(fa:F[A]):F[B]\sf{ \textcolor{magenta}{def} \; \colorbox{yellow}{\textcolor{maroon}{map}}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] }

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

Function

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

type  F[A]=X ⟹ Adef  map[A,B](f:AB)(fa:F[A]):F[B]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \colorbox{yellow}{\textcolor{blue}{X} ⟹ \textcolor{blue}{A}} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad ???} \end{aligned}

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

type  F[A]=XAdef  map[A,B](f:AB)( fa: F[A]):F[B]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{X} ⟹ \textcolor{blue}{A} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) (\colorbox{yellow}{ fa: \textcolor{blue}{F}[\textcolor{blue}{A}]}): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad ???} \end{aligned}

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

type  F[A]=XAdef  map[A,B](f: A ⟹ B)(fa:F[A]):F[B]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{X} ⟹ \textcolor{blue}{A} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\colorbox{yellow}{\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad ???} \end{aligned}

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

type  F[A]=XAdef  map[A,B](f:AB)(fa:F[A]):F[B]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{X} ⟹ \textcolor{blue}{A} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \colorbox{yellow}{\textcolor{blue}{F}[\textcolor{blue}{B}]} = } \\ &\sf{\quad ???} \end{aligned}

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

type  F[A]=XAdef  map[A,B](f:AB)(fa:F[A]):F[B]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{X} ⟹ \textcolor{blue}{A} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{orange}{\quad ???} } \end{aligned}

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

type  F[A]=XAdef  map[A,B](f:AB)(fa:F[A]):F[B]=fa   andThen   f\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{X} ⟹ \textcolor{blue}{A} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{lime}{\quad \textcolor{maroon}{fa \; }andThen \textcolor{maroon}{\; f}} } \end{aligned}

yielding the correct result:

Breaking Function

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

type  F[A]=A ⟹ Xdef  map[A,B](f:AB)(fa:F[A]):F[B]=fa  andThen  f\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \colorbox{lime}{\textcolor{blue}{A} ⟹ \textcolor{blue}{X}} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \quad \textcolor{maroon}{fa \; }andThen \textcolor{maroon}{\; f}} \end{aligned}

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

type  F[A]=AXdef  map[A,B](f:AB)(fa:F[A]):F[B]=fa   andThen   f\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} ⟹ \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{orange}{\quad \textcolor{maroon}{fa \; }andThen \textcolor{maroon}{\; f}} } \end{aligned}

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

type  F[A]=ABoolean\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} ⟹ \textcolor{blue}{Boolean} } \end{aligned}

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

type  Predicate[A]=ABoolean\begin{aligned} &\sf{ type\; \textcolor{blue}{Predicate}[\textcolor{blue}{A}] = \textcolor{blue}{A} ⟹ \textcolor{blue}{Boolean} } \end{aligned}

which is not a Functor\sf Functor :).

Key takeaways

A function parameterised on its:

  • output type is a Functor\sf Functor
  • input type is not a Functor\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 Product\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:

case  class  ×[A,B](fst:A,snd:B)\begin{aligned} &\sf{ case \; class \;\textcolor{blue}{×}[\textcolor{blue}{A}, \textcolor{blue}{B}](fst: \textcolor{blue}{A}, snd: \textcolor{blue}{B}) } \end{aligned}

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

def  build[A,B](a: A,b: B):A×B=a×b\begin{aligned} &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{build}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\colorbox{yellow}{a: \textcolor{blue}{A}}, \colorbox{yellow}{b: \textcolor{blue}{B}}): \textcolor{blue}{A} × \textcolor{blue}{B} = } \\ &\sf{ \quad a × b } \end{aligned}

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

def  fst[A,B](ab:A×B):A=val  a×b=aba\begin{aligned} &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{fst}[\textcolor{blue}{A}, \textcolor{blue}{B}] (ab: \textcolor{blue}{A} × \textcolor{blue}{B}): \textcolor{blue}{A} = } \\ &\sf{ \quad val \; a × b = ab } \\ &\sf{ \quad a } \end{aligned}

Products are Functor\sf Functors

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

type  F[A]=A × Xdef  map[A,B](f:AB)(fa:F[A]):F[B]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \colorbox{yellow}{\textcolor{blue}{A} × \textcolor{blue}{X}} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad ???} \end{aligned}

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

type  F[A]=A×Xdef  map[A,B](f:AB)(fa:F[A]):F[B]= (???: B) × (???: X) \begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{lime}{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } } \end{aligned}

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

type  F[A]=A×Xdef  map[A,B](f:AB)(fa:F[A]):F[B]= val   (a × x) = fa (???:B)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{lime}{ \quad val \; (a × x) = fa } } \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  map[A,B](f:AB)(fa:F[A]):F[B]=val  (a×x)=fa val   b = f(a) (???:B)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \quad val \; (a×x) = fa } \\ &\sf{ \colorbox{lime}{ \quad val \; b = \textcolor{maroon}{f}(a) } } \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  map[A,B](f:AB)(fa:F[A]):F[B]=val  (a×x)=faval  b=f(a)(???:B)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a×\colorbox{yellow}{x}) = fa} \\ &\sf{\quad val \; \colorbox{yellow}{b} = \textcolor{maroon}{f}(a)} \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  map[A,B](f:AB)(fa:F[A]):F[B]=val  (a×x)=faval  b=f(a) b × x \begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map}[\textcolor{blue}{A}, \textcolor{blue}{B}] (\textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{B}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a×\colorbox{yellow}{x}) = fa} \\ &\sf{\quad val \; \colorbox{yellow}{b} = \textcolor{maroon}{f}(a)} \\ &\sf{ \colorbox{lime}{ \quad b × x } } \end{aligned}

Key takeaways

A binary parametric product type is:

  • a Functor\sf Functor

Functor\sf Functor but not Apply\sf Apply

Advancing along the hierarchy diagram, we can now use our knowledge of Product types to break the Apply\sf Apply type class. An Apply\sf Apply.3 An Apply\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 – map2\sf\textcolor{maroon}{map2}:

def  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] (\textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] }

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

def  map2[A,B,C](f:(A,B)C)( fa: F[A],  fb : F[B] ):F[C]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] (\textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C}) (\colorbox{yellow}{ fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] } ): \textcolor{blue}{F}[\textcolor{blue}{C}] }

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

def  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] (\textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C}) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \colorbox{yellow}{\textcolor{blue}{F}[\textcolor{blue}{C}]} }

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

def  map2[A,B,C]( f: (A, B) ⟹ C)(fa:F[A], fb:F[B]):F[C]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] (\colorbox{yellow}{ \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C}} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] }

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

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

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

type  F[A]=A × Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \colorbox{yellow}{\textcolor{blue}{A} × \textcolor{blue}{X}} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad ???} \end{aligned}

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

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

type  F[A]=A×Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=(???: C) × (???: X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{ \colorbox{lime}{\quad (???: \textcolor{blue}{C}) × (???: \textcolor{blue}{X})} } \end{aligned}

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

type  F[A]=A×Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]= val   (a × x1) = fa  val   (b × x2) = fb (???:C)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{ \colorbox{lime}{ \quad val \; (a × x1) = fa } } \\ &\sf{ \colorbox{lime}{ \quad val \; (b × x2) = fb } } \\ &\sf{ \quad (???: \textcolor{blue}{C}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval   c = f(a, b)(???:C)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\colorbox{lime}{\sf{\quad val \; c = f(a, b)}} \\ &\sf{ \quad (???: \textcolor{blue}{C}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval  c=f(a,b)(???: C)×(???: X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \colorbox{yellow}{\textcolor{blue}{F}[\textcolor{blue}{C}]} = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\sf{\quad val \; c = f(a, b)} \\ &\sf{ \quad (\colorbox{yellow}{???: \textcolor{blue}{C}}) × (\colorbox{yellow}{???: \textcolor{blue}{X}}) } \end{aligned}

To combine our x1\sf x1 and x2\sf x2 we do literally need a combine\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:

type  F[A]=A×Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval  c=f(a,b)val   x3 = combine(x1, x2)(???:C)×(???:X)def  combine[X](lhs:X,rhs:X):X=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\sf{\quad val \; c = f(a, b)} \\ &\sf{\colorbox{lime}{\quad val \; x3 = combine(x1, x2)}} \\ &\sf{ \quad (???: \textcolor{blue}{C}) × (???: \textcolor{blue}{X}) } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{X}] ( lhs: \textcolor{blue}{X}, rhs: \textcolor{blue}{X} ): \textcolor{blue}{X} = \; ??? } \end{aligned}

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

type  F[A]=A×Xdef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval  c=f(a,b)val  x3=combine(x1,x2)c × x3def  combine[X](lhs:X,rhs:X):X=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\sf{\quad val \; c = f(a, b)} \\ &\sf{\quad val \; x3 = combine(x1, x2)} \\ &\sf{ \quad \colorbox{lime}{c × x3} } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{X}] ( lhs: \textcolor{blue}{X}, rhs: \textcolor{blue}{X} ): \textcolor{blue}{X} = \; ??? } \end{aligned}

Breaking Product\sf Product

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

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

enum  Label:case  FrontEndcase  BackEndcase  Bugcase  Feature\begin{aligned} &\sf enum \; \textcolor{blue}{Label}: \\ &\sf \quad case \; \textcolor{blue}{FrontEnd} \\ &\sf \quad case \; \textcolor{blue}{BackEnd} \\ &\sf \quad case \; \textcolor{blue}{Bug} \\ &\sf \quad case \; \textcolor{blue}{Feature} \\ \end{aligned}

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

type  F[A]=A×Labeldef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval  c=f(a,b)val  x3=combine(x1,x2)c×x3def  combine[Label]( lhs: Label, rhs: Label ):Label=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \colorbox{lime}{\textcolor{blue}{Label}} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\sf{\quad val \; c = f(a, b)} \\ &\sf{\quad val \; x3 = combine(x1, x2)} \\ &\sf{ \quad c × x3 } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\colorbox{lime}{\textcolor{blue}{Label}}] (\colorbox{lime}{ lhs: \textcolor{blue}{Label}, rhs: \textcolor{blue}{Label} } ): \colorbox{lime}{\textcolor{blue}{Label}} = \; ??? } \end{aligned}

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

type  F[A]=A×Labeldef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval  c=f(a,b)val  x3=combine(x1,x2)c×x3 def   combine[Label] ( lhs: Label, rhs: Label ): Label =   ??? \begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{Label} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\sf{\quad val \; c = f(a, b)} \\ &\sf{\quad val \; x3 = combine(x1, x2)} \\ &\sf{ \quad c × x3 } \\ \\ &\sf{ \colorbox{orange}{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{Label}] ( lhs: \textcolor{blue}{Label}, rhs: \textcolor{blue}{Label} ): \textcolor{blue}{Label} = \; ??? } } \end{aligned}

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

type  F[A]=A×Labeldef  map2[A,B,C](f:(A,B)C)(fa:F[A], fb:F[B]):F[C]=val  (a×x1)=faval  (b×x2)=fbval  c=f(a,b)val   x3 = combine(x1, x2) c × x3  def   combine[Label] ( lhs: Label, rhs: Label ): Label =   ??? \begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{Label} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{map2}[\textcolor{blue}{A}, \textcolor{blue}{B}, \textcolor{blue}{C}] ( \textcolor{maroon}{f}: (\textcolor{blue}{A}, \textcolor{blue}{B}) ⟹ \textcolor{blue}{C} ) ( fa: \textcolor{blue}{F}[\textcolor{blue}{A}], \ fb : \textcolor{blue}{F}[\textcolor{blue}{B}] ): \textcolor{blue}{F}[\textcolor{blue}{C}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{\quad val \; (b × x2) = fb} \\ &\sf{\quad val \; c = f(a, b)} \\ &\colorbox{orange}{\sf{\quad val \; x3 = combine(x1, x2)}} \\ &\sf{ \colorbox{orange}{ \quad c × x3 } } \\ \\ &\sf{ \colorbox{orange}{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{Label}] ( lhs: \textcolor{blue}{Label}, rhs: \textcolor{blue}{Label} ): \textcolor{blue}{Label} = \; ??? } } \end{aligned}

Key takeways

A binary parametric product type:

  • is a Functor\sf Functor
  • is not an Apply\sf Apply if the other member is not a Semigroup\sf Semigroup

    • Label\sf \textcolor{blue}{Label} is not a Semigroup\sf Semigroup because the combine\sf \textcolor{maroon}{combine} operation is not closed on its members

Apply\sf Apply but not Applicative\sf Applicative

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

def  pure[A](a:A):F[A]\begin{aligned} \sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{F}[\textcolor{blue}{A}] } \end{aligned}

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

type  F[A]=A×Xdef  pure[A](a:A):F[A]=(???:A)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{F}[\textcolor{blue}{A}] = } \\ &\sf{\quad (???: \textcolor{blue}{A}) × (???: \textcolor{blue}{X})} \end{aligned}

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

type  F[A]=A×Xdef  pure[A](a:A):F[A]=a×emptydef  empty:X=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{F}[\textcolor{blue}{A}] = } \\ &\sf{\quad a × empty} \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{empty}: \textcolor{blue}{X} = \; ??? } \end{aligned}

Breaking Product

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

type  F[A]=A×PosIntdef  pure[A](a:A):F[A]=a×emptydef  empty:PosInt=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \colorbox{lime}{\textcolor{blue}{PosInt}} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{F}[\textcolor{blue}{A}] = } \\ &\sf{\quad a × empty} \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{empty}: \colorbox{lime}{\textcolor{blue}{PosInt}} = \; ??? } \end{aligned}

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

type  F[A]=A×PosIntdef  pure[A](a:A):F[A]=a×empty def   empty: PosInt =   ??? \begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{PosInt} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{F}[\textcolor{blue}{A}] = } \\ &\sf{\quad a × empty} \\ &\sf{ \colorbox{orange}{ \textcolor{magenta}{def} \; \textcolor{maroon}{empty}: \textcolor{blue}{PosInt} = \; ??? } } \end{aligned}

Key takeways

A binary parametric product type:

  • is a Functor\sf Functor
  • is not an Apply\sf Apply if the other member is not a Semigroup\sf Semigroup
  • is not an Applicative\sf Applicative if the other member is not a Monoid\sf Monoid

    • a Monoid\sf Monoid has an associative operation and an identity element

Apply\sf Apply but not Flatmap\sf Flatmap

FlatMap\sf FlatMap

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

def  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] }

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

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]= (???: B) × (???: X) \begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{lime}{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } } \end{aligned}

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

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]= val   (a × x1) = fa (???:B)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{ \colorbox{lime}{ \quad val \; (a × x1) = fa } } \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]=val  (a×x1)=fa val   fb = f(a) (???:B)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{ \colorbox{lime}{ \quad val \; fb = \textcolor{maroon}{f}(a) } } \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \end{aligned}

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]=val  (a×x1)=fa val   (b × x2) = f(a) (???:B)×(???:X)\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{ \colorbox{lime}{ \quad val \; (b × x2) = \textcolor{maroon}{f}(a) } } \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \end{aligned}

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

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]=val  (a×x1)=faval  (b×x2)=f(a) val   x3 = combine(x1, x2) (???:B)×(???:X)def  combine[X](lhs:X,rhs:X):X=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{ \quad val \; (b × x2) = \textcolor{maroon}{f}(a) } \\ &\sf{ \colorbox{lime}{ \quad val \; x3 = \textcolor{maroon}{combine}(x1, x2) } } \\ &\sf{ \quad (???: \textcolor{blue}{B}) × (???: \textcolor{blue}{X}) } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{X}] ( lhs: \textcolor{blue}{X}, rhs: \textcolor{blue}{X} ): \textcolor{blue}{X} = \; ??? } \end{aligned}

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

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]=val  (a×x1)=faval  (b×x2)=f(a)val  x3=combine(x1,x2)b×x3def  combine[X](lhs:X,rhs:X):X=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{ \quad val \; (b × x2) = \textcolor{maroon}{f}(a) } \\ &\sf{ \quad val \; x3 = \textcolor{maroon}{combine}(x1, x2) } \\ &\sf{ \quad b × x3 } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{X}] ( lhs: \textcolor{blue}{X}, rhs: \textcolor{blue}{X} ): \textcolor{blue}{X} = \; ??? } \end{aligned}

Breaking Product

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

type  F[A]=A×Xdef  flatMap[A,B](f:AF[B])(fa:F[A]):F[B]=val  (a×x1)=faval  (b×x2)=f(a)val  x3=combine(x1,x2)b×x3def  combine[X](lhs:X,rhs:X):X=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{X} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{F}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{F}[\textcolor{blue}{A}]): \textcolor{blue}{F}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{ \quad val \; (b × x2) = \textcolor{maroon}{f}(a) } \\ &\sf{ \quad val \; x3 = \textcolor{maroon}{combine}(x1, x2) } \\ &\sf{ \quad \colorbox{yellow}{b} × x3 } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{X}] ( lhs: \textcolor{blue}{X}, rhs: \textcolor{blue}{X} ): \textcolor{blue}{X} = \; ??? } \end{aligned}

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

type  F[A]=X\begin{aligned} &\sf{ type\; \textcolor{blue}{F}[\textcolor{blue}{A}] = \textcolor{blue}{X} } \end{aligned}

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

type  Weight[A]=PosIntdef  combine[PosInt](lhs:PosInt,rhs:PosInt):PosInt=  ???\begin{aligned} &\sf{ type\; \textcolor{blue}{Weight}[\textcolor{blue}{A}] = \textcolor{blue}{PosInt} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{combine}[\textcolor{blue}{PosInt}] ( lhs: \textcolor{blue}{PosInt}, rhs: \textcolor{blue}{PosInt} ): \textcolor{blue}{PosInt} = \; ??? } \end{aligned}

Key takeways

A binary parametric product type:

  • is a Functor\sf Functor
  • is not an Apply\sf Apply if the other member is not a Semigroup\sf Semigroup
  • is not an Applicative\sf Applicative if the other member is not a Monoid\sf Monoid
  • is not a FlatMap\sf FlatMap if the Apply\sf Apply is of a Phantom Type

Applicative\sf Applicative but not Monad\sf Monad

We've introduced all the fundamental operations of a Monad\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 Applicative\sf Applicative to be a Monad\sf Monad, it must implement flatMap\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:

type  Flagged[A]=A×Booleandef  pure[A](a:A):Flagged[A]=a×false\begin{aligned} &\sf{ type\; \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{Boolean} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = } \\ &\sf{ \quad a × \colorbox{yellow}{false} } \end{aligned}

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

type  Flagged[A]=A×Booleandef  pure[A](a:A):Flagged[A]=a×falsedef  flatMap[A,B](f:AFlagged[B])(fa:Flagged[A]):Flagged[B]=val  (a×x1)=faval  (b×x2)=f(a)val  x3=x1 || x2b×x3\begin{aligned} &\sf{ type\; \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{Boolean} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = } \\ &\sf{ \quad a × false } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{Flagged}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{Flagged}[\textcolor{blue}{A}]): \textcolor{blue}{Flagged}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (a × x1) = fa} \\ &\sf{ \quad val \; (b × x2) = \textcolor{maroon}{f}(a) } \\ &\sf{ \quad val \; x3 = \colorbox{yellow}{x1 || x2} } \\ &\sf{ \quad b × x3 } \\ \end{aligned}

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

type  Flagged[A]=Boolean\begin{aligned} &\sf{ type\; \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = \textcolor{blue}{Boolean} } \end{aligned}

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

type  Flagged[A]=A ×Booleandef  pure[A](a:A):Flagged[A]=a ×falsedef  flatMap[A,B](f:AFlagged[B])(fa:Flagged[A]):Flagged[B]=val  (a×x1)=faval  (b×x2)=f(a)val  x3=x1    x2b×x3\begin{aligned} &\sf{ type\; \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = \colorbox{orange}{\textcolor{blue}{A} ×} \textcolor{blue}{Boolean} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{Flagged}[\textcolor{blue}{A}] = } \\ &\sf{ \quad \colorbox{orange}{a ×} false } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{Flagged}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{Flagged}[\textcolor{blue}{A}]): \textcolor{blue}{Flagged}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (\colorbox{orange}{a} × x1) = fa} \\ &\sf{ \quad val \; (\colorbox{orange}{b} × x2) = \textcolor{maroon}{f}(a) } \\ &\sf{ \quad val \; x3 = x1 \; || \; x2 } \\ &\sf{ \quad \colorbox{orange}{b} × x3 } \\ \end{aligned}

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

type  Flag[A]=Booleandef  pure[A](a:A):Flag[A]=false\begin{aligned} &\sf{ type\; \textcolor{blue}{Flag}[\textcolor{blue}{A}] = \textcolor{blue}{Boolean} } \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{Flag}[\textcolor{blue}{A}] = false } \end{aligned}

Key takeways

A binary parametric product type:

  • is a Functor\sf Functor
  • is not an Apply\sf Apply if the other member is not a Semigroup\sf Semigroup
  • is not an Applicative\sf Applicative if the other member is not a Monoid\sf Monoid
  • is not a FlatMap\sf FlatMap if the Apply\sf Apply is of a Phantom Type
  • is not a Monad\sf Monad if the Applicative\sf Applicative is of a Phantom Type

FlatMap\sf FlatMap but not Monad\sf Monad

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

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

type  Weighted[A]=A×PosIntdef  pure[A](a:A):Weighted[A]=a×   ???def  flatMap[A,B](f:AWeighted[B])(fa:Weighted[A]):Weighted[B]=val  (b×x1)=faval  (b×x2)=f(a)val  x3=x1  +  x2b×x3\begin{aligned} &\sf{ type\; \textcolor{blue}{Weighted}[\textcolor{blue}{A}] = \textcolor{blue}{A} × \textcolor{blue}{PosInt} } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{pure}[\textcolor{blue}{A}] (a: \textcolor{blue}{A}): \textcolor{blue}{Weighted}[\textcolor{blue}{A}] = a \colorbox{orange}{× \; ???} } \\ \\ &\sf{ \textcolor{magenta}{def} \; \textcolor{maroon}{flatMap}[\textcolor{blue}{A}, \textcolor{blue}{B}] ( \textcolor{maroon}{f}: \textcolor{blue}{A} ⟹ \textcolor{blue}{Weighted}[\textcolor{blue}{B}] ) (fa: \textcolor{blue}{Weighted}[\textcolor{blue}{A}]): \textcolor{blue}{Weighted}[\textcolor{blue}{B}] = } \\ &\sf{\quad val \; (b × x1) = fa} \\ &\sf{ \quad val \; (b × x2) = \textcolor{maroon}{f}(a) } \\ &\sf{ \quad val \; x3 = x1 \; \colorbox{lime}{+} \; x2 } \\ &\sf{ \quad b × x3 } \end{aligned}

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

Key takeways

A binary parametric product type:

  • is a Functor\sf Functor
  • is not an Apply\sf Apply if the other member is not a Semigroup\sf Semigroup
  • is not an Applicative\sf Applicative if the other member is not a Monoid\sf Monoid
  • is not a FlatMap\sf FlatMap if the Apply\sf Apply is of a Phantom Type
  • is not a Monad\sf Monad if the Applicative\sf Applicative is of a Phantom Type
  • is not a Monad\sf Monad if a FlatMap\sf FlatMap if the other member is not a Monoid\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!


  1. nrinaudo.github.io/things-that-are-things

  2. typelevel.org

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