Back
Category Theory Type Classes in Scala 3

/ 7 min read

Category Theory Type Classes in Scala 3

Last Updated:

This is the second chapter in a series of posts exploring the structure and hierarchy of type classes in the Scala Cats library. You can read the first post here.

Category Theory

Category Theory is a branch of mathematics that looks at mathematical structures and their relationship to one another. In terms of functional programming, we can use these algebraic relations to compose behaviour.

We can model the structures and their relationship to one another in Scala with Type Classes.

Algebraic Structures

Let’s have a look at some of the most common structures and define them using type classes.

Semigroup

One of the simplest structures is the Semigroup, which is defined as a structure containing the behaviour of ‘combining’ a value of type A with another value also of type A.

trait Semigroup[A] {
  def combine(a: A, b: A): A
}

In addition to this definition, we also specify that for a structure to implement Semigroup lawfully, it MUST be associative in the combine operation.

This means that no matter in which order the operation takes place, the result must be equal.

combine(A, combine(B, C)) === combine(combine(A, B), C)

In practice this law holds in operations such as addition or multiplication, but NOT subtraction.

To make this more concrete, let’s implement multiple implementations of Semigroup for type Int.

val intSemigroupAddition = new Semigroup[Int] {
  def combine(a: Int, b: Int): Int = a + b
}
val intSemigroupMultiplication = new Semigroup[Int] {
  def combine(a: Int, b: Int): Int = a * b
}
val intSemigroupSubtraction = new Semigroup[Int] {
  def combine(a: Int, b: Int): Int = a - b
}


val additionResultOne =
  intSemigroupAddition.combine(intSemigroupAddition.combine(2, 3), 4)
val additionResultTwo =
  intSemigroupAddition.combine(2, intSemigroupAddition.combine(3, 4))
val isAdditionAssociative = additionResultOne == additionResultTwo


val multiplicationResultOne =
  intSemigroupMultiplication.combine(
    intSemigroupMultiplication.combine(2, 3),
    4
  )
val multiplicationResultTwo =
  intSemigroupMultiplication.combine(
    2,
    intSemigroupMultiplication.combine(3, 4)
  )
val isMultiplicationAssociative =
  multiplicationResultOne == multiplicationResultTwo


val subtractionResultOne =
  intSemigroupSubtraction.combine(intSemigroupSubtraction.combine(2, 3), 4)
val subtractionResultTwo =
  intSemigroupSubtraction.combine(2, intSemigroupSubtraction.combine(3, 4))
val isSubtractionAssociative = subtractionResultOne == subtractionResultTwo


println(isAdditionAssociative) // true
println(isMultiplicationAssociative) // true
println(isSubtractionAssociative) // false

Some points to note:

  • We can implement multiple different valid implementations for a type
  • We can implement lawful AND unlawful implementations
  • We MUST NOT implement unlawful implementations

There is nothing stopping us from implementing unlawful implementations, but doing so would cause chaos further down the line.

There are libraries you can use to test the lawfulness of your implementations, such as discipline.

Reasoning

It might seem rather pointless to have a structure just to represent such a simple operation, however simple operations form the basis of complex operations, and by abstracting the operation away from the underlying type allows us to perform common operations (in this case combine) on abstract types.

For example, we could implement some more complex operation, into which is passed 2 parameters. If we constrain the parameters’ type to some type T in the scope of an implemented Semigroup[T], we can perform combine operations on them without knowing anything else about the type.

Monoid

As useful as this may be, if we had more information about the type, we would be able to perform more complex operations on it. For example, let’s try to implement combine over a list, such that all elements in the list are combined with one another.

def sum(ints: List[Int])(using semigroup: Semigroup[Int]): Int =
  ints.foldLeft(0)((a, b) => semigroup.combine(a, b))

Here we have created a sum function, which sums up all the elements in a list by combineing them.

So far so good, but what if we want to express the idea of combineing over a list of unknown type T for Semigroup[T]?

def sum[T](ints: List[T])(using semigroup: Semigroup[T]): T =
  ints.foldLeft(/* ... this is an issue ... */)((a, b) => semigroup.combine(a, b))

We do not know what value to start the fold with, since a semigroup alone does not provide that information.

We are looking for a value which when combined with another value of the same type, it will result in the SAME value as the other value.

In the case of integer addition, this special value would be 0.

5 + 0 = 5
0 + 7 = 7

In the case of integer multiplication, this special value would be 1.

8 * 1 = 8
1 * 3 = 3

This special value is called the identity value for the specific type and implementation combination.

When we include the identity value in the algebraic structure, the structure is called a Monoid.

Let’s define the type class for a monoid.

trait Monoid[A] {
  def combine(a: A, b: A): A
  def identity: A
}

Now that we have this additional information about the abstract type, let’s try to implment a list combine again.

def combineAll[T](ts: List[T])(using monoid: Monoid[T]): T =
  ts.foldLeft(monoid.identity)((a, b) => monoid.combine(a, b))

Note that this function is NOT a sum. It certainly CAN sum integers, assuming there exists an in scope implementation for Monoid[Int] AND that implementation combines using addition, but this function can do much more than only sum, because it can operate on any Monoid[T].

Notice additionally, that since the monoid requires the same combine behaviour as the semigroup, we can say that the monoid extends the semigroup and rewrite it as follows:

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

Journey to the Monad

Just as with the semigroup and the monoid structures, there are a few very common other structures which when put together through inheritance, allows us to construct a Monad.

Monads are special, because they are incredibly useful, so useful that Scala even has special syntax for them, called for comprehensions, which we will look at later.

Before we define the monad itself, let’s take a simplified look at the monad structure hierarchy.

Functor -> Applicative -> Monad

This means that monads ARE applicatives which themselves ARE functors.

Functor

Let’s start with the functor.

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

From this definition we can see that a functor is some higher-kinded structure T which itself is generic over anything _, which has an implementation for map.

What then is map?

The function map represents the abstract behaviour of transforming the wrapped value A inside the higher-kinded wrapper T[A] and returning a new, same typed T higher-kinded wrapper containing the transformed value of type B which COULD be a different type than A.

That is a mouthful, but we could make it more concrete by considering an example wrapper, such as Option[_]. In this case, the map function would be applied to the value wrapped by the option and return a new option wrapping the new value.

Option[Int].map(_.toString()) // Option[String]

Note the above is not real Scala, but rather only to illustrate the principle.

Applicative

Applicative is a rather simple structure which simply defines the behaviour of lifting a plain value into a wrapper of some higher-kind T. The function to perform this behaviour is called pure.

Note also, the applicative extends the functor.

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

Monad

Finally we have the monad which extends the applicative and adds the behaviour of transforming the wrapped value such that when transformed into a result wrapped in it’s own higher-kinded type, the value is returned in a new wrapper which is not nested. The function to perform this behaviour is called flatMap.

trait Monad[T[_]] extends Applicative[T] {
  def flatMap[A, B](ta: T[A])(f: A => T[B]): T[B]
}

In addition, since the monad extends the applicative which itself extends the functor, the implementation of the monad needs to define map, pure and flatMap. However, it turns out that map can be implemented in terms of pure and flatMap, thus we can define the monad as follows:

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

This means that implementations of the monad would only need to implement pure and flatMap, and we would get the functionality of map automatically.

Summary

We have seen some of the type classes which represent elements in Category Theory and have built up to the monad.

We have seen that the monad is satisfied for any type T which for which an implementation exists for map, pure and flatMap.

In a later post we will look at how this generic extraction of behaviour becomes very useful in common programming situations.