Type Classes

Type classes are a powerful tool used in functional programming to enable ad-hoc polymorphism, more commonly known as overloading. Where many object-oriented languages leverage subtyping for polymorphic code, functional programming tends towards a combination of parametric polymorphism (think type parameters, like Java generics) and ad-hoc polymorphism.

Example: collapsing a list

The following code snippets show code that sums a list of integers, concatenates a list of strings, and unions a list of sets.

def sumInts(list: List[Int]): Int = list.foldRight(0)(_ + _)

def concatStrings(list: List[String]): String = list.foldRight("")(_ ++ _)

def unionSets[A](list: List[Set[A]]): Set[A] = list.foldRight(Set.empty[A])(_ union _)

All of these follow the same pattern: an initial value (0, empty string, empty set) and a combining function (+, ++, union). We'd like to abstract over this so we can write the function once instead of once for every type so we pull out the necessary pieces into an interface.

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

// Implementation for Int
val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

The name Monoid is taken from abstract algebra which specifies precisely this kind of structure.

We can now write the functions above against this interface.

def combineAll[A](list: List[A], m: Monoid[A]): A = list.foldRight(m.empty)(m.combine)

Type classes vs. subtyping

The definition above takes an actual monoid argument instead of doing the usual object-oriented practice of using subtype constraints.

// Subtyping
def combineAll[A <: Monoid[A]](list: List[A]): A = ???

This has a subtle difference with the earlier explicit example. In order to seed the foldRight with the empty value, we need to get a hold of it given only the type A. Taking Monoid[A] as an argument gives us this by calling the appropriate empty method on it. With the subtype example, the empty method would be on a value of type Monoid[A] itself, which we are only getting from the list argument. If list is empty, we have no values to work with and therefore can't get the empty value. Not to mention the oddity of getting a constant value from a non-static object.

For another motivating difference, consider the simple pair type.

final case class Pair[A, B](first: A, second: B)

Defining a Monoid[Pair[A, B]] depends on the ability to define a Monoid[A] and Monoid[B], where the definition is point-wise, i.e. the first element of the first pair combines with the first element of the second pair and the second element of the first pair combines with the second element of the second pair. With subtyping such a constraint would be encoded as something like

final case class Pair[A <: Monoid[A], B <: Monoid[B]](first: A, second: B) extends Monoid[Pair[A, B]] {
  def empty: Pair[A, B] = ???

  def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] = ???
}

Not only is the type signature of Pair now messy but it also forces all instances of Pair to have a Monoid instance, whereas Pair should be able to carry any types it wants and if the types happens to have a Monoid instance then so would it. We could try bubbling down the constraint into the methods themselves.

final case class Pair[A, B](first: A, second: B) extends Monoid[Pair[A, B]] {
  def empty(implicit eva: A <:< Monoid[A], evb: B <:< Monoid[B]): Pair[A, B] = ???

  def combine(x: Pair[A, B], y: Pair[A, B])(implicit eva: A <:< Monoid[A], evb: B <:< Monoid[B]): Pair[A, B] = ???
}
// error: class Pair needs to be abstract.
// Missing implementations for 2 members of trait Monoid.
//   def combine(x: Pair[A,B], y: Pair[A,B]): Pair[A,B] = ??? // implements `def combine(x: A, y: A): A`
//   def empty: Pair[A,B] = ??? // implements `def empty: A`
//

But now these don't conform to the interface of Monoid due to the implicit constraints.

Implicit derivation

Note that a Monoid[Pair[A, B]] is derivable given Monoid[A] and Monoid[B]:

final case class Pair[A, B](first: A, second: B)

def deriveMonoidPair[A, B](A: Monoid[A], B: Monoid[B]): Monoid[Pair[A, B]] =
  new Monoid[Pair[A, B]] {
    def empty: Pair[A, B] = Pair(A.empty, B.empty)

    def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] =
      Pair(A.combine(x.first, y.first), B.combine(x.second, y.second))
  }

One of the most powerful features of type classes is the ability to do this kind of derivation automatically. We can do this through Scala's implicit mechanism.

import cats.Monoid

object Demo {
  final case class Pair[A, B](first: A, second: B)

  object Pair {
    implicit def tuple2Instance[A, B](implicit A: Monoid[A], B: Monoid[B]): Monoid[Pair[A, B]] =
      new Monoid[Pair[A, B]] {
        def empty: Pair[A, B] = Pair(A.empty, B.empty)

        def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] =
          Pair(A.combine(x.first, y.first), B.combine(x.second, y.second))
      }
  }
}

We also change any functions that have a Monoid constraint on the type parameter to take the argument implicitly, and any instances of the type class to be implicit.

implicit val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

def combineAll[A](list: List[A])(implicit A: Monoid[A]): A = list.foldRight(A.empty)(A.combine)

Now we can also combineAll a list of Pairs as long as Pair's type parameters themselves have Monoid instances.

implicit val stringMonoid: Monoid[String] = new Monoid[String] {
  def empty: String = ""
  def combine(x: String, y: String): String = x ++ y
}

import Demo.{Pair => Paired}

combineAll(List(Paired(1, "hello"), Paired(2, " "), Paired(3, "world")))
// res2: Demo.Pair[Int, String] = Pair(first = 6, second = "hello world")

A note on syntax

In many cases, including the combineAll function above, the implicit arguments can be written with syntactic sugar.

def combineAll[A : Monoid](list: List[A]): A = ???

While nicer to read as a user, it comes at a cost for the implementer.

import cats.Monoid

// Defined in the standard library, shown for illustration purposes
// Implicitly looks in implicit scope for a value of type `A` and just hands it back
def implicitly[A](implicit ev: A): A = ev

def combineAll[A : Monoid](list: List[A]): A =
  list.foldRight(implicitly[Monoid[A]].empty)(implicitly[Monoid[A]].combine)

For this reason, many libraries that provide type classes provide a utility method on the companion object of the type class, usually under the name apply, that skirts the need to call implicitly everywhere.

object Monoid {
  def apply[A : Monoid]: Monoid[A] = implicitly[Monoid[A]]
}

def combineAll[A : Monoid](list: List[A]): A =
  list.foldRight(Monoid[A].empty)(Monoid[A].combine)

Laws

Conceptually, all type classes come with laws. These laws constrain implementations for a given type and can be exploited and used to reason about generic code.

For instance, the Monoid type class requires that combine be associative and empty be an identity element for combine. That means the following equalities should hold for any choice of x, y, and z.

combine(x, combine(y, z)) = combine(combine(x, y), z)
combine(x, id) = combine(id, x) = x

With these laws in place, functions parametrized over a Monoid can leverage them for say, performance reasons. A function that collapses a List[A] into a single A can do so with foldLeft or foldRight since combine is assumed to be associative, or it can break apart the list into smaller lists and collapse in parallel, such as

val list = List(1, 2, 3, 4, 5)
val (left, right) = list.splitAt(2)

// Imagine the following two operations run in parallel
val sumLeft = combineAll(left)
// sumLeft: Int = 3
val sumRight = combineAll(right)
// sumRight: Int = 12

// Now gather the results
val result = Monoid[Int].combine(sumLeft, sumRight)
// result: Int = 15

Cats provides laws for type classes via the kernel-laws and laws modules which makes law checking type class instances easy.

You can find out more about law testing here.

Type classes in Cats

From cats-infographic by @tpolecat.

Incomplete type class instances in cats

Originally from @hobwekiva

Further reading

• Returning the "Current" Type in Scala