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.

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:

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.

Example:

Functor

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

Example:

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.

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.

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.

Example:

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”.

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.

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.

Applicative

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.

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.

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

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:

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.

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].

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).