Cats: Essential Type Class Hierarchy Explained

Daniel Ciocîrlan

Daniel Ciocîrlan

9 min read  • 

cats scala

Share on:

Introduction

We’ll discuss the essential type classes in the Cats library, why we need them, how they’re related and how you should think about them so that you’re not tangled in all the abstractions.

Prerequisites

The code we’ll write here is for Scala 3, but with a minor adjustment it will work with Scala 2 as well.

Background

You’ve surely heard (or even read) about Cats: it’s a library for functional programming abstractions, going beyond what Scala brings with its standard library. Cats offers (offer?) a range of type classes, extension methods and general FP primitives that allow us to write very general and extensible code very quickly (if we know what we’re doing).

Cats needs to be added to your build.sbt file for us to work with it:

libraryDependencies += "org.typelevel" %% "cats-core" % "2.6.1"

Starting Easy: Semigroups and Monoids

We’ve already talked a bit about semigroups and monoids in another article. These are some of the simplest type classes in Cats.

A Semigroup is a type class granting the capability of a type to combine two values of that type and produce another value of that same type:

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

We can use Semigroups whenever we write generic code and operate with values that need to be combined:

  • Numbers
  • Strings
  • Shopping carts in an online store
  • Permissions in a data repository

Monoids are a special kind of semigroups, where besides the combination function, we also have a “neutral element” of that combination function. We call that value empty, or “zero” (with the proper quotes because zero has a special meaning in math, you know). The property is that

combine(x, empty) == x
combine(empty, x) == x

for all elements x of type A. A monoid is defined as

trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

So we have our first relationship: Monoids extend Semigroups.

Functors

We also talked about functors in another article and video. In there, we talked about why we need functors, with lots more examples. As a summary, functors describe the capability to “map” containers, such as lists, options, sets, futures, etc. The functor trait looks like this:

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

Notice it’s higher-kinded, because the types which can be “mapped” are also generic.

At this point, it’s worth mentioning that Cats has a rule of thumb when it deconstructs type classes: in general, each type class has one fundamental method. In the case of functors here, the fundamental method is map.

Monads

Monads are the sweet spot of pure FP. They encapsulate chainable computations, and we talked more about the practical side of monads and the very theoretical side of monads in other articles here on the blog, but never about monads as a type class.

For those of you who have read about Cats and experimented with monads, you know that monads have two capabilities:

  • The capability to “lift” a plain value into a monadic type, an operation known as pure
  • The capability to “chain” computations of monadic types, an operation known as flatMap or bind

The monad trait can look something like this:

trait Monad[F[_]] {
  def pure[A](a: A): F[A]
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}

You know this from real life: flatMapping lists, futures, options are all (simpler) versions of the monadic chaining capabilities.

Because Monads have pure and flatMap, we can express the much weaker map method in terms of those two:

def map[A, B](fa: F[A])(f: A => B): F[B] =
  flatMap(fa)(a => pure(f(a)))

Therefore, Monad should extend Functor, because we can implement the map method for free. So we have the type class hierarchy like this:

 Semigroup            Functor
     │                   │
     │                   │
     ▼                   ▼
  Monoid               Monad

Applicatives and Weaker Monads

The thing is, I mentioned earlier that Cats’ rule of thumb is one fundamental capability for each type class. Monad has two. Which of these two should be in a separate type class?

The main intuition of monads is the “chained” computations of FP. Therefore, the pure method should be the one to go into a separate type class. That type class is called Applicative, and it sits between Functor and Monad.

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
}

Nice. Applicative is the type class with the capability to wrap a plain value into a wrapped type. Now, here’s some kicker news for you: we’ll also move flatMap to a different type class.

Why?

Monads establish most of the equivalence between imperative programming and functional programming. An imperative program can easily be transformed into FP by creating a monadic type capable of chaining each “instruction” as a new (pure) value. “Do this, do this, and then this” becomes “new monad, flatMap to new monad, then flatMap to a final monad”.

In order to keep its promise and bridge the concept of “imperative” to FP, the Monad trait has another fundamental method that can “iterate”. That method is called tailrecM, which brings stack safety to an arbitrarily large sequence of flatMaps. The flatMap method belongs to a different type class, which bears the (perhaps uninspired) name of FlatMap (with an F):

trait FlatMap[F[_]] extends Functor[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}

Therefore, Monad extends these two and implements that map method for free:

trait Monad[F[_]] extends FlatMap[F] with Applicative[F] {
  override def map[A, B](fa: F[A])(f: A => B) = {
    flatMap(fa)(a => pure(f(a)))
  }
}

So the hierarchy looks like this:


                       Functor
  Semigroup               │
      │           ┌───────┴────────┐
      │           │                │
      ▼           ▼                ▼
   Monoid     FlatMap           Applicative
                  │                │
                  └───────┬────────┘
                          │
                          ▼
                        Monad

Semigroupals

This is one of the type classes which are harder to get into and rarely used directly.

Think of two lists. Whenever we write a for-comprehension of two lists (or a flatMap), we’re doing a cartesian product of those two lists. The concept of a cartesian product (which is not the same as a flatMap) is core to the type class called Semigroupal.

trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

Semigroupal has a method that takes two wrapped values and returns a wrapped value of tuple(s). This is the (very general) concept of a cartesian product over any type F. Semigroupal doesn’t have a parent type class in our hierarchy here.

Weaker Applicatives

Here’s where it gets tricky. Cats has a bunch of type classes that seem unnecessarily abstract and without correspondent in real life. Apply is one of them.

Apply is a weaker (but more general) applicative, and it sits between Applicative and Functor in the above diagram. It’s a higher-kinded type class (much like Applicative, Functor and Monad) which allows us to invoke a wrapped function over a wrapped value and obtain a wrapped result:

trait Apply[F[_]] extends Functor[F] {
  def ap[A, B](fab: F[A => B], fa: F[A]): F[B]
}

Now, with the ap method and the map method from Functor, we can implement the following method for free:

def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] = {
  val myFunction: A => B => (A, B) = (a: A) => (b: B) => (a, b)
  val fab: F[B => (A, B)] = map(fa)(myFunction)
  ap(fab, fb)
}

In other words, if Apply extends Functor, then it naturally extends Semigroupal as well. Now, with the product method set, we can implement a much useful method that you may have used in real life — mapN:

def mapN[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] = {
  map(product(fa, fb)) {
    case (a,b) => f(a,b)
  }
}

The mapN method not only does a (cartesian) product between two wrapped values, but it also applies a function to the elements being tupled. Our hierarchy now looks like this:

                      Functor            Semigroupal
                         │                    │
                 ┌───────┴────────┐ ┌─────────┘
 Semigroup       │                ▼ ▼
     │           │               Apply
     │           │                 │
     ▼           ▼                 │
  Monoid     FlatMap               ▼
                 │             Applicative
                 │                 │
                 └───────┬─────────┘
                         │
                         ▼
                       Monad

Error Types

Besides Applicatives which can wrap successful values of type A into a wrapped type F[A], we can also wrap error types and treat them in the same way:

trait ApplicativeError[F[_], E] extends Applicative[F] {
  def raiseError[A](error: E): F[A]
}

The raiseError method can take an undesirable, “error” value and wrap that into a wrapped type F[A]. Notice that the error type E does not appear in the result type F[A] — that’s because we treat wrapped types in the same way down the line, regardless of whether they’re successful or not, and treat the error cases later in a purely functional way if we need to.

In the same style, we have an error-enhanced monadic type as well, called MonadError:

trait MonadError[F[_], E] extends ApplicativeError[F, E] with Monad[F]

And thus, the final type class hierarchy looks like this:

                      Functor            Semigroupal
                         │                    │
                 ┌───────┴────────┐ ┌─────────┘
 Semigroup       │                ▼ ▼
     │           │               Apply
     ▼           ▼                 │
  Monoid     FlatMap               ▼
                 │             Applicative
                 │                 │
                 └───────┬─────────┤
                         ▼         │
                       Monad       │
                         │         ▼
                         │    ApplicativeError
                         │         │
                         └─────┬───┘
                               │
                               ▼
                          MonadError

Conclusion

In this article, we’ve gone over the major type classes in Cats and established the basic relationship between them. The deep reasoning behind them is complex and way outside the scope of this piece, but hopefully you got the main intuition behind most (maybe all) of the type classes and relationships above.

Obviously, the Cats course describes everything in detail, with lots of exercises and many more functionalities of Cats that we did not have time to even touch in this article — e.g. data validation, purely functional state, modes of evaluation, traversing, Kleisli, type class variance — but I hope this article gave you some essential tips on how to start looking at the core type classes so you can use them for your own projects.