An Introduction to Type Classes in Scala
This article is an introduction to the concept of type classes in Scala. Type classes provide a way to define functions with different implementations for different types, a characteristic often referred to as “ad-hoc polymorphism”. This article will start with a motivating example for the introduction of type classes, followed by a description on how to implement them in Scala and it will wrap up with a few words about the ecosystem that has been built around type classes for the Scala language.
Motivating example
Let’s consider these four different functions:
def sum(elements: List[Int]): Int =
if (elements.isEmpty)
0
else
elements.head + sum(elements.tail)def product(elements: List[Int]): Int =
if (elements.isEmpty)
1
else
elements.head * product(elements.tail)def concat(elements: List[String]): String =
if (elements.isEmpty)
""
else
elements.head + concat(elements.tail)def concat[A](elements: List[Seq[A]]): Seq[A] =
if (elements.isEmpty)
Nil
else
elements.head ++ concat(elements.tail)
Even though they compute different operations for different types, these functions have similar implementations: they recursively combine the elements of an input list, using an associative binary operator (+, * or ++) and an identity/empty element for this operator (either 0, 1, "”or Nil) to deal with the case when the list is empty. These two properties together on a data type form an algebraic structure known as a monoid.
In software engineering, when a repeating pattern occurs, it is considered to be a best practice to refactor the code in order to reuse a single implementation of this pattern. Let’s try to refactor these four functions into a single polymorphic function that could operate on any type for which there exists a monoid structure.
In Object-Oriented Programming (OOP) language, such as Java or Scala, we are used to relying on subtyping to implement polymorphic functions. This concept could be applied here:
trait Monoid[A] {
def combine(other: A): A
}def combineAll[A <: Monoid[A]](elements: List[A]): A =
if (elements.isEmpty)
/* some identity element */
else
elements.head.combine(combineAll(elements.tail))
As we can see, if we try to model a Monoid trait that should be implemented by all classes used with the combineAll function, we are facing several issues:
- We cannot model the identity element as a member of the trait. Indeed, the identity element is not a property of a given instance, but a static property at the type level and static properties cannot be overridden.
- Base types such as
IntandString, or external library types such asSeq[A]cannot extend a new trait, so subtyping could only work on our own defined classes. - We cannot have multiple behaviors for the same class as there can only be one implementation of a trait for a given type, therefore it would not be possible to have two different implementations of
Monoidfor the same type, eg. to define the sum and the product for integers.
Thus, it appears that subtyping is not a solution to our refactoring problem. To find a solution, let’s have a look at the type classes in Haskell, the language which this concept originates from.
In Haskell, a type class defines a contract on a type as a set of functions. Note that even though it uses the same class keyword that we are used to apply to OOP classes in most languages, these functions are regular functions and not “methods” or “attributes“ defined on an element of a type. Therefore, it becomes possible to define a Monoid type class with both a binary operator combine and a factory function empty to return the identity element.
We can then declare our function combineAll to work only with those types for which there is an implementation of the Monoid type class (called an instance) and thus use the definition of combine and empty that it provides. Moreover, as type class instances are external to type definitions, we can declare them on any type.
The following code snippet provides a possible implementation of the combineAll function with a Monoid type class in Haskell, as we have just described:
class Monoid a where
empty :: a
combine :: a -> a -> acombineAll :: (Monoid a) => [a] -> a
combineAll list =
if null list
then empty
else combine (head list) (combineAll (tail list))instance Monoid Int where
empty = 0
combine x y = x + y-- return 10
combineAll [1, 2, 3, 4]-- no instance defined for String, does not compile
combineAll ["Hello", " ", "world"]
However, there remains one problem that this concept does not solve, which is the possibility to declare multiple instances of the same type class for a single type. Despite this fact, the type class concept seems well suited to solve our refactoring problem.
Unfortunately, unlike Haskell, type classes are not a feature provided by the language in Scala. But we will see in the next section that we can still implement them as a design pattern based on other features of the language.
Type classes as a design pattern in Scala
Type classes implementation
Scala does not have type classes built in the language but two features of the language allow us to implement them.
The first feature is subtyping. This could appear surprising since we have just declared in the previous section that subtyping was not a solution here. But we actually just need to change perspective: we are not going to implement a Monoid trait as a contract for every element of a given type but as a contract for an external object that represents the monoid structure of a type, and which is equivalent to a type class instance in Haskell.
The second feature is implicit parameters. In Scala, the last parameter group of a function can be declared with the keyword implicit. When using the function, the compiler will allow these parameters to be left unspecified, providing that for every parameter there exists an implicit value of the same type declared in the scope. Implicit parameters will serve two purposes in the context of type classes:
- They will introduce a compile-time dependency to an instance of a given type class.
- They will provide the actual instance as a parameter so that the implementation of the function can have access to its functions.
Here is an example of an implementation of a Monoid type class and a combineAll function in Scala, based on this type class design pattern:
trait Monoid[A] {
def empty: A
def combine(elem1: A, elem2: A): A
}def combineAll[A](elements: List[A])(
implicit monoid: Monoid[A]
): A =
if (elements.isEmpty)
monoid.empty
else
monoid.combine(elements.head, combineAll(elements.tail))
And this is an example of the declaration of an instance for the sum monoid on the type Int, with an implicit object extending the Monoid trait, which is implicitly passed to the combineAll function call:
implicit object SumMonoid extends Monoid[Int] {
val empty: Int = 0
def combine(i: Int, j: Int): Int = i + j
}// return 10
combineAll(List(1, 2, 3, 4))
Type class instances can also be declared using implicit values extending the trait at runtime:
implicit val stringMonoid: Monoid[String] = new Monoid[String] {
val empty: String = ""
def combine(s1: String, s2: String): String = s1 + s2
}// return "Hello World"
combineAll(List("Hello", " ", "World"))
However, when we need to support parametric types, we cannot use objects or values. Fortunately, implicit parameters resolution supports implicit functions:
implicit def seqMonoid[A]: Monoid[Seq[A]] = new Monoid[Seq[A]] {
val empty: Seq[A] = Nil
def combine(seq1: Seq[A], seq2: Seq[A]): Seq[A] = seq1 ++ seq2
}// return Seq(1, 2, 3, 4)
combineAll(List(Seq(1, 2), Seq(3, 4)))// return Seq("Hello", "Ciao", "Salut", "Hola")
combineAll(List(Seq("Hello", "Ciao"), Seq("Salut", "Hola")))
Multiple behaviors for the same type
We have seen that the type class concept from Haskell was a solution to our problem, except for one aspect: the ability to define multiple instances of a type class for the same type. For example, we had the case of the type Int, for which we would like to define one monoid for the sum and another for the product.
What about type classes in Scala, do they suffer from the same limitation? Let’s try to define two instances of Monoid for the type Int:
implicit object SumMonoid extends Monoid[Int] {
val empty: Int = 0
def combine(i: Int, j: Int): Int = i + j
}implicit object ProductMonoid extends Monoid[Int] {
val empty: Int = 1
def combine(i: Int, j: Int): Int = i * j
}// compiler complains about ambiguous implicit values
// for `Monoid[Int]`
combineAll(List(1, 2, 3, 4))
As we can see in the example above, we cannot just call the combineAll function with two implicit values in scope, as the compiler does not know which one it should pass to the function.
However, since the instances are passed as implicit parameters, we can simply remove the ambiguity by passing the appropriate instance explicitly to the function:
// return 24
combineAll(List(1, 2, 3, 4))(ProductMonoid)So in a way, one could say that type classes in Scala, available as a design pattern, are more flexible than type classes in Haskell since we can have multiple instances for the same type!
Type classes as type bounds
We mentioned that type classes are not a feature of the language in Scala, however, we can make them look just as if they were built-in using the context type bound, which will hide the internal implicit parameter mechanism and provide a nice declarative syntax.
Indeed the following function declaration, using a context type bound:
def combineAll[A: Monoid](elements: List[A]): Ais actually some syntactic sugar equivalent to:
def combineAll[A](elements: List[A])(implicit ev: Monoid[A]): AThe context bound notation is more concise, and actually very helpful if you do not need to manipulate the instance in the function implementation, but only need to pass it down to internal function calls expecting it as an implicit parameter as well.
However, we can still use this type bound notation and get access to an instance within the function implementation, thanks to the helper function implicitly, which is provided by the standard library and simply implemented as:
def implicitly[T](implicit ev: T): T = evTherefore, it becomes possible to rewrite our original combineAll function using a type bound:
def combineAll[A: Monoid](elements: List[A]): A =
if (elements.isEmpty)
implicitly[Monoid[A]].empty
else
implicitly[Monoid[A]].combine(
elements.head,
combineAll(elements.tail)
)Type classes composition
The last feature of type classes that is worth mentioning is how well you can compose them.
Let’s consider the following monoid instances:
implicit val sumMonoid: Monoid[Int] = new Monoid[Int] {
val empty: Int = 0
def combine(i: Int, j: Int): Int = i + j
}implicit val stringMonoid: Monoid[String] = new Monoid[String] {
val empty: String = ""
def combine(s1: String, s2: String): String = s1 + s2
}implicit def pairMonoid[A: Monoid, B: Monoid]: Monoid[(A, B)] =
new Monoid[(A, B)] {
val empty: (A, B) = (
implicitly[Monoid[A]].empty,
implicitly[Monoid[B]].empty
) def combine(pair1: (A, B), pair2: (A, B)): (A, B) = (
implicitly[Monoid[A]].combine(pair1._1, pair2._1),
implicitly[Monoid[B]].combine(pair1._2, pair2._2)
)
}implicit def mapMonoid[K, V](
implicit monoid: Monoid[V]
): Monoid[Map[K, V]] = new Monoid[Map[K, V]] {
val empty: Map[K, V] = Map.empty def combine(map1: Map[K, V], map2: Map[K, V]): Map[K, V] = {
val keys = map1.keys.toSet union map2.keys.toSet keys.foldLeft(Map.empty[K, V]) { case (acc, key) =>
acc.updated(
key,
monoid.combine(
map1.getOrElse(key, monoid.empty),
map2.getOrElse(key, monoid.empty)
)
)
}
}
Here we have added a pairMonoid and mapMonoid in addition to our previously defined sumMonoid and stringMonoid. With these two new instances, one can see that we can define type class instances that depend on the existence of a given type class instance for some of their type parameters. For example, thanks to this mechanism it becomes possible to let the compiler recursively derive monoid instances for complex data types based on the simple definition of each basic type.
Therefore, these four monoid instances are all we need to combine structures with an arbitrary nested level of Int, String, Pair and Map data types, as exemplified in the following snippet:
val obj1 = (Map("foo" -> 1, "bar" -> 2), "Hello")
val obj2 = (Map("foo" -> 3), " ")
val obj3 = (Map("bar" -> 4), "World")// return (Map("foo" -> 4, "bar" -> 6), "Hello World")
combineAll(List(obj1, obj2, obj3))
Type classes ecosystem
Type classes in the standard library
If you came to Scala from the OOP world, type classes may seem exotic to you. However, you may have already used them without noticing, as they are used in the standard collection library. For example, an Ordering type class is declared on collection methods such as max and sorted, and a Numeric type class is declared on other collection methods such as product and sum. You probably did not notice it since the standard library already provides default implicit values for these instances that cover many base and standard types.
Type classes in other libraries
Type classes are also used as a basis in several libraries that favor a purely functional approach of programming in Scala, such as Scalaz or Cats. These two libraries provide most of the concept that you need to follow a purely functional programming paradigm and that you may already be familiar with if you practice Haskell, such as our Monoid example, but also Semigroup, Eq, Order, Show, Applicative, Functor, Monad, and many others.
If you think that these are abstract mathematical concepts that are too exotic for actual programming, have a look at the Typelevel stack, which contains libraries for any aspect of a web application development (database framework, JSON deserialization/serialization, HTTP framework…) entirely based on Cats and its type classes!
Conclusion
Type classes in Scala can be implemented as a design pattern based on subtyping and implicit parameters. They provide an interesting alternative to subtyping in any situation since they are not restricted to user-defined types, compose easily, and offer a custom implementation of static functions or to provide multiple versions of behavior for the same type. Moreover, if you are leaning toward a more functional style of programming in Scala, you will find well-designed libraries implementing all the basic concepts you need as flexible type classes.
