Scala Type Classes comparison

Published in

SE Notes by Alexey Novakov

7 min readNov 25, 2019

In the first article we discussed how Type Classes are encoded in Scala. In the second article we are going to compare Scala type class implementation with Java, Rust and Scala 3, which is new version of Scala compiler. Before comparing Scala 2 type classes encoding we will discuss some of the drawbacks of this feature.

Current Scala Drawbacks

Before we look at new version of Scala 3, let us summarize what are the current drawbacks of main Scala version, which is 2.13 as of writing this article.

No language level support. One can encode type classes using traits, implicits and objects. Quick look back:

trait Formatter[A] { … }object instances {
  implicit val …
  implicit val …
  implicit def …
}
object syntax {
  implicit class FromatterOps[A: Formatter](a: A) {
    …
  }
}

It would be nice to get rid some of ceremonies and get support from the language.

2. Ambiguous instances error

That it the main problem as for me. Since we can have non-unique instances defined in our program or in imported libraries, sometimes we have to disambiguate type classes usage in our program, i.e. to tell compiler explicitly which instance we meant. Event if we do not care which instance will be used for some particular type, we have to leave only one in scope for a caller site.

One of the example of this problem is described here in this paper:

The Limitations of Type Classes as Subtyped Implicits https://adelbertc.github.io/publications/typeclasses-scala17.pdf

You can see that this problem with implicits related to type classes even led to writing a white paper about it :-)

Here is an example of this problem:

      Functor
  +---->   <----+
  |             |
  |             |
  |             |
Monad        Traverse

Monad and Traverse type classes can share common base type, which is Functor, i.e. they both need map function. In case we have polymorphic function like this:

def myFunc[F[_] : Traverse : Monad] =   
  println(implicitly[Functor[F]].map(…))

in function body we need a Functor instance for type F[_] to map over this type, however later in this function body we need a Traverse and then Monad. So we need both type classes, but at some point we just need a Functor, which we know it is a base type for both. In situation, we will have compile-time error:

Error:(12, 23) ambiguous implicit values:
both value evidence$2 of type Monad[F]
and value evidence$1 of type Traverse[F]
match expected type Functor[F]

There are some techniques how to disambiguate type classes in this situation. However, they require writing additional code or thinking on how to avoid such code situations where base type classes may clash in their children type classes, when both are in scope.

In case you use Cats library or will be using it, then you may find yourself in such situation. Different Cats imports may bring clashing instances, so that you need to be careful with what to import or perhaps choose some strategy either always use cats.implicits import or import exact instances one by one. Implicit disambiguation approach is relatively clear for the code you control or wrote, but it is much harder to understand such problems, if a clash is coming due to conflicting instances from the 3rd party library.

3. Multi-parameter Type Classes

Type Classes can have more than one type parameter. When we implement an instance of such type, we need to specify all types. Let’s imagine a trait with addition operation:

trait Add[A, B, C] {
  def +(a: A, b: B): C
}

Ideally, we need to confirm this operation with mathematical laws. If A or B operand is Double, result must be Double. However, we can define different combination of instances and they will compile.

Possible type class instances:

implicit val intAdd1: Add[Int, Int, Double] =
  (a: Int, b: Int) => a + bimplicit val intAdd2: Add[Int, Int, Int] =
  (a: Int, b: Int) => a + b

Notice that first instance returns Double type as a result, which does not makes sense from math perspective, however someone would want such behaviour in some cases. Problem with multi-parameter type classes that we cannot specify dependencies among type parameters easily and disallow some combinations of them.

Comparison with Java

Java developers looks at Scala type classes

In case you have Java experience, there is example below showing how Scala type classes could be implemented in Java at certain degree. However, there is a lack of some implicit constructions, which immediately neglects the whole idea of type classes and makes it impossible:

public interface Formatter<T> {
  String fmt(T t);
}class instances {
  static Formatter<String> string = 
    s -> String.format("string: %s", s);
  
  static Formatter<Integer> integer = 
    i -> String.format("int: %s", i);
}class Api {
  static <T> String fmt(T t, Formatter<T> ev) {
    return ev.fmt(t);
  }
}…public static void main(String[] args) {   
  System.out.println(Api.fmt("some string", instances.string));   
  System.out.println(Api.fmt(4, instances.integer));
}

We pass type class instances as static variable of class called “instances”, i.e. we are doing this explicitly, which is quite weird.

Comparison with Rust

If you are Rust programmer, you will probably find better understanding of Scala type classes, by looking at Rust translation below. If you have no clue how Rust is implementing similar ideas like Haskell Type Classes, then below example might be interesting to see as well. Rust example might be a good motivator for you to finally study what is type classes at all.

Some Rust characteristics with regards to type classes:

Rust supports traits, which are a limited form of type classes with coherence
Instances can be also defined conditionally
Does not support higher-kinded types <T<U>>

Example:

// trait with generic type T
pub trait Formatter<T> {
  fn fmt(&self) -> String;
}// type instance for string
impl Formatter<Self> for &str {
  fn fmt(&self) -> String {
    "[string: ".to_owned() + &self + "]"
  }
}// type instance for integer
impl Formatter<Self> for i32 {
  fn fmt(&self) -> String { 
    "[int_32: ".to_owned() + &self.to_string() + "]"
  }
}// type instance for Vec<T>
impl<T: Formatter<T>> Formatter<Self> for Vec<T> { 
  fn fmt(&self) -> String {
    self.iter().map(|e| e.fmt()).collect::<Vec<_>>().join(" :: ")
  }
}// polymorphic function
fn fmt<T>(t: T) -> String where T: Formatter<T> {
  t.fmt()
}

Polymorphic function above is really unnecessary in Rust, since postfix notation work out-of-the box for Rust traits when using “self” pointer.

Rust in Action

We have implemented Formatter trait for string, integer and vector.

let x = fmt("Hello, world!”); // or “Hello…”.fmt()
let i = 4.fmt();
let ints = vec![1, 2, 3].fmt();println!("{}", x); // [string: Hello, world!]
println!("{}", i); // [int_32: 4]
println!("{}", ints) // [int_32: 1] :: [int_32: 2] :: [int_32: 3]

If we try to use fmt function for some other type, which does not have implementation for Formatter, then it fails in compile time.

let floats = fmt(vec![1.0, 2.0, 3.0]);error[E0277]: the trait bound `{float}: Formatter<{float}>` is not satisfied
--> src/main.rs:31:18
|
31 |     let floats = fmt(vec![1.0, 2.0, 3.0]);
|                  ^^^ the trait `Formatter<{float}>` is not implemented for `{float}`
|
= help: the following implementations were found:
<&str as Formatter<&str>>
<i32 as Formatter<i32>>
<std::vec::Vec<T> as Formatter<std::vec::Vec<T>>>
= note: required because of the requirements on the impl of `Formatter<std::vec::Vec<{float}>>` for `std::vec::Vec<{float}>`
note: required by `fmt`
--> src/main.rs:23:1
|
23 | fn fmt<T>(t: T) -> String where T: Formatter<T> {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

As we can see, compiler says there were 3 other implementations found, but none for Formatter<Float>.

Future Of Type Classes in Scala

In new version of Scala 3, which is also known as Dotty, type classes received proper attention. The “implicit” modifier has been replaced by “given” modifier with some syntax around it. This change should bring some clarity in how to work in Scala with implicit arguments, values, imports, etc. In my opinion, it is good change. It should help new Scala programmers to grasp power of the language faster, instead of searching for different applications of implicit keyword in different contexts of their programs. In the latest release of Scala 3 as of November 2019, we can now encode our Formatter type classes as below:

trait Formatter[A] {
  def (a: A)fmt: String
}given Formatter[Float] {
  def (a: Float) fmt: String = s"$a f"
}given Formatter[Boolean] {
  def (a: Boolean) fmt: String = a.toString.toUpperCase
}given [T:Formatter]: Formatter[List[T]] {
  def (l: List[T]) fmt: String = 
   l.map(e => summon[Formatter[T]].fmt(e)).mkString(" :: ")
}

Above code mimics our Scala 2 implementation sequence. Type class definition is still defined using traits. Then we have 3 type class instances. The last one is conditional instance for a List of a type T as long Formatter of T is given. New method called summon replaces old method implicitly. Old implicit and implicitly method still work, but will be deprecated in some future versions of Scala 3.x or 4.

import formatting.{given, _}
import formatting.Formatterobject Main {
  def main(args: Array[String]): Unit =  {
    println(List[Float](1f, 2f).fmt)
    println(2f.fmt)   
    println(List[Boolean](true, false).fmt)
    println(true.fmt)
  }
}
// prints:
1.0 f :: 2.0 f
2.0 f
TRUE :: FALSE
TRUE

Imports of those “given” instances is now done explicitly using given keyword in import statements. The problem with ambiguous instances is mitigated by this new feature, i.e. now user needs to explicitly import “given” instances. It is possible to import “given” instances for a type. Probably, so called, type class “coherence” in Scala will be never solved on JVM, due its dynamic class loading nature.

Additionally, we do not need to write extension methods manually. You might have noticed new syntax, when we defined single method in the trait. Method name can be written after the arguments, which allows to apply this method in postfix notation. That means we do not need Simulacrum plugin any more. The latest video you can find about Scala 3 and implicits is a keynote of Martin Odersky at Lambda World 2019: https://www.youtube.com/watch?v=uPd9kJq-Z8o