Many software engineers may not need to explicitly deal with type parameterization or generic types in their day-to-day job, but it’s very likely that the libraries and frameworks that they’re heavily using have already done their duty to ensuring static type-safety via such parametric polymorphism feature.

In a static-typing functional programming language like Scala, such feature would often need to be used first-hand in order to create useful functions that ensure type-safety while keeping the code lean and versatile. Generics is apparently taken seriously in Scala’s inherent language design. That, coupled with Scala’s implicit conversion, constitutes a signature feature of Scala’s. Given Scala’s love of “smileys”, a few of them are designated for the relevant functionalities.

**Merge Sort**

Merge Sort is a popular text-book sorting algorithm that I think also serves a great brain-teasing programming exercise. I have an old blog post about implementing Merge Sort using Java Generics. In this post, I’m going to use Merge Sort again to illustrate Scala’s type parameterization.

By means of a merge function which recursively merge-sorts the left and right halves of a partitioned list, a basic Merge Sort function for integer sorting might be something similar to the following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def mergeSort(l: List[Int]): List[Int] = { def merge(l: List[Int], r: List[Int]): List[Int] = (l, r) match { case (Nil, _) => r case (_, Nil) => l case (lHead :: lTail, rHead :: rTail) => if (lHead < rHead) lHead :: merge(lTail, r) else rHead :: merge(l, rTail) } val n = l.length / 2 if (n == 0) l else { val (r, s) = l splitAt n merge(mergeSort(r), mergeSort(s)) } } |

A quick test …

1 2 3 4 5 |
scala> val li = List(9, 5, 16, 3, 4, 11, 8, 12) li: List[Int] = List(9, 5, 16, 3, 4, 11, 8, 12) scala> mergeSort(li) res1: List[Int] = List(3, 4, 5, 8, 9, 11, 12, 16) |

Contrary to Java Generics’ MyClass<T> notation, Scala’s generic types are in the form of MyClass[T]. Let’s generalize the integer Merge Sort as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def mergeSort[T](l: List[T]): List[T] = { def merge(l: List[T], r: List[T]): List[T] = (l, r) match { case (Nil, _) => r case (_, Nil) => l case (lHead :: lTail, rHead :: rTail) => if (lHead < rHead) lHead :: merge(lTail, r) else rHead :: merge(l, rTail) } val n = l.length / 2 if (n == 0) l else { val (r, s) = l splitAt n merge(mergeSort(r), mergeSort(s)) } } |

1 2 3 |
<console>:15: error: value < is not a member of type parameter T if (lHead < rHead) ^ |

The compiler immediately complains about the ‘<' comparison, since T might not be a type that supports ordering for '<' to make any sense. To generalize the Merge Sort function for any list type that supports ordering, we can supply a parameter in a curried form as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Generic Merge Sort using math.Ordering import math.ordering def mergeSort[T](l: List[T])(order: Ordering[T]): List[T] = { def merge(l: List[T], r: List[T]): List[T] = (l, r) match { case (Nil, _) => r case (_, Nil) => l case (lHead :: lTail, rHead :: rTail) => if (order.lt(lHead, rHead)) lHead :: merge(lTail, r) else rHead :: merge(l, rTail) } val n = l.length / 2 if (n == 0) l else { val (r, s) = l splitAt n merge(mergeSort(r)(order), mergeSort(s)(order)) } } |

Another quick test ...

1 2 3 4 5 6 7 8 9 10 11 |
scala> val li = List(9, 5, 16, 3, 4, 11, 8, 12) li: List[Int] = List(9, 5, 16, 3, 4, 11, 8, 12) scala> mergeSort(li)(Ordering[Int]) res2: List[Int] = List(3, 4, 5, 8, 9, 11, 12, 16) scala> val ls = List("banana", "pear", "orange", "grape", "apple", "strawberry", "guava", "peach") ls: List[String] = List(banana, pear, orange, grape, apple, strawberry, guava, peach) scala> mergeSort(ls)(Ordering[String]) res3: List[String] = List(apple, banana, grape, guava, orange, peach, pear, strawberry) |

That works well, but it's cumbersome that one needs to supply the corresponding Ordering[T] for the list type. That's where implicit parameter can help:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Generic Merge Sort using implicit math.Ordering parameter import math.Ordering def mergeSort[T](l: List[T])(implicit order: Ordering[T]): List[T] = { def merge(l: List[T], r: List[T]): List[T] = (l, r) match { case (Nil, _) => r case (_, Nil) => l case (lHead :: lTail, rHead :: rTail) => if (order.lt(lHead, rHead)) lHead :: merge(lTail, r) else rHead :: merge(l, rTail) } val n = l.length / 2 if (n == 0) l else { val (r, s) = l splitAt n merge(mergeSort(r), mergeSort(s)) } } |

Testing again ...

1 2 3 4 5 |
scala> mergeSort(li) res3: List[Int] = List(3, 4, 5, 8, 9, 11, 12, 16) scala> mergeSort(ls) res4: List[String] = List(apple, banana, grape, guava, orange, peach, pear, strawberry) |

Note that the 'if (lHead < rHead)' condition is now replaced with 'if (order.lt(lHead, rHead))'. That's because math.Ordering defines its own less-than method for generic types.

Let's dig a little deeper into how it works. Scala's math.Ordering extends Java’s Comparator interface and implements method compare(x: T, y: T) for all the common types, Int, Long, Float, Double, String, etc. It then provides all these lt(x: T, y: T), gt(x: T, y: T), …, methods that know how to perform all the less-than, greater-than comparisons for various types.

The following are highlights of math.Ordering’s partial source code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Scala's math.Ordering source code highlight import java.util.Comparator ... trait Ordering[T] extends Comparator[T] with PartialOrdering[T] with Serializable { ... def compare(x: T, y: T): Int ... override def lt(x: T, y: T): Boolean = compare(x, y) < 0 override def gt(x: T, y: T): Boolean = compare(x, y) > 0 ... } ... object Ordering extends LowPriorityOrderingImplicits { def apply[T](implicit ord: Ordering[T]) = ord ... trait IntOrdering extends Ordering[Int] { def compare(x: Int, y: Int) = if (x < y) -1 else if (x == y) 0 else 1 } implicit object Int extends IntOrdering ... trait StringOrdering extends Ordering[String] { def compare(x: String, y: String) = x.compareTo(y) } implicit object String extends StringOrdering ... } |

**Scala’s math.Ordered versus math.Ordering**

Note that math.Ordering does not overload comparison operators ‘<', '>‘, etc, which is why method lt(x: T, y: T) must be used instead in mergeSort for the ‘<' operator.

Scala's math.Ordered extends Java’s Comparable interface (instead of Comparator) and implements method compareTo(y: T), derived from math.Ordering’s compare(x: T, y: T) via implicit parameter. One nice thing about math.Ordered is that it consists of overloaded comparison operators.

The following highlights partial source code of math.Ordered:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Scala's math.Ordered source code highlight trait Ordered[A] extends Any with java.lang.Comparable[A] { ... def compare(that: A): Int def < (that: A): Boolean = (this compare that) < 0 def > (that: A): Boolean = (this compare that) > 0 def <= (that: A): Boolean = (this compare that) <= 0 def >= (that: A): Boolean = (this compare that) >= 0 def compareTo(that: A): Int = compare(that) } object Ordered { implicit def orderingToOrdered[T](x: T)(implicit ord: Ordering[T]): Ordered[T] = new Ordered[T] { def compare(that: T): Int = ord.compare(x, that) } } |

Using math.Ordered, an implicit method, implicit orderer: T => Ordered[T], (as opposed to an implicit value when using math.Ordering) is passed to the mergeSort function as a curried parameter. As illustrated in a previous blog post, it’s an implicit conversion rule for the compiler to fall back to when encountering problem associated with type T.

Below is a version of generic Merge Sort using math.Ordered:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Generic Merge Sort using implicit math.Ordered conversion import math.Ordered def mergeSort[T](l: List[T])(implicit orderer: T => Ordered[T]): List[T] = { def merge(l: List[T], r: List[T]): List[T] = (l, r) match { case (Nil, _) => r case (_, Nil) => l case (lHead :: lTail, rHead :: rTail) => if (lHead < rHead) lHead :: merge(lTail, r) else rHead :: merge(l, rTail) } val n = l.length / 2 if (n == 0) l else { val (r, s) = l splitAt n merge(mergeSort(r), mergeSort(s)) } } |

1 2 3 4 5 |
scala> mergeSort(li) res5: List[Int] = List(3, 4, 5, 8, 9, 11, 12, 16) scala> mergeSort(ls) res6: List[String] = List(apple, banana, grape, guava, orange, peach, pear, strawberry) |

**View Bound**

A couple of notes:

- The implicit method ‘implicit orderer: T => Ordered[T]‘ is passed into the mergeSort function also as an implicit parameter.
- Function mergeSort has a signature of the following common form:

1 2 3 4 |
// Implicit method passed in as implicit parameter def someFunction[T](x: SomeClass[T])(implicit imp: T => AnotherClass[T]): WhateverClass[T] = { ... } |

Such pattern of implicit method passed in as implicit paramter is so common that it’s given the term called View Bound and awarded a designated smiley ‘<%'. Using view bound, it can be expressed as:

1 2 3 4 |
// View Bound def someFunction[T <% AnotherClass[T]](x: SomeClass[T]): WhateverClass[T] = { ... } |

Applying to the mergeSort function, it gives a slightly more lean and mean look:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Generic Merge Sort using view bound import math.Ordered def mergeSort[T <% Ordered[T]](l: List[T]): List[T] = { def merge(l: List[T], r: List[T]): List[T] = (l, r) match { case (Nil, _) => r case (_, Nil) => l case (lHead :: lTail, rHead :: rTail) => if (lHead < rHead) lHead :: merge(lTail, r) else rHead :: merge(l, rTail) } val n = l.length / 2 if (n == 0) l else { val (r, s) = l splitAt n merge(mergeSort(r), mergeSort(s)) } } |

As a side note, while the view bound looks like the other smiley '<:' (Upper Bound), they represent very different things. An upper bound is commonly seen in the following form:

1 2 3 4 |
// Upper Bound def someFunction[T <: S](x: T): R = { ... } |

This means someFunction takes only input parameter of type T that is a sub-type of (or the same as) type S. While at it, a Lower Bound represented by the '>:’ smiley in the form of [T >: S] means the input parameter can only be a super-type of (or the same as) type S.