Polymorphism in Scala — Part 1
The purpose of this article is to talk about Polymorphism while we trying to implement a simple, but non trivial, functionality.
The Problem
Our task, if we want to accept it, is to implement a function quicksort that allow us to sort a List, of anything, through the quicksort algorithm.
If we establish that Nil is the empty list and [x|xs] is a non empty list composed by a head x and a tail xs, quicksort is a recursive algorithm with two premises.
quicksort(Nil) ⇒ Nilquicksort(x|xs) ⇒ quicksort( y / y ∈ xs & y ≤ x ) + x + quicksort( y / y ∈ xs & y > x )
As you can see, we need, in some way, compare the elements on the List in order to know which is smaller or bigger.
If it was hard to understand, here you are some awesome guys that can explain it better than me.
Up to this point the problem is clear, let’s try to solve it.
Polymorphism
Oh Wait… I was going to talk about polymorphism.
There are many ways to define polymorphism, we can say that two entities are polymorphic if they can be seen as equal in the eyes of a third party.
If we are talking about types, a polymorphic type is the one whose operations can be applied to another types.
The most commonly classes of polymorphism are:
- Sub-typing
- Parametric
- Ad hoc
In order to accomplish our task we need that our Lists or its elements would be polymorphic because we want to apply our quicksort function to any kind of List.
Sub-typing Polymorphism
In general terms, it is a kind of polymorphism in which a type (sub-type) is related to another (super-type) in a way where operations that apply to the super-type can also apply to its sub-types.
In Scala we are talking about sub-typing when a type inherits from another.
Our first approach will be implement an interface in which we delegate the comparing behavior.
trait Comparable[A] {
def compareTo(other:A):Int
}Then will be easy to implement our quicksort.
def quicksort[A <: Comparable[A]](xs: List[A]):List[A] = {
xs match {
case Nil => Nil
case x :: ys => {
val smallers = ys.filter( elem => elem.compare(x) <= 0 )
val biggers = ys.filter( elem => elem.compare(x) > 0 )
quicksort(smallers) ::: x :: quicksort(biggers)
}
}
}Let’s test our function.
case class Dog(name:String, age:Int) extends Comparable[Dog] {
def compareTo(other: Dog): Int = {
if(age < other.age) -1
else if(age == other.age) 0
else 1
}
}val dogs = List(Dog("Spike", 4), Dog("Toto", 3), Dog("Beethoven", 7))
quicksort(dogs)
// List(Dog(Toto,3), Dog(Spike,4), Dog(Beethoven,7))
Everything seems to be fine, but we have some issues here.
First the good news, our implementation is extensible. If we create a new type A and we want to sort a List[A], the only thing we need to do is inherit from Comparable[A].
But it’s not all a bed of roses, we are tied to a single implementation (we can sort our dogs by name or age, only one of them) and the most important issue is that types that are not ours can’t implement Comparable[A], so the following code doesn’t compile.
quicksort(List(3,5,6,8,0,3,1))
quicksort(List("Spider-Man", "Captain America", "Iron Man"))Duck Typing to the Rescue!
Luckily for us, Scala has Structural Types and classes like String or Int have a compareTo method.
We can try to change our Trait into a type but there is a problem.
type Comparable[A] = {
def compareTo(other:A):Int
}
// ERROR: Parameter type in structural refinement may not refer to an abstract type defined outside that refinementIf it compiled it wouldn’t be possible to use quicksort with many types, because there are a lot of them that don’t implement a compareTo method.
Parametric Polymorphism
It is a kind of polymorphism where types, methods or functions can be written generically so they can handle values without depending on their types. In Scala is implemented through Type Parameters.
For instance, on List, the head method is polymorphic because it doesn’t matter which type of elements it contains, it works in the same way.
List(1, 2, 3).head
// 1List("Spider-Man", "Captain America", "Iron Man").head
// Spider-Man
Let’s try to improve our function in order to be more generic.
def quicksort[A](xs: List[A], f: (A, A) => Int): List[A] = {
xs match {
case Nil => Nil
case x :: ys => {
val smallers = ys.filter(elem => f(elem, x) <= 0)
val biggers = ys.filter(elem => f(elem, x) > 0)
quicksort(smallers, f) ::: x :: quicksort(biggers, f)
}
}
}Now, our function works with any Type, we just need to provide a way to compare the elements. It is still extensible and we are not tied to a single comparing implementation.
quicksort[Dog](dogs, (d1, d2) => d1.age.compareTo(d2.age) )
// List(Dog(Toto,3), Dog(Spike,4), Dog(Beethoven,7))
quicksort[Dog](dogs, (d1, d2) => d1.name.compareTo(d2.name) )
// List(Dog(Beethoven,7), Dog(Spike,4), Dog(Toto,3))quicksort[Int](List(3,5,6,8,0,3,1), _.compareTo(_))
// List(0, 1, 3, 3, 5, 6, 8)
It seems perfect but there is something that bother me. We always need to provide the comparing function, even for common types like String, Int or Tuples. It would be nice if quicksort didn’t require the function for those types.
We can implement a repository of comparators, but they need to be used explicitly (yes, I think you know where we are going).
object Comparators {
val IntComparator = (a:Int, b:Int) => a.compareTo(b)
val StringComparator = (a:String, b:String) => a.compareTo(b)
...
}Ad hoc Polymorphism
Finally, we are talking about ad hoc polymorphism, known as method or function overloading, when functions or methods can be applied to arguments of different types due they have many implementations depending on the type of the arguments to which they are applied.
It isn’t a feature of the type system and let say that someone else (*cof* the compiler *cof*) decide for us which implementation is the correct.
String and Int are polymorphic on the eyes of combine, we can call it without specify which implementation we need to execute.
def combine(a:String, b:String):String = a + b
def combine(a:Int, b:Int):Int = a + bWe can try to solve our last issue overloading quicksort in order to provide implementations for common types.
def quicksort(xs: List[Int]): List[Int] = ???
def quicksort(xs: List[String]): List[String] = ???
def quicksort(xs: List[Boolean]): List[Boolean] = ???But we are buying two more problems. The code above doesn’t compile because of type erasure (there is a way to solve that but it is more a hack than a elegant solution). The second is that we are tied again to a single implementation per type.
To face our task it seems that the best approach was the parametric polymorphism but… there is something more about ad hoc polymorphism that we should need to check before drawing any conclusion.
That’s all for the moment, thanks for reading and I hope to see you again in the second part.
