Cats (Introducing Typelevel Scala into an OO Environment)

(Examples can be found on GitHub)

Last time, we discovered Type Classes and how they give us more power to build extensible software than sub class polymorphic trees can give us. Here we introduce the Cats library to use a production quality library instead of the Adder and Chainer classes from the previous post.

We'll need the following imports from the cats library:

import cats.Monoid
import cats.Monad
import cats.implicits._

and to recall our Team definition:

case class Team[Type](members: List[Type])

The Monoid Type Class

Recall the Adder trait described the process of adding two containers of the same type together to create a new container of that type. This is the basic idea for a structure in category theory called a Monoid. A full treatment of a Monoid is beyond the scope of this post; the important thing here is they describe semantics for adding members of other types together.

In the cats library, a Monoid for our unstructured Team data is defined thus:

implicit def adder[Arg]: Monoid[Team[Arg]] =
  new Monoid[Team[Arg]]{
    override def empty: Team[Arg] = Team(Nil)
    override def combine(
        left: Team[Arg], right: Team[Arg]): Team[Arg] = {
      val newMembers = left.members ++ right.members

A Monoid has two operations, empty and combine, where empty is the identity element under the combine operation. In other words empty is a value, e, that when combined with any other value, v, returns v. Monoid replaces our Adder trait from the previous post. Our structured Team would have Monoid:

implicit def adder[Arg]: Monoid[Team[Arg]] =
  new Monoid[Team[Arg]]{
    override def empty: Team[Arg] = Team(Nil)
    override def combine(
        left: Team[Arg], right: Team[Arg]): Team[Arg] = {
      val (lead1, indi1) = left.members.splitAt(2)
      val (lead2, indi2) = right.members.splitAt(2)
      val newMembers = lead1 ++ lead2 ++ indi1 ++ indi2

Note, the empty value is the same for both cases. This is often the case for multiple Monoids over the same data structure; no matter how you combine elements, the identity is trivially applied.

The Monad Type Class

Now, we shift our focus to the Chainer trait from the previous post. This trait described how to sort of flatten a nesting of containers for instance, a Team[Team[_]] into a Team[_]. This is the basic operation behind the Monad. Again, we're not interested in figuring out Monads in detail; we're just trying to use a library in our work.

With Cats we'll have:

implicit def chainer: Monad[Team] = new Monad[Team]{
  override def flatMap[Arg, Ret](
      team: Team[Arg])(f: Arg => Team[Ret]): Team[Ret] = {
    val newMembers = team.members.flatMap(f(_).members)

for our unstructred Monad and our structured would look like:

implicit def chainer: Monad[Team] = new Monad[Team]{
  override def flatMap[Arg, Ret](
      team: Team[Arg])(f: Arg => Team[Ret]): Team[Ret] = {
    val (leaders, individuals) ={member =>
      val mems = f(member).members
        leaders.flatMap {x=>x} ++

Monads add the flatMap (also called bind or >>= in some circles) operation to a data type. flatMap describes how to take a value of Team and a function which maps a member to a Team to produce another Team. It is a flattening operation. These are important as they describe data flow and functional composition through a system. To get the individual contributors from their Directors on could:

case class Director(name: String)
case class Manager(name: String)
case class Individual(name: String)
val directors: Team[Director] = ???
def managers(director: Director): Team[Managers] = ???
def individualContributors(manager: Manager): Team[Individual] = ???
val individuals = directors >>= (managers) >>= (individualContributors)

Then swapping out different functionality is simply recombining your function calls around your Monadic chain.

Monoids and Monads are simple to use. They describe operations to combine and process data as simple, type safe functional chains.

Introducing Typelevel Scala into an OO Environment

These posts seek to describe a process by which a Scala dev can reasonably (responsibly) introduce Functional Programming (FP) in Scala into an Object Oriented (OO) Java development atmosphere. It can also serve as an entry point for an OO dev into the Scala community. They are based on a talk I gave at the Typelevel Summit in Philadelphia in 2016. Here are the slides and index cards from that talk. A video is available on YouTube.

We'll transform from OO paradigms to FP paradigms through five key ideas:

  1. Immutability as Default
  2. Combinators over loops, null & throw
  3. Case Classes for auto-encapsulation
  4. Objects are not Coroutines
  5. Type Classes over Subclasses

And provide practical examples using 3 libraries:

  1. Monocle
  2. Argonaut
  3. Cats

Each of these ideas builds upon the last and by the end we'll have a solid foundation for introducing FP and Category Theory without even saying any of the "M-words".

Before starting it is important to note that many of the people who develop software do not have Computer Science (CS) degrees. They will sometimes have a degree in another science or engineering discipline. Often, they will have no degree at all. An extension of this idea is you don't need a degree to define flatMap.

This fact is important to us because, the vernacular of CS is different from the vernacular of other disciplines. On the other hand, we are assuming an audience of OO developers so, some CS terminology is ok and indeed will be present throughout. Wherever OO words fail us, we will find "plain old English" ways of describing idioms and ideas. We will be coaching usage, strategies and tactics not terms and vocabulary.

Type Class over Coupled Monads

Scala has support for built in language level Monads. They go a little something like this:

case class MyMonad[Type](item: Type){
  def map[Ret](f: Type => Ret): MyMonad[Ret] = ???
  def flatMap[Ret](f: Type => MyMonad[Ret]): MyMonad[Ret] = ??? 

The issue here is the Monadic flatMap (bind, >>=, whatever) is coupled to the data structure; there is a single operation which defines the Monadic functionality across all the code which uses the data structure. For instance, the Buffer flatMap flattens the Buffer[Buffer] into a Buffer by concatenating the first with the second with the third ... This flattening style is the only flattening style Buffer provides with Scala's built in, for comprehension Monadic chaining. This is very limiting.

If one wanted a different kind of flattening such as a round-robin: taking the first element from each Buffer, then the second from each ... One would need to implement their own Buffer structure and bake into that new Buffer a flatMap operation detailing the round-robin. Now, there are two separate Buffer data structures presenting two separate methods of Monadic chaining. Each function which accepts a Buffer needs to enforce which Buffer type it needs to ensure the flatMap provides the necessary functionality. Type Classes provide a solution to this issue.

Cats to the rescue

The Typelevel Cats library defines a Monad Type Class and implicits for syntax. Keeping to Buffer for our example: we would have two Monads over Buffer which look like:

import scala.collection.mutable.Buffer
import cats.Monad
import cats.implicits._

val mMonad = new Monad[Buffer]{
  override def pure[Type](items: Type): Buffer[Type] = pure(Seq(items))
  def pure[Type](items: Seq[Type]): Buffer[Type] = Buffer(items: _*)
  override def flatMap[Arg, Ret](c: Buffer[Arg])(f: Arg => Buffer[Ret]): Buffer[Ret] = {
val rrMonad = new Monad[Buffer]{
  override def pure[Type](items: Type): Buffer[Type] = pure(Seq(items))
  def pure[Type](items: Seq[Type]): Buffer[Type] = Buffer(items: _*)
  override def flatMap[Arg, Ret](c: Buffer[Arg])(f: Arg => Buffer[Ret]): Buffer[Ret] = {
    val mapped =
    val tupled = => (i, i.size))
    val max = tupled.unzip._2.max
    val seq = (0 to max).flatMap{index =>
        case (seq, size) if size > index => seq(index)

Then to use them:

object simple{
  implicit val monad = mMonad
  def apply(values: Seq[Int]){
    val mMulti = mMonad.pure(values) >>={ int =>
      mMonad.pure((0 to int))
object roundRobin{
  implicit val monad = rrMonad
  def apply(values: Seq[Int]){
    val rrMulti = rrMonad.pure(values) >>={int =>
      rrMonad.pure((0 to int))
val values = Seq(1,2,3,4,5)

And that's it! Ad-hoc Monadic chaining any way you'd like without redefining classes or parameterized methods.

D3js defines a Functor over the DOM

D3js is a wonderful library for parsing datasets and manipulating the DOM based on what was parsed. With the right frame of mind, even complex data manipulations into the DOM become simple enough to implement in short order. The code here is written in javascript.

Those unfamiliar with the library can visit the D3js website for a set of very nice tutorials to get started.

Those unfamiliar with Category theory and Functors can find myriad resources on the internet which describe the concepts. In my opinion, the best treatment of Category Theory is in the book Categories for the Working Mathematician written by Saunders Mac Lane. The first few chapters are all that's needed here.

The basic idea behind D3js is you select one or many DOM elements and manipulate the set of them without cluttering your code with loops and control statements. Take:

<ul id='list'>
  <li id='idx1'>first</li>
  <li id='idx2'>second</li>
  <li id='idx3'>third</li>
  <li id='idx4'>fourth</li>

This represents the array ['first','second','third','fourth']. This is the example we will use to show how D3js can be seen as a Functor.

A Category over the DOM

We will define a Category over the DOM by taking the DOM elements as the objects and containment as the arrows.

Given an arrow, f, the domain is the parent DOM element and the codomain is the child DOM element. So, an arrow f: a -> b shows that b is a child of a. Trivially, the identity arrow maps DOM elements to themselves, f: a -> a.

These arrows are composable. Given an arrow, f: a -> b, and an arrow, g: b -> c, an arrow, h: a -> c, can be produced by first applying f to a then applying g to b = f(a); h = g(f). This would show a grandchild relationship within the DOM.

This composition is associative. Take arrows, f: a -> b, g: b -> c, h: c -> d. Let z = h(g(f)), y = g(f), w = h(g). z = h(y) and z = w(f). The grandchild's child is the same as the child's grandchild. This is the great-grandchild relationship within the DOM.

This composition obeys the left and right unit laws. Take f: a -> b, f(id(a)) = f(a) = b. id(f(a)) = id(b) = b. is a Functor over the DOM

The first part to discovering a Functor is to define a unit function which maps an element of the DOM, a, to the Functor, F(a). In D3js this function is

var element = document.getElementById('list');
var selection =; returns a d3 selector object which wraps the DOM element in argument. It "lifts" the DOM element into the d3 selector.

Next we need a function which maps arrows in the DOM, f: a -> b, to arrows in the Functor, F(a) -> F(b). We took our arrows to refer to containment; getElementsByTagName will serve as our f.

var element = document.getElementById('list');
var selection =;

var childElement = element.getElementsByTagName('li')[0];
var childText = childElement.textContent;
var child ={
  var current = this.getElementsByTagName('li')[0];
  return current;

var same = childText === child.text();
  alert('It didn\'t work!');

Category Theory: Cheat Sheet

I have found Category Theory has increased my productivity as a programmer more than any other mathematic tool at my disposal. This is my cheat sheet. 


  • Objects: a, b, c,...  
  • Arrows: f, g, h,...  
  • Domain: for each arrow, f, there is an object a = dom f 
  • Codomain: for each arrow, f, there is an object b = cod f 

A Metacategory is a Metagraph plus

  • Identity: for each object, a, there is an arrow f: a -> a
  • Composition: arrows, <f, g>, where dom g = cod f, admit an arrow h: dom f - > cod g
  • Composition is associatve
  • Composition obeys left and right unit laws 

A Category is an interpretation of a Metacategory within Set Theory. 


A Functor, T: C - > B, is a morphism of categories.  

  • Object function: mapping objects c in C to objects Tc in B
  • Arrow function: mapping arrows f in C to arrows Tf in B where the unit and composition are preserved
  • T is Covariant if for each arrow f: a -> b in C, Tf: Ta -> Tb in B
  • T is Contravariant if for each arrow f: a -> b in C, Tf: Tb -> Ta (arrows are reversed).
  • T is an Endofunctor if B = C

A Natural Transformation, t: S -*> T, is a morphism of Functors, T: C -> B. 

  • Each object c in C yields an arrow, tc: Sc -> Tc, in B
  • Each arrow f: a -> b in C holds tb(Sf(Sc)) = tb(Sb) = Tb 

A Monad in a Category, C, is an endofunctor, T, with two Natural Transformations; e: Id(C) -*> T, m: T(T) -*> T.

  • m(Tm) = m(mT)
  • m(Te) = m(eT) = Id(T)


A Monic is an arrow m: a -> b in a Category, C, that is left cancellable. 

  • Given parallel arrows f, g: d -> a, m(f) = m(g) implies f = g

An Epi is an arrow h: a -> b in a Category, C, that is right cancellable. 

  • Given parallel arrows f, g: b -> c, f(h)  = g(h)  implies f = g. 


An Idempotent is an arrow, f: b -> b, where f(f) = f. 

An Initial object, a, of a Category, C, yields for each object, c, in C exactly one arrow f: a -> c. 

A Terminal object, a, of a Category, C, yields for each object, c,  in C exactly one arrow f: c -> a.  


A Monoid is a Category with a single object.  

A Groupoid is a Category, C, where for each arrow, f, in C there is an inverse of f. 


A Dual Category, D, of a Category, C, is C with all arrows reversed

  • An arrow, f: a -> b, in C yields an arrow, g: b -> a, in D.