<img height="1" width="1" src="https://www.facebook.com/tr?id=1076094119157733&amp;ev=PageView &amp;noscript=1">

This blogpost is the first of a series about "Type level programming in Scala", covering all the topics and techniques that I had to learn in order to do develop my side project troy.

In this post, I'll be taking a code-first approach, building real world usecases, step-by-step. No strong FP jargon, I promise!

Sorting in Java

Wait, what? Isn't this post about Scala?
Yes, it is. But we'll start from Java land, all the way down to idiomatic Scala! So bare with me.

Now, let's sort some ArrayLists!

import java.util._
// import java.util._

val l = new ArrayList[String]()
// l: java.util.ArrayList[String] = []

l.add("Foo"); l.add("Bar"); l.add("Baz")
// res0: Boolean = true

Collections.sort(l)

println(l)
// [Bar, Baz, Foo]

The example above works because Java knows how to sort Strings, as they implement java.lang.Comparable. So if we have a custom class that we'd like to sort, we'll need to implement the Comparable interface too.

case class Employee(name: String) extends Comparable[Employee] {
  override def compareTo(o: Employee): Int = this.name.compareTo(o.name)
}
// defined class Employee

Now we can sort an ArrayList of Employee too.

val l2 = new ArrayList[Employee]
// l2: java.util.ArrayList[Employee] = []

l2.add(Employee("Foo")); l2.add(Employee("Bar")); l2.add(Employee("Baz"))
// res3: Boolean = true

Collections.sort(l2)

println(l2)
// [Employee(Bar), Employee(Baz), Employee(Foo)]

However, the solution above might not be suitable if we don't own the class Employee (i.e it is defined in some other 3rd part lib). Fortunately, there is an alternative solution in Java land.

case class Employee(name: String)
// defined class Employee

class EmployeeComparator extends Comparator[Employee] {
  override def compare(o1: Employee, o2: Employee): Int =
    o1.name.compareTo(o2.name)
}
// defined class EmployeeComparator

val l3 = new ArrayList[Employee]; l3.add(Employee("Foo")); l3.add(Employee("Bar")); l3.add(Employee("Baz"))
// l3: java.util.ArrayList[Employee] = [Employee(Foo), Employee(Bar), Employee(Baz)]
// res6: Boolean = true

Collections.sort(l3, new EmployeeComparator)

println(l3)
// [Employee(Bar), Employee(Baz), Employee(Foo)]

We've just extracted the comparing functionality into a separate class whose only purpose it to sort our class. This pattern is more or less what we call a "type-class"! However, our example above is very verbose, we now try to rewrite it in an idiomatic Scala syntax.

Back to Scala

Let's first build our own version of Comparator and sort, then try to make them more idiomatic step-by-step

trait Comparator[T] {
  def compare(o1: T, o2: T): Int
}

object Collections {
  // Inefficient quick sort implementation
  def sort[T](xs: Seq[T], comparator: Comparator[T]): Seq[T] =  xs match {
    case Seq() => Seq.empty
    case head +: tail =>
      val (st, gte) = tail.partition(comparator.compare(xs.head, _) > 0)
      sort(st, comparator) ++ Seq(head) ++ sort(gte, comparator)
  }
}

Now let's define our Employee comparator

object EmployeeComparator extends Comparator[Employee] {
  override def compare(o1: Employee, o2: Employee): Int =
    o1.name.compareTo(o2.name)
}

Notice that EmployeeComparator is a singleton object rather than a class, since we don't wish to parameterise it.

val l = Seq[Employee](Employee("Foo"), Employee("Bar"), Employee("Baz"))
// l: Seq[Employee] = List(Employee(Foo), Employee(Bar), Employee(Baz))

Collections.sort(l, EmployeeComparator)
// res10: Seq[Employee] = List(Employee(Bar), Employee(Baz), Employee(Foo))

Concise syntax using Implicits

Passing the comparator param is definitely very verbose. Luckily Scala has a feature for us that makes calling the sort function a little bit more concise.

object Collections {
  def sort[T](xs: Seq[T])(implicit comparator: Comparator[T]): Seq[T] = xs match {
    case Seq() => Seq.empty
    case head +: tail =>
      val (st, gte) = tail.partition(comparator.compare(xs.head, _) > 0)
      sort(st) ++ Seq(head) ++ sort(gte)
  }
}
// defined module Collections

In the example above, we defined comparator in a separate parameter list, that is marked with implicit modifier. This modifier instructs Scala to look if for a suitable value (of the right type) to be passed in the method call. As you see in line 6, we didn't have to specify the parameter comparator ourselves, it has been implicitly specified for us!

Likewise, by marking our Comparator instances as implicit, we'll be able to call sort without specifying the comparator explicitly.

implicit object EmployeeComparator extends Comparator[Employee] {
  override def compare(o1: Employee, o2: Employee): Int =
    o1.name.compareTo(o2.name)
}
Collections.sort(l)
// res11: Seq[Employee] = List(Employee(Bar), Employee(Baz), Employee(Foo))

Recursive implicits

Scala's implicits search allows implicit definitions to depend on each other. For example, let's build on top a Comparator for Option[Employee].

implicit val optionOfEmployeeComparator = new Comparator[Option[Employee]] {
  override def compare(o1: Option[Employee], o2: Option[Employee]): Int =
    (o1, o2) match {
      case (None, None) => 0
      case (None, Some(_)) => -1
      case (Some(_), None) => 1
      case (Some(e1), Some(e2)) => EmployeeComparator.compare(e1, e2)
    }
}

The example above works only for Option[Employee], but the implementation itself can work for Option of any type (as longs as this type has a comparator instance). Luckily we have a way to do this:

implicit def optionComparator[T](implicit innerComparator: Comparator[T]) = new Comparator[Option[T]] {
  override def compare(o1: Option[T], o2: Option[T]): Int =
    (o1, o2) match {
      case (None, None) => 0
      case (None, Some(_)) => -1
      case (Some(_), None) => 1
      case (Some(e1), Some(e2)) => innerComparator.compare(e1, e2)
    }
}
// optionComparator: [T](implicit innerComparator: Comparator[T])Comparator[Option[T]]

Collections.sort(Seq(Some(Employee("Foo")), None, Some(Employee("Bar")), Some(Employee("Baz"))))
// res12: Seq[Option[Employee]] = List(None, Some(Employee(Bar)), Some(Employee(Baz)), Some(Employee(Foo)))

Notice that optionComparator is now defined as a def rather than a val. This function accepts only implicit params, that is a kind of precondition that must be fulfilled in order to use this function. Read it as "we have Comparator[Option[T]], as long as there is a Comparator[T]"

The compiler will now search for a suitable instance of the type-class, or at least, a way to derive it. So it finds a way to derive Comparator[Option[T]] (optionComparator), but it depends on Comparator[T]. Luckily we have EmployeeComparator which fulfils the requirement.

If we tried with Option[Int] for example, the code won't compile

Collections.sort(Seq(Some(1), None, Some(3), Some(2)))
// <console>:18: error: could not find implicit value for parameter comparator: Comparator[Option[Int]]
//               Collections.sort(Seq(Some(1), None, Some(3), Some(2)))
//                               ^

Unless, we defined an instance for Ints!

implicit val intComparator = new Comparator[Int] {
  override def compare(o1: Int, o2: Int): Int = o1 - o2
}
// intComparator: Comparator[Int] = [email protected]

Now it works.

Collections.sort(Seq(Some(1), None, Some(3), Some(2)))
// res14: Seq[Option[Int]] = List(None, Some(1), Some(2), Some(3))

Wrapping up

We have seen how to implement Typeclass pattern elegantly using implicits. In the next blog, we will introduce HLists, and use it to enrich our example to able to derive type-class instances for any case class!

Finally

I'll be giving a talk titled "How to program the type system" in Scala-Swarm this June. I'll be showing how Scala's typesystem is capable of typechecking SQL-like queries against a schema (without connecting to the database at compile-time, no cheating)!

Checkout the conference at scala-swarm.org.

Recent Posts

Posts by Topic

see all

Subscribe to Email Updates