The Typeclass Pattern in Scala

In computer science, a type class is a type system construct that supports ad hoc polymorphism. Wikipedia

As we work on software projects we successively add types and operations so the piece of software we write grows and grows. At the same time we try to keep our pieces of code small and independent (DRY) units which can be easily composed, tested, improved and modified. This is approximately how Seth Tisue introducted his talk on why using the typeclass pattern at the Northeast Scala Symposium in 2012.

So what is (ad hoc) polymorphism?

Polymorphism as such means having a particular operation like a function or method where this particular operation works on different types.

Eugene Yokota refers on his blog about learning Scalaz to three different types of polymorphism:

Parametric polymorphism

The following function head takes a list of As and returns the first element of that list where it completely ignores what A actually is.

1
def head[A](xs: List[A]): A = xs(0)

So you could pass a list of Int, a list of String or whatever type you can dream of. The function just returns the first element.

Things get a bit trickier when we want to provide a polymorphic function like plus:

1
def plus[A](a1: A, a2: A): A = ???

What can we do here? It seems obvious that, depending on the A, plus has a different meaning or definition.

Subtype polymorphism to the rescue?

Subtype polymorphism

To overcome this, let’s try subtype polymorphism. So what we usually do here is to define a trait first which decribes what we want to achieve:

1
2
3
trait Addable[A] {
  def plus(a2: A): A
}

Addable describes the following: whenever implementing this trait with a concrete type we take the same type as an argument to plus and also return this concrete type where these types get added somehow. Now we can refactor our plus function like this:

1
def plus[A <: Addable[A]](a1: A, a2: A): A = a1.plus(a2)

With that generic plus function in place (with an upper bound to Addable[A]) we can actually define it’s implementation by making use of the Addable traits contract. Now we can be sure that whatever type comes in it has a plus method which we can use to add those types together.

Finally let’s implement such a concrete type by extending this trait. Let’s call that type Letter:

1
2
3
case class Letter(text: String) extends Addable[Letter] {
  override def plus(a2: Letter): Letter = Letter(text + a2.text)
}

Let’s try that out:

1
2
scala> plus(Letter("foo"), Letter("bar"))
res1: Letter = Letter(foobar)

Nice! But wait… can we do the same for types like String or Int?

As it turns out, we can’t. We need to extend that trait or mix it in on definition of the type. Of course, this is not possible for built-in types or types of libraries where we have no access to it’s source code.

And this is where ad hoc polymorphism comes into play.

Ad hoc polymorphism

Again, we start by defining a trait. This time we slightly change the signature of plus.

1
2
3
trait Addable[A] {
  def plus(a1: A, a2: A): A
}

Because we do not intend to mix that trait into a type on it’s definition we need to pass both instances of A.

But if we do not extend from that trait, or mix it in, what is it good for?

We use it in combination with Scala’s implicits. In particluar, we can write a function with an implicit parameter like this:

1
def plus[A](a1: A, a2: A)(implicit ev: Addable[A]): A = ev.plus(a1, a2)

We could also rewrite this function by using context bounds and implicitly, which is a function of scala.Predef materializing types from the surrounding scope, imports and companion objects (see also Daniel C. Sobral’s answer at SO on how implicit resolution in Scala works):

1
def plus[A: Addable](a1: A, a2: A): A = implicitly[Addable[A]].plus(a1, a2)

It is even more concise to provide an apply method on Addables companion object (credits to Erik Torreborre for his pro tip):

1
2
3
object Addable {
  def apply[A: Addable]: Addable[A] = implicitly[Addable[A]]
}

With this companion object and it’s apply method in place, plus gets even more concise, as promised:

1
def plus[A: Addable](a1: A, a2: A): A = Addable[A].plus(a1, a2)

Awesome, isn’t it?

At last we can provide implicit conversions of Addable[A] for arbitrary types, even for Int and String as follows:

1
2
3
4
5
6
7
8
9
implicit val intAddable = new Addable[Int] {
  def plus(a1: Int, a2: Int): Int = a1 + a2
}
implicit val stringAddable = new Addable[String] {
  def plus(a1: String, a2: String): String = a1 + a2
}
implicit val adderAddable = new Addable[Letter] {
  def plus(a1: Letter, a2: Letter): Letter = Letter(a1.text + a2.text)
}

And that’s it. Here’s how we use our (ad hoc) polymorphic plus function:

1
2
3
4
5
6
7
8
scala> plus(Letter("foo"), Letter("bar"))
res1: Letter = Letter(foobar)

scala> plus(40, 2)
res2: Int = 42

scala> plus("foo", "bar")
res3: String = foobar

So that’s all nice, but what of all this is now the typeclass pattern?

(Re-) enter the typeclass pattern

To make it even more clear what the typeclass pattern actually is, let’s point out the ingredients of the typeclass pattern in Scala:

  • Typeclasses (traits) which describe some behaviour (e.g. trait Addable[A])
  • Type parameters (A) i.e. abstractions of our concrete types
  • Typeclass instances (implicit conversions) for concrete types and their implementations (e.g. implicit val stringAddable = new Addable[String] { ... })
  • Polymorphic operations or typeclasses receiving other typeclasses respectively their instances via implicit parameters (e.g. def plus[A](a1: A, a2: A)(implicit ev: Addable[A]))

Let’s recap what we’ve achieved in the section above. The polymorhpic operation (plus) now works for any type, even for types which do not extist yet. When we miss an Addable typeclass instance for any type A in future, we can easily provide one by (ad hoc) definition via an implicit conversion and we don’t need to touch any existing implementation. This implementation is type safe as well, since the availability of a typeclass instance is checked at compile time. Furthermore, we are able to turn those typeclass instances on and off as we like (e.g. via import). We could also have multiple instances for Addable[String] in different scopes, or even within the same scope where you can disambiguate these conversions by passing the desired one explicitly as a parameter like this:

1
2
3
4
5
6
7
8
scala> implicit val stringAddable = new Addable[String] { .. }
stringAddable: Addable[String] = $anon$1@45125002

scala> implicit val upperCaseStringAddable = new Addable[String] { .. }
upperCaseStringAddable: Addable[String] = $anon$1@1777051a

scala> plus("foo", "bar")(upperCaseStringAddable)
res3: String = FOOBAR

What have we gained?

To sum it all up, we’ve gained following:

  • Type safety: available conversions are checked at compile time.
  • Extensibility: to add Addable typeclass instances is easy.
    • We can declare instances outside of the types themselves (String knows nothing about Addable). John Kodumal calls that the open world assumption.
  • Decoupling: we can add new independent pieces of code and don’t need to alter existing implementations.
    • We can override typeclass instances by putting new ones in scope.

What are the downsides?

Though I find this pattern really useful, there are downsides:

  • Implicits: Implicits are less discoverable, so one stronger relies on IDE support. You may run into complicated error messages when something goes wrong. Debugging your code can get a little bit more involved.
  • Performance: Experts claim that one may encounter some performance penalties at compile time when using implicits extensively.
  • Boilerplate: In real world examples there is a certain amount of boilerplate you need to write for that pattern, especially when it comes to method injection (see bonus chapter below). However, that effort really pays off on the consumer-side of your implementation.

Bonus chapter: Method injection a.k.a. pimp my library

So far, for adding arbitrary types together with our polymorphic plus function, we needed to pass both instances of that type as arguments to that function.

But what if we want plus to be a member of such a type (e.g. Int)? And what if we want such an operator not only for one type, but for all types that have an instance of Addable[A]? Here’s an example of what it should look like:

1
2
3
4
5
scala> 41 plus 1
res1: Int = 42

scala> "foo" plus "bar"
res2: String = foobar

Let’s craft a trait which describes the desired behaviour:

1
2
3
4
5
6
7
8
9
trait AddableOps[A] {
  val a: A
  val F: Addable[A]
  def plus(a2: A): A = F.plus(a, a2)
  // let's create an alias for plus (a boolean addition corresponds
  // to the logical function of an OR gate as well as to parallel
  // switch contacts)
  def ⋁(a2: A): A = plus(a2)
}

This trait describes: whatever A we get (e.g. Int), we require an Addable[A] for it (e.g. Addable[Int]) and provide a plus operation in terms of that values. This trait or typeclass enables us to provide a typeclass instance respectively an implicit conversion like this:

1
2
3
4
5
implicit def toAddableOps[A: Addable](value: A): AddableOps[A] =
  new AddableOps[A] {
    val a: A = value
    val F: Addable[A] = implicitly[Addable[A]]
  }

Here we put an implicit AddableOps[A] for every implicit Addable[A] in place. That means we can call our plus operation as a member of any type A which has a typeclass instance of Addable[A] in scope:

1
2
scala> 41 plus 1
res6: Int = 42

Awesome! As already mentioned, there’s a little boilerplate to write, but once you put that in place you win huge extensibility. Do you want that operation for Boolean? Just provide a typeclass instance for it and have fun (now we can use our nice syntax):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
scala> implicit def booleanAddable = new Addable[Boolean] {
     |   def plus(a1: Boolean, a2: Boolean): Boolean = a1 || a2
     | }
booleanAddable: Addable[Boolean]

scala> true  true
res1: Boolean = true

scala> true  false
res2: Boolean = true

scala> false  true
res3: Boolean = true

scala> false  false
res4: Boolean = false

But there is one more thing…

What if we want to have Addables for F[A]s, i.e. types which themselves accept type parameters like Option[A]? As it turns out we just need to provide another typeclass instance with some pattern matching inside…

1
2
3
4
5
6
7
8
9
implicit def optionAddable[A: Addable]: Addable[Option[A]] = new Addable[Option[A]] {
  def plus(lhs: Option[A], rhs: Option[A]) =
    (lhs, rhs) match {
      case (Some(a1), Some(a2)) => Some(a1  a2)
      case (Some(a1), None)     => lhs
      case (None, Some(a2))     => rhs
      case (None, None)         => None
    }
}

…and use it just like the other typeclass instances:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
scala> Option(true)  Option(true)
res1: Option[Boolean] = Some(true)

scala> Option(true)  Option(false)
res2: Option[Boolean] = Some(true)

scala> Option(false)  Option(true)
res3: Option[Boolean] = Some(true)

scala> Option(false)  Option(false)
res4: Option[Boolean] = Some(false)

scala> None  Option(false)
res5: Option[Boolean] = Option(false)

Our Addable typeclass, the primary purpose of which is to append types, is actually close to very common algebraic structures like Semigroup or Monoid.

How such Monoids and its relatives look like and what they are good for will be discussed in one of my next posts.

Stay tuned!

References

Invasion of the Monad Transformers »