Bartosz Witkowski - Blog.
Home About me

# Basics

## Comparable/Ordered

In java there’s a Comparable interface that defines a compareTo method used for sorting/comparing objects.

For the unaware, comparing in Java works as follows - the compareTo method returns a value $x$ such that:

and $x = 0$ otherwise.

On the other hand Scala, defines a Ordered trait that extends the Java Comparable interface. Because mixin composition in Scala is possible, the Ordered trait defines some additional concrete methods that depend on the compare method.

By default the compareTo method is an alias for the abstract compare method (this is mostly because in Scala &lt 2.8 Ordered didn’t extend Comparable).

As you can see, Ordered[T] in scala gives us comparison methods and we don’t have to resort to ugly this.compareTo(that) > 0 kludges.

Anyway, let’s define a simple Value case class that holds integers:

Because Value extends Ordered we can use methods that expect a natural ordering of objects - look at this interpreter session:

By contrast, we can’t sort on classes not defining the Ordered trait:

## Ordering/Comparator

Java/Scala also defines another kind of abstraction which is used to compare two values. In java this interface is called Comparator and in scala it’s Ordering:

Ordering can be thought as a more general interface then Ordered - you can have many Orderings available for a class, which for Ordered isn’t possible without subtyping.

# Generic sorting

Let’s create a generic container:

We can sort on it using this sort class:

For Sort to work, we have to define an Ordering on Boxes:

Now we can define a trivial box type:

And we can sort sequences of IntBox using:

This isn’t good as we can make it more general, but now let’s talk implicits.

# Implicits 101

## Implicit parameters

An implicit parameter T of a method, can be omitted when the argument can be deduced by the compiler - when an implicit instance of the type T is in scope.

Trivial example for Ints:

## Implicit definitions

Another type of implicits are implicit definitions which are used to create conversions between objects of type A to B. If we have a method that expects a parameter of type B we can give it an instance of A if there exists a implicit method in scope:

Concretely, lets go back and modify the IntBox class giving it a + method:

If we wanted + to work on ints we could extend the functionality by defining an implicit conversion between Int and IntBox

Now both versions will work:

# Sorting on Ordered

Coming back to our Box example - the scala library defines an implicit conversion between Ordered[T] and Ordering[T] and vice-versa. We can use this to define a universal sorting function on Boxes:

And now, sorting works as expected:

# Type classes

I’ve written a little post about typeclasses (Ordering is in fact a type class) you can check it out here

# Edit history

## 2013-03-28

• Fixed typos/spelling errors.
• Added link to “Polymorhpism, and type classes in Scala.”

## 2016-03-15

• Fixed the code snippet in the Ordering/Comparator section - thanks to Marcus Bosten for pointing that out