Of Scala Type Classes
Scala Type Classes are often used in different Scala libraries. Type Classes solve problems of OOP polymorphism using elegant ideas of parametric and ad hoc polymorphism. This leads to less coupled and more extensible code, when designing a library or leveraging already designed type system with type classes approach. In order to understand Type Classes, let us shortly look at their origination language such as Haskell. In this article, we will also go through the type class implementation in Scala.
In the second part, we will look at similar idea of Type Classes in Rust, such as traits and support of Type Classes in Scala 3 (Dotty).
Your first look at Scala
If you are Scala newbie, you might have heard or already seen some examples of type class usage, however it can be quite hard to grasp their ideas at the beginning of learning Scala. If you are coming from language, which has type classes in some form, then you just need to get the difference between Scala 2/3 versions with what you already know at other languages.
Let’s start from the problems type classes solve
Imagine, we have such class hierarchy:
At some point we need add new member such as Tiger, but we do not want or even can’t extend from existing class like WildAnimals. What we want is actually to implement new behaviour for existing or new class.
Problems we want to avoid which arise using subtyping polymorphism:
- Classes coupling
- Complexity when adding new functionality to an already existing inheritance chain and existing class
- Weak type safety (conversions)
Solution: Type Classes which solve these problems via ad hoc polymorphism
What ad hoc word means at all? Let’s consult a dictionary:
ad hoc | ad ˈhɒk |
adverb:
when necessary or needed: the group was constituted ad hoc.
adjective:
created or done for a particular purpose as necessary: the discussions were on an ad hoc basis.
ORIGIN
Latin, literally ‘to this’.
Origins
Haskell language originates idea of type classes. They were first proposed in white paper:
where it starts with comparison of ad hoc and parametric polymorphism.
Parametric polymorphism
acts in the same way for each type, for example we have method List[T].length on standard Scala List defined for some type T. Even if we put Int, Float or any other type instead of T:
List[Int].length
List[Float].lengthmethod length will work in the same way i.e. it counts number of elements regardless their types.
Ad hoc polymorphism
acts in different way for each type, for example we have method ‘*’ — multiply, which takes two operands/arguments and does their multiplication. We may have different implementation and result based on operand types. For example T * T , or in Scala:
def *(x: Int, y: Int): Int = …
def *(x: Double, y: Double): Double = …mathematical multiplication of integer numbers and fractional numbers is done a little bit differently. That means argument types matter and they lead to different implementation.
Mess with Subtyping
Although subtyping polymorphism is “goto” approach in OOP paradigm, it can easily lead to high coupling, when we need to implement one or multiple interfaces. Let’s imaging we have some classes like A, B, C, D and they need to implement some interfaces like Serializable, Eq, Hashable, Printable.
Eventually, we end up that everybody needs to implement everything at the moment of a class definition. However, it would be nice to add new behaviour for existing classes on a side, i.e. somewhere in separate place, maybe even in separate file(s). If we are going to use ad hoc polymorphism, then it will be more like on below picture, i.e. more linear than hierarchical:
Implementation
In order to understand idea of Type Classes, I recommend we look at how they are originally implemented in Haskell. For example, let’s take class Num with three operations: addition, multiplication and negation
-- First comes type class definition
class Num a where
(+), (*) :: a -> a -> a
negate :: a -> a-- Then, one instance for type Int
instance Num Int where
(+) = addInt
(*) = mulInt
negate = negInt-- And another instance for type Float
instance Num Float where
(+) = addFloat
(*) = mulFloat
negate = negFloat
Whenever we want to sum, multiply or negate two integers or float numbers above type class instances will be used. More precisely, the functions these instances use on the right hand side of ‘=’ sign.
In Scala case, we can write similar type class like this:
// Type Class definition
trait Num[A] {
def +(l: A, r: A): A
def *(l: A, r: A): A
}object instances {
// instance for Int
implicit val intNum = new Num[Int] {
override def +(l: Int, r: Int): Int = l + r
override def *(l: Int, r: Int): Int = l * r
}
// instance for Float
implicit val floatNum = new Num[Float] {
override def +(l: Float, r: Float): Float = l + r
override def *(l: Float, r: Float): Float = l * r
}
}object Num {
// polymorphic functions to be used by end user
def +[A: Num](l: A, r: A): A = implicitly[Num[A]].+(l, r)
def *[A: Num](l: A, r: A): A = implicitly[Num[A]].*(l, r)
}
As Type Classes in Scala came later into the language, their implementation is not so natural and straight forward as in Haskell. There are few differences between Haskell and Scala type classes:
1. Unique type class instance in global namespace (coherence)
2. Support on language level via class and instance keywords
- Multiple instances can co-exist, but only one can be used at a time
- No special language support (via trait + implicit)
The first point above is a key difference, so called, coherence of type classes. Simply put, it is about instance uniqueness. We can compile a program in Scala having more than one instance of Num class for Int or for any other concrete type, where is in Haskell we cannot.
English word Coherence:
coherence | kə(ʊ)ˈhɪər(ə)ns, kə(ʊ)ˈhɪərəns |
noun [mass noun]
1 the quality of being logical and consistent: this raises further questions on the coherence of state policy.
2 the quality of forming a unified whole: the group began to lose coherence and the artists took separate directions.
Scala allows multiple instances to exist, but only one can be used at a time. From one hand, this can an advantage, because we can write different implementations and decide what to choose at caller site. From another hand, this feature can be error-prone, we need to be careful in selecting right type class instances. In some situations we would need to disambiguate our code and help compiler to select implicit instance manually, so that Scala can be sure what instance should be used at particular place.
Scala type class ingredients
Let’s take another example and implement a type class from scratch. The following type class allows to format some value of type T into a string.
- Trait with generic parameters
trait Formatter[A] {
def fmt(a: A): String
}2. Implicit instances with [concrete] types
object instances {
implicit val float: Formatter[Float] =
(a: Float) => s"$a f" implicit val boolean: Formatter[Boolean] =
(a: Boolean) => a.toString.toUpperCase implicit def list[A] (implicit ev: Formatter[A])
: Formatter[List[A]] =
(a: List[A]) => a.map(e => ev.fmt(e)).mkString(" :: ")
}
We have not mentioned implicit keyword yet, however this is a “backbone” of Scala 2 type classes. Implicit values allow us to summon them in polymorphic functions (in user APIs) using implicit arguments. This is happening automatically, we do not need to pass these instances manually.
Instances defined with def keyword allow us to implement, so called conditional type class instances. Above Formatter for List can format a List of A, in case there is a Formatter[A] defined around. This check by compiler will be driven by caller site. Once type A is defined by caller, Scala will try to find an instance of Formatter for A and then finally construct a Formatter for List[A]. Implementation of Formatter[List[A]] is just delegating formatting of A type to implicit instance of Formatter[A]. This feature is really useful, because it allows us to implement type class instances for high-order types once and expect those individual instances for concrete types to be available in advance. Thus, we avoid a situation when we would have to define implicit instances for all possible element types of A for List, for example Formatter[List[Boolean]], Formatter[List[Float]] and so on. This approach helps us to deal with any other “containers” like Option[A], Either[A, B], Map[K, V], etc.
3. User API (singleton object)
object Formatter {
def fmt[A](a: A) (implicit ev: Formatter[A]): String =
ev.fmt(a)
}Final step is to use implicit parameters to implement end-user API, i.e. polymorphic functions. You will see that sometimes people name this implicit parameter(s) as “ev”, which is shortening for “evidence”. This analogy highlights function requirements: function/method needs an instance of a type class for a specific user type A, if we apply this for the Formatter case above.
In Action
In order to use polymorphic functions, we now need to import implicit instances in scope to get our code compiled. Let’s finally use our fmt function:
import instances._ // important: importing implementationval floats = List(4.5f, 1f)
val booleans = List(true, false)
val integers = List(1, 2, 3)println(Formatter.fmt(floats)) // 4.5 f :: 1.0 f
println(Formatter.fmt(booleans)) // TRUE :: FALSEprintln(Formatter.fmt(integers)) // won't compile:
// could not find implicit value for parameter ev:
// Formatter[List[Int]]
As we defined formatter instances for boolean and float types, our attempt to use formatter for integer fails in compile time.
More on Implicits
As we have seen above, Scala implicit modifier is quite overloaded in terms of usage for different purposes in Scala code. This makes it quite hard to grasp for a newbie in Scala. We can summarize 3 things about implicits when it comes to use them for type classes:
a) location:
- Companion object: popular place to put your implicit instances val/defs. Compiler will look at Companion object members by default, so that we do not need to explicitly import implicit values in scope.
- Any other object or trait: we can of course put implicit instances in any other object and use import statement to bring those implicits in scope. Same applies for traits. Scala traits can have implicit definitions and we can mixin/extend such traits when we need to bring those implicit instances in scope.
b) search:
- local or inherited definitions
- imported, for example: import myInstances._
- companion object either of a type class (in example above, this will be object Formatter) or of a parameter type [A]. Formatter[MyClass] may have a type class instance inside the object MyClass.
There is a nice article from Scala documentation web-site explaining where compiler is looking for implicits: https://docs.scala-lang.org/tutorials/FAQ/finding-implicits.html
c) providers:
- val — instance as value
- def — conditional instance, when additional implicit arguments are needed to construct current type class instance
More on User API
The third part of Scala Type Classes is User API. This is the code our user is going to use, in other words these are polymorphic functions. We put our polymorphic functions into:
- singleton objects
- extension methods (syntactic sugar to enable postfix notation)
Our polymorphic functions always take one more implicit arguments.
There are few styles how Scala programmers define User API. Let’s look at Formatter object:
object Formatter { // write like this
def fmt[A](a: A)(implicit ev: Formatter[A]): String = ev.fmt(a)
// or like that using "context bounds", colon symbol
def fmt[A : Formatter](a: A) : String =
Formatter[A].fmt(a)
//line above is the same as: implicitly[Formatter[A]].fmt(a) // trick to avoid implicitly method
def apply[A](implicit ev: Formatter[A])
: Formatter[A] = ev
}
Note as for the trick with def apply function. It allows us to call Formatter[F], which is equal and shorter than the same code like implicitly[Formatter[A]].
To make our User API looks nicer, Scala gives us ability to define extension methods. It is also done via implicit keywords :-). Do not be confused as “implicit” feature is really overloaded in Scala 2. There is an example below on adding extension method fmt. It allows us to call polymorphic function in postfix way:
object syntax {
implicit class FromatterOps[A: Formatter](a: A) {
def fmt: String = Formatter[A].fmt(a)
}
}…
import syntax._println(floats.fmt) // 4.5 f :: 1.0 f
println(booleans.fmt) // TRUE :: FALSE
Object name syntax is borrowed from Cats library, where it enables extension methods for their type classes.
When to use Type Classes?
At this point, you might have a question, when it is better to use type classes and when I can go with subtyping. Some answers to this:
- Use type classes approach, in case you want to add new behavior without modification of the existing class or when subtyping is not really possible.
Using above Formatter example, we can just implement:
implicit val myType: Formatter[MyType] = ...Now our MyType class has a behavior of Formatter, however MyType class was not changed. We are also decoupled from Formatter trait, since implicit value can be defined anywhere in our code base.
Type Class approach allows us to provide an evidence that a type outside of our control conforms with some behavior. Someone else type can be a member of our typeclass, once evidence is provided.
object Formatter {
def fmt[A](a: A)(implicit ev: Formatter[A]): String =
ev.fmt(a)
}import instances._
println(Formatter.fmt(floats)(here comes implicit))
I have added a hint above just to show that fmt function takes implicit instances we imported with “import instances._” statement.
One more counterexample using subtyping:
trait Formatter {
def fmt: String = {
this match {
case v: FloatVal => s"${v.v} f"
case v: BooleanVal => v.v.toString.toUpperCase
case v: SomeNewType …
// new case popped up, we have to add new case :-(
}
}
}
case class FloatVal(v: Float) extends Formatter
case class BooleanVal(v: Boolean) extends FormatterThis code example is using pattern-matching in base type to do different things based on possible subtypes. Such approach requires continues modification of base class whenever new subtype is introduced and that is not good, because we might not have an access to base class to modify it. Another disadvantage is that base class knows about its descendants ,which is additional coupling in our code. If you found yourself in situation like above, try to rewrite such code using type class approach, if code base allows.
2. Another reason to use type classes: subtyping polymorphism dispatch dynamically, however type classes dispatch in compile time.
As we run most of the Scala programs on JVM, Java Runtime needs to resolve method, which needs to be called for a particular object in runtime by looking at object’s metadata. There are a lot of information at the Internet, why dynamic method dispatch can be bad and from other hand — useful. One of the disadvantage is performance in terms code execution time and memory usage. Of course you might not always care about these things, since you are already on JVM and not in native code execution. Nevertheless, compile-time dispatch feature of type classes is definitely an advantage, since we indicate concrete types when polymorphic functions are called. A compiler can see concrete implementations and which code should be eventually called. It does not need to derive this information in runtime.
Let’s compare polymorphism types based on our Formatter example.
Subtyping polymorphism:
trait Formatter {
def fmt: String
}case class FloatVal(v: Float) extends Formatter {
override def fmt: String = s"$v f"
}case class BooleanVal(v: Boolean) extends Formatter {
override def fmt: String = v.toString.toUpperCase
}val vals: Seq[subtyping.Formatter] =
List(FloatVal(1), BooleanVal(true), BooleanVal(false))vals.foreach(v => printf(v.fmt))
As our variable “vals” is of Seq[Formatter] type, Java Runtime needs to analyze object metadata to understand, which fmt implementation is meant to be called, when iterate over the vals sequence in foreach.
Ad hoc polymorphism:
import instances._val floats = List(4.5f, 1f)
println(Formatter.fmt[List[Float]](floats)(implicit ev))
Since we put concrete type above as List[Float], compiler knows that required Formatter must be in scope. In our example, it is imported from object called “instances”. Of course you can say that it is not fair comparison, because in subtyping example we have different types which implement Formatter trait, but in ad hoc polymorphism example above there is only one type of values in the list which is Float. That is why runtime needs to investigate, which implementation to call. However, even subtyping example can be done using type classes. There is an example I took from Rob Noris blog post and adopted for our Formatter example: https://tpolecat.github.io/2015/04/29/f-bounds.html
Basically, what we want to get is a Heterogeneous List, which is a list where every element can be a different type than other element in this list.
// we invent a wrapper W to be able to put different Formatters
// in the listtrait W[F[_]] {
type A
val a: A
val fa: F[A]
}object W {
def apply[F[_], A0](a0: A0)(implicit ev: F[A0]): W[F] =
new W[F] {
type A = A0
val a = a0
val fa = ev
}
}// this wrapper also needs its own type class instance
implicit val e: Formatter[W[Formatter]] =
(w: W[Formatter]) => w.fa.fmt(w.a)// and now we can construct a list with different elements
val hlist = List(W(1f), W(true), W(2f))
println(hlist.fmt)
Above hlist has two float and one boolean values. List construction is type-checked in compile time. There is no class casting involved. Compiler is checking that every wrapped element has its own Formatter around. So as long as Formatter[Float] and Formatter[Boolean] are in scope, above code compiles. However, once we put a value of some type, which does not have its own instance of Formatter[X] around, then that code won’t compile. Again, compile-time dispatch. Huge win!
List(.. W(2)) // Int - won’t compile, because no instance around3. Use type classes when it comes to write a library.
As library authors, we want to keep our API extendable for new type members. If we take Formatter example, we can have default type class instances for all possible Scala collections. However when it comes to some user types, which we cannot be aware of and we do not want to be aware of, we give a possibility to a library user to provide us evidences that their new type members can work with our library type classes (polymorphic functions).
Examples of type classes can be found in many popular Scala libraries:
- Cats: Semigroup, Monoid, Applicative, Monad, Traversable
- Play-JSON: Reader, Writer
- uPickle: Reader, Writer
- Circe: Encoder, Decoder
- Scata std library: scala.math.Ordering, scala.math.Numeric
- + other 100500 Scala libraries
Reducing boilerplate with macroses
Writing many type classes from scratch may be quite boring and repetitive. In order to reduce amount of boilerplate code we can use Scala library Simulacrum. This library is generating that amount of code we would need to write manually. First we need to add it as a project dependency and compiler plugin which Simulacrum is using. SBT configuration:
“org.typelevel” %% “simulacrum” % "<version>"
addCompilerPlugin(“org.scalamacros” % “paradise” % “<version>”)Now we can apply Simulacrum annotations to generate some of our code automatically:
import simulacrum._@typeclass trait Formatter[A] {
def fmt(a: A): String
}
Once we compile above code, it will produce some amount of Java byte code on a disk:
Now we can import those generated objects plus instances which we still need to write ourselves (of course!) and use generated polymorphic functions:
import Formatter.ops._import instances._object Main extends App {
print(true.fmt)
}
In the result, we have only defined type class definition and required for us type class instances. Then, we are ready to use type classes in our main code.
If we compare with what we had to write ourselves before using Simulacrum, then this is what has been removed, so no need to write this code below:
object syntax { implicit class FromatterOps[A: Formatter](a: A) {
def fmt: String = Formatter[A].fmt(a)
}
}object Formatter {
def fmt[A: Formatter](a: A): String =
Formatter[A].fmt(a) def apply[A](implicit formatter: Formatter[A]): Formatter[A] =
formatter
}
In summary, Simulacrum helps us with steps #1 and #3 according to our ingredients list, we have discussed above. Point #2 is still on us, since nobody knows in advance how exactly you would like to implement a type class instance for some type A.
Summary
Type classes is a powerful feature, which is used a lot in functional and type level programming. The main strength of type classes is that they allow to decouple type class definition from concrete implementation and achieve fewer couling than with subtyping polymorphism. There are other languages, which have type classes in some form:
- Agda (instance arguments)
- Coq
- Rust
- Mercury
- Clean
There are not only Haskell and Scala developers who love type classes, but other languages which consider this feature useful. I hope this article helped you in your way of learning type classes in Scala.
Links I used during the research on type classes in Scala and in general:
