Is Comparator a type class?

Question

I've been reading up on type classes in Scala and thought I had a good grasp on it, until I remembered Java's java.util.Comparator.

If I understand properly, Ordering is the prototypical example of a type class. The only difference I can think of between a Comparator and an instance of Ordering is that comparators are necessarily explicit, while orderings can be, and often are, implicit.

Is Comparator a type class? I get the (mistaken?) impression that Java does not actually have type classes. Does this mean that a type class needs to be able to be implicit? I considered implicit conversions of type classes to be mostly syntactic sugar - awesome as it is, it's "simply" giving the compiler enough hint - was I missing something?

---

The following code example shows how Comparator adds an ordering operation to a type that didn't have it, without having to modify said type.

// Comparator used to retroactively fit the MyExample class with an ordering operation.
public static class MyExampleComparator implements Comparator<MyExample> {
    public static final Comparator<MyExample> SINGLETON = new MyExampleComparator();

    private MyExampleComparator() {}

    public int compare(MyExample a, MyExample b) {
        return a.value - b.value;
    }
}

// Custom type, its only purpose is to show that Comparator can add an ordering operation to it when it doesn't
// have one to begin with.
public static class MyExample {
    private final int value;

    public MyExample(int v) {
        value = v;
    }

    public String toString() {
        return Integer.toString(value);
    }
}

public static void main(String... args) {
    List<MyExample> list = new ArrayList<MyExample>();

    for(int i = 0; i < 10; i++)
        list.add(new MyExample(-i));

    // Sorts the list without having had to modify MyExample to implement an interface.
    Collections.sort(list, MyExampleComparator.SINGLETON);

    // Prints the expected [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0]
    System.out.println(list);
}

Answer 1

I prefer not to talk specifically about type classes but about the type class pattern in Scala; the reason is that when you start asking "what is the type class", you end up concluding that it is just an interface used in a particular way.

(In Haskell it makes more sense to call a specific construct a type class.)

The type class pattern consists of three essential parts (but there are usually a couple more for convenience). The first is an interface parameterized by a single type that abstracts some sort of capability on the parameterized type. java.util.Comparator is a perfect example: it provides an interface for comparison. Let's just use that.

The second thing you need is a method that makes use of that parameterization, which you can specify with short-hand notation in Scala:

// Short signature
//             v------------------- "We must be able to find a Comparator for A"
def ordered[A: java.util.Comparator](a0: A, a1: A, a2: A) = {
  val cmp = implicitly[java.util.Comparator[A]]   // This is the Comparator
  cmp.compare(a0, a1) <= 0 && cmp.compare(a1, a2) <= 0
}

// Long signature version
def ordered[A](a0: A, a1: A, a2: A)(implicit cmp: java.util.Comparator[A]) = {
  cmp.compare(a0, a1) <= 0 && cmp.compare(a1, a2) <= 0
}

Okay, but where do you get that comparator from? That's the third necessary piece. By default, Scala doesn't give you Comparators for the classes you might like, but you can define your own:

implicit object IntComp extends java.util.Comparator[Int] {
  def compare(a: Int, b: Int) = a.compareTo(b)
}

scala> ordered(1,2,3)
res5: Boolean = true

scala> ordered(1,3,2)
res6: Boolean = false

Now that you've provided the functionality for Int (implicitly), the compiler will fill in the implicit parameter to ordered to make it work. If you haven't yet provided the functionality, it gives an error:

scala> ordered("fish","wish","dish")
<console>:12: error: could not find implicit value
for parameter cmp: java.util.Comparator[String]
          ordered("fish","wish","dish")

until you supply that functionality:

implicit object StringComp extends java.util.Comparator[String] {
  def compare(a: String, b: String) = a.compareTo(b)
}

scala> ordered("fish","wish","dish")
res11: Boolean = false

So, do we call java.util.Comparator a type class? It certainly functions just as well as a Scala trait that handles the equivalent part of the type class pattern. So even though the type class pattern doesn't work as well in Java (since you have to explicitly specify the instance to use instead of having it implicitly looked up), from a Scala perspective java.util.Comparator is as much a type class as anything.