Scala Cats comes with a rich set of typeclasses, each of which “owns” a well-defined autonomous problem space. Many of those typeclasses are correlated and some are extended from others.

In this blog post, we’re going to give an at-a-glance hierarchical view of some of the most common Cats typeclasses. For brevity, we’ll skip discussions re: their corresponding mathematical laws, which can be found in many relevant tech docs. Our focus will be more on highlighting the correlations among these typeclasses.

Common typeclass hierarchy

For the impatient, below is a diagram highlighting the hierarchical correlation.

Semigroup and Monoid

Let’s start with the simplest ones, Semigroup and Monoid.

Semigroup comes with the abstract method combine to be implemented with the specific “combine” computational logic such as the addition of integers, union of sets, etc.

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

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

Note that Monoid simply supplements Semigroup with empty as the “zero” or “identity” element, allowing aggregating operations of arbitrarily many elements (e.g. summation of numbers from an initial 0).

Example:

implicit def setSemigroup[A]: Semigroup[Set[A]] =
  new Semigroup[Set[A]] {
    def combine(s1: Set[A], s2: Set[A]) = s1 union s2
  }

// Or, using SAM for brevity
// implicit def setSemigroup[A]: Semigroup[Set[A]] = _ union _

val setSG = implicitly[Semigroup[Set[Char]]]
setSG.combine(Set('a', 'b'), Set('c'))
// Set('a', 'b', 'c')

implicit def setMonoid[A](implicit sg: Semigroup[Set[A]]): Monoid[Set[A]] =
  new Monoid[Set[A]] {
    def combine(s1: Set[A], s2: Set[A]) = sg.combine(s1, s2)
    def empty = Set()
  }

val setM = implicitly[Monoid[Set[Char]]]
List(Set('a','b'),Set('c'),Set('d','e')).
  foldLeft(setM.empty)(setM.combine(_, _))
// HashSet('e', 'a', 'b', 'c', 'd')

SemigroupK and MonoidK

With a similar correlation, SemigroupK and MonoidK are the higher-kinded version of Semigroup and Monoid, respectively. SemigroupK combines values within a given context and MonoidK ensures the existence of an “empty” context.

trait SemigroupK[F[_]] {
  def combineK[A](x: F[A], y: F[A]): F[A]
}

trait MonoidK[F[_]] extends SemigroupK[F] {
  def combineK[A](x: F[A], y: F[A]): F[A]
  def empty[A]: F[A]
}

Example:

implicit val listSemigroupK: SemigroupK[List] =
  new SemigroupK[List] {
    def combineK[A](ls1: List[A], ls2: List[A]) = ls1 ::: ls2
  }

val listSGK = implicitly[SemigroupK[List]]
listSGK.combineK(List(1,2), List(3))
// List(1, 2, 3)

implicit def listMonoidK(implicit sgk: SemigroupK[List]): MonoidK[List] =
  new MonoidK[List] {
    def combineK[A](ls1: List[A], ls2: List[A]) = sgk.combineK(ls1, ls2)
    def empty[A] = List.empty[A]
  }

val listMK = implicitly[MonoidK[List]]
List(List(1,2),List(3),List(4,5)).foldLeft[List[Int]](listMK.empty)(listMK.combineK(_, _))
// List(1, 2, 3, 4, 5)

Functor

Functor is a higher-kinded typeclass characterized by its method map which transforms some value within a given context F via a function.

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

Example:

implicit val listFunctor: Functor[List] =
  new Functor[List] {
    def map[A, B](ls: List[A])(f: A => B) = ls.map(f)
  }

val listF = implicitly[Functor[List]]
listF.map(List(1,2,3))(i => s"#$i!")
// List("#1!", "#2!", "#3!")

Monad

Monad enables sequencing of operations in which resulting values from an operation can be utilized in the subsequent one.

But first, let’s look at typeclass FlatMap.

trait FlatMap[F[_]] extends Apply[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  @tailrec
  def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]
}

FlatMap extends Apply whose key methods aren’t what we would like to focus on at the moment. Rather, we’re more interested in method flatMap which enables sequential chaining of operations.

In addition, method tailRecM is a required implementation for stack-safe recursions on the JVM (which doesn’t natively support tail call optimization).

Monad inherits almost all its signature methods from FlatMap.

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

Monad also extends Applicative which we’ll get to (along with Apply) in a bit. For now, it suffices to note that Monad inherits pure from Applicative.

Even without realizing that Monad extends Functor (indirectly through FlatMap and Apply), one could conclude that Monads are inherently Functors by implementing map using flatMap and pure.

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

Example:

trait Monad[F[_]] {  // Skipping dependent classes
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def pure[A](a: A): F[A]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  def tailRecM[A, B](init: A)(f: A => F[Either[A, B]]): F[B]
}

implicit val optionMonad: Monad[Option] =
  new Monad[Option] {
    def flatMap[A, B](opt: Option[A])(f: A => Option[B]) = opt.flatMap(f)
    def pure[A](a: A) = Option(a)
    def map[A, B](opt: Option[A])(f: A => B): Option[B] = flatMap(opt)(a => pure(f(a)))
    @scala.annotation.tailrec
    def tailRecM[A, B](a: A)(f: A => Option[Either[A, B]]): Option[B] = f(a) match {
      case None => None
      case Some(leftOrRight) => leftOrRight match {
        case Left(a1) => tailRecM(a1)(f)
        case Right(b1) => Option(b1)
      }
    }
  }

val optMonad = implicitly[Monad[Option]]
optMonad.flatMap(Option(3))(i => if (i > 0) Some(s"#$i!") else None)
// Some("#3!")

Semigroupal and Apply

A higher-kinded typeclass, Semigroupal conceptually deviates from SemiGroup’s values combining operation to joining independent contexts in a tupled form “product”.

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

Despite the simplicity of method product (which is the only class method), Semigroupal lays out the skeletal foundation for the problem space of concurrency of independent operations, as opposed to Monad’s sequential chaining.

Next, Apply brings together the goodies of Semigroupal and Functor. Its main method ap has a rather peculiar signature that doesn’t look intuitively meaningful.

trait Apply[F[_]] extends Semigroupal[F] with Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  def map[A, B](fa: F[A])(f: A => B): F[B]
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

Conceptually, it can be viewed as a specialized map in which the transformation function is “wrapped” in the context.

By restructuring the type parameters in ap[A, B] and map[A, B], method product can be implemented in terms of ap and map.

// 1: Substitute `B` with `B => (A, B)`
def map[A, B](fa: F[A])(f: A => B => (A, B)): F[B => (A, B)]

// 2: Substitute `A` with `B` and `B` with `(A, B)`
def ap[A, B](ff: F[B => (A, B)])(fb: F[B]): F[(A, B)]

// Applying 1 and 2:
def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
  ap(map(fa)(a => (b: B) => (a, b)))(fb)

Applicative

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

Like how Monoid supplements SemiGroup with the empty element to form a more “self-contained” typeclass, Applicative extends Apply and adds method pure which wraps a value in a context. The seemingly insignificant inclusion makes Applicative a typeclass capable of addressing problems within a particular problem space.

Similarly, Monad takes pure from Applicative along with the core methods from FlatMap to become another “self-contained” typeclass to master a different computational problem space.

Contrary to Monad’s chaining of dependent operations, Applicative embodies concurrent operations, allowing independent computations to be done in parallel.

We’ll defer examples for Applicative to a later section.

Foldable

Foldable offers fold methods that go over (from left to right or vice versa) some contextual value (oftentimes a collection) and aggregate via a binary function starting from an initial value. It also provides method foldMap that maps to a Monoid using an unary function.

trait Foldable[F[_]] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]
  def foldMap[A, B: Monoid](fa: F[A])(f: A => B): B
}

Note that the well known foldRight method in some Scala collections may not be stack-safe (especially in older versions). Cats uses a data type Eval in its foldRight method to ensure stack-safety.

Traverse

Traverse extends Functor and Foldable and provides method traverse. The method traverses and transforms some contextual value using a function that wraps the transformed value within the destination context, which as a requirement, is bound to an Applicative.

trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(ff: A => G[B]): G[F[B]]
}

If you’ve used Scala Futures, method traverse (and the sequence method) might look familiar.

def sequence[G[_]: Applicative, A](fg: F[G[A]]): G[F[A]] =
  traverse(fg)(identity)

Method sequence has the effect of turning a nested context “inside out” and is just a special case of traverse by substituting A with G[B] (i.e. making ff an identity function).

Example: Applicative and Traverse

To avoid going into a full-on implementation of Traverse in its general form that would, in turn, require laborious implementations of all the dependent typeclasses, we’ll trivialize our example to cover only the case for Futures (i.e. type G = Future).

First, we come up with a specialized Traverse as follows:

import scala.concurrent.{ExecutionContext, Future}

trait FutureTraverse[F[_]] {  // Skipping dependent classes
  def traverse[A, B](fa: F[A])(ff: A => Future[B]): Future[F[B]]
}

For similar reasons, let’s also “repurpose” Applicative to include only the methods we need. In particular, we include method map2 which will prove handy for implementing the traverse method for FutureTraverse.

trait Applicative[F[_]] {  // Skipping dependent classes
  def map[A, B](fa: F[A])(f: A => B): F[B]
  def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z]
  def pure[A](a: A): F[A]
}

implicit val futureApplicative: Applicative[Future] =
  new Applicative[Future] {
    implicit val ec = ExecutionContext.Implicits.global
    def map[A, B](fa: Future[A])(f: A => B): Future[B] = fa.map(f)
    def map2[A, B, Z](fa: Future[A], fb: Future[B])(f: (A, B) => Z): Future[Z] =
      (fa zip fb).map(f.tupled)
    def pure[A](a: A): Future[A] = Future.successful(a)
  }

We implement map2 by tuple-ing the Futures and binary function via zip and tupled, respectively. With the implicit Applicative[Future] in place, we’re ready to implement FutureTraverse[List].

implicit val listFutureTraverse: FutureTraverse[List] =
  new FutureTraverse[List] {
    implicit val ec = ExecutionContext.Implicits.global
    implicit val appF = implicitly[Applicative[Future]]
    def traverse[A, B](ls: List[A])(ff: A => Future[B]): Future[List[B]] = {
      ls.foldRight[Future[List[B]]](Future.successful(List.empty[B])){ (a, acc) =>
        appF.map2(ff(a), acc)(_ :: _)
      }
    }
  }

import scala.concurrent.ExecutionContext.Implicits.global

val lsFutTraverse = implicitly[FutureTraverse[List]]
lsFutTraverse.traverse(List(1,2,3)){ i =>
  if (i > 0) Future.successful(s"#$i!") else Future.failed(new Exception())
}
// Future(Success(List("#1!", "#2!", "#3!")))

As a side note, we could implement traverse without using Applicative. Below is an implementation leveraging Future’s flatMap method along with a helper function (as demonstrated in a previous blog post about Scala collection traversal).

implicit val listFutureTraverse: FutureTraverse[List] =
  new FutureTraverse[List] {
    implicit val ec = ExecutionContext.Implicits.global
    def pushToList[A](a: A)(as: List[A]): List[A] = a :: as
    def traverse[A, B](ls: List[A])(ff: A => Future[B]): Future[List[B]] = {
      ls.foldRight[Future[List[B]]](Future.successful(List.empty[B])){ (a, acc) =>
        ff(a).map(pushToList).flatMap(acc.map)
      }
    }
  }