What are Scala Type Classes?

What are Scala type classes, what kind of problem do they solve and how are they implemented?

In a nut shell, type classes provide polymorphism without using subtyping, but in a completely type safe way.

Type classes represent some common functionality that can be applied to values of many different types. Moreover, we don’t have to change existing types in order to extend them with the new functionality.

In this post I will describe 5 simple steps for encoding a type class in Scala in an idiomatic way.

A problem and a specific solution

Let’s first look at a problem and its specific solution.

Consider a type ShoppingCart:

type ProductId = String
type Quantity = Int

case class ShoppingCart(items: Map[ProductId, Quantity])

Assume we have to implement a function that merges a list of ShoppingCart into a single instance that contains all the product items from all the carts with their quantities summed up.

One way to do this is to implement a fold over the list of shopping carts:

def merge(list: List[ShoppingCart]): ShoppingCart = {
    val emptyCart = ShoppingCart(Map())
    list.fold(emptyCart)(combineTwoShoppingCarts)
}

To make this work we need a function to combine two shopping carts:

def combineTwoShoppingCarts(sc1: ShoppingCart, sc2: ShoppingCart): ShoppingCart = {
    ShoppingCart(combineItems(sc1.items, sc2.items))
}

We are delegating the work to a function that takes two lists of product IDs with their quantities and merges them into one:

  def combineItems(m1: Map[ProductId, Quantity], m2: Map[ProductId, Quantity])
  : Map[ProductId, Quantity] = {
    (m1.keys ++ m2.keys)
      .toList
      .distinct
      .map(id => (id, m1.getOrElse(id, 0) + m2.getOrElse(id, 0)))
      .toMap
  }

It’s not the most efficient solution, but it works:

scala> val carts = List(
    ShoppingCart(Map("p0001" -> 1, "p0002" -> 3)),
    ShoppingCart(Map("p0001" -> 4, "p0004" -> 6)))

scala> merge(carts)
ShoppingCart(Map(p0001 -> 5, p0002 -> 3, p0004 -> 6))

The generalized solution

Let’s find a common pattern.

There are two concepts that appear several times as demonstrated in the image below:

  1. A value that represents a neutral or empty element (marked in green)
  2. A function that combines two elements (marked in pink)

alt text

The empty value and the combine function are used with three different types:

  • Quantity (which expands to Int)
    • Empty value: 0
    • Combine function: +
  • Map[ProductId, Quantity]
    • Empty value: Map()
    • Combine function: combineItems
  • ShoppingCart
    • Empty value: ShoppingCart(Map())
    • Combine function: combineTwoShoppingCarts

Type class encoding in 5 simple steps

Let’s encode the common concepts in a custom type class that we will call Combinable.

Here are the steps to create a type class and instances.

Some of the steps are optional, as they only provide syntactic sugar.

1. Define a parameterised trait

First we define a parameterised trait with the empty value and the combine function:

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

2. Define a companion object with an apply method (optional)

object Combinable {
  def apply[A](implicit comb: Combinable[A]): Combinable[A] = comb
}

The apply method gives us syntactic sugar, when we want to use an instance of the Combinable type class.

Note the implicit parameter. In order to obtain an instance of the type class, the instance has to be defined somewhere within the scope, annotated with implicit. (Find out more on implicit here.)

E.g. if an implicit instance for Int is defined, we can get the empty value like this:

scala> Combinable[Int].empty
res0: Int = 0

3. Define a factory method (optional)

Within the companion object we can define a factory method which reduces much of the boiler-plate code when creating Combinable instances.

def instance[A](emptyValue: A, combineFunc: (A, A) => A): Combinable[A] = {
  new Combinable[A] {
    def combine(a: A, b: A): A = combineFunc(a,b)
    def empty: A = emptyValue
  }
}

4. Define globally visible type class instances

Also within the companion object, we define all the instances that should be globally visible and mark them with implicit.

In our case we need instances for Int and Map.

Here is the definition of Combinable[Int]:

implicit val intCombinableInstance: Combinable[Int] = 
  Combinable.instance(0, _ + _)

This is the instance for Map:

implicit def mapCombinableInstance[A,B](implicit b: Combinable[B])
: Combinable[Map[A, B]] = {
  def merge(map1: Map[A, B], map2: Map[A, B]): Map[A, B] = {
    (map1.keys ++ map2.keys)
      .toList
      .distinct
      .map(a => (a, b.combine(
        map1.getOrElse(a, b.empty),
        map2.getOrElse(a, b.empty))))
      .toMap
  }
  Combinable.instance(Map(), merge)

To create an instance of Combinable[Map[A, B]] we have to use an implicit function.

The reason is that there is a constraint on the type B. B itself has to be a Combinable. So we have to pass an implicit parameter of type Combinable[B].

Type safety

The compiler will figure out if there is an implicit value of Combinable[B] in scope. If not, the code won’t compile.

E.g. this will work since we have a Combinable[Int]:

scala> Combinable[Map[String, Int]].empty
res0: Map[String,Int] = Map()

But this won’t compile unless we define a Combinable instance for Boolean:

scala> Combinable[Map[String, Boolean]].empty
<console>:16: error: could not find implicit value for parameter comb: Combinable[Map[String,Boolean]]
       Combinable[Map[String, Boolean]].empty
                 ^

Recursive resolution

The compiler can even recursively resolve instances:

scala> Combinable[Map[Int, Map[Int, Map[Int, Int]]]].empty
res0: Map[Int,Map[Int,Map[Int,Int]]] = Map()

5. Define locally visible type class instances

No we can define an instance for our ShoppingCart type. This can be done within the companion object of ShoppingCart or elsewhere:

implicit val shoppingCartCombinableInstance: Combinable[ShoppingCart] = {
  Combinable.instance(
    ShoppingCart(
      Map()),
      (m1, m2) => ShoppingCart(Combinable[Map[ProductId, Quantity]].combine(m1.items, m2.items)))
}

Back to the problem

We can now retrieve an empty shopping cart or combine two shopping carts. However, we still have to implement the fold to combine a list of shopping carts.

The nice thing is that we can now do that for every instance of the Combinable type class by defining a non-abstract method within the trait:

trait Combinable[A] {
  // ...
  def combineAll(list: List[A]) = list.fold(empty)(combine)
}

Now we can call this method like this:

scala> Combinable[ShoppingCart].combineAll(carts)
res0: ShoppingCart = ShoppingCart(Map(p0001 -> 5, p0002 -> 3, p0004 -> 6))

Monoids

It turns out that there already exists a type class like Combinable called Monoid.

The concept of monoids is simple yet powerful and goes way beyond what we’ve discussed here. E.g. monoids are the building blocks of much more advanced types and they are extensively used in data processing.

Conclusion

We have seen that with the help of type classes we can reduce the code that is specific to a particular problem by a great deal.

We have also seen:

  • Type classes offer general solutions to specific problems
  • Type classes provide polymorphism without subtyping
  • Existing types can be extended with new functionality without changing their internals
  • Programming with type classes is completely type safe
  • Type classes are encoded with traits and implicits
  • Cats and scalaz provide a lot of implementations of very useful type classes

There are 5 simple steps to create a type class:

  1. Define a parameterised trait
  2. Define a companion object with an apply method (optional)
  3. Define a factory method (optional)
  4. Define globally visible type class instances
  5. Define locally visible type class instances

If you want to practice, here are two exercises:

  1. Take the code from this post and define Combinable instances for String, Boolean, and List (or any other type that seems appropriate).
  2. Implement a type class Printable which prints a String representation of a value to the console.

And have fun! 🙂

  • Alexander Prokofyev

    Very clear and practical article. Thank you!