Friday, May 28, 2010

My Misperception of Scala's Ordered Trait

A brief tale of a little misperception that I had, and how it was corrected.

The Ordered trait in Scala is typically used when defining a class of objects that know how to order themselves by comparing against other instances of that class. The typical class definition looks something like this:

case class Thing(val n:Int) extends Ordered[Thing] {
    def compare(that: Thing): Int = { this.n - that.n }  //[1]
}
When I first started looking at these definitions, they just looked wrong to me: it seemed like Ordered[Thing] depended on the definition of Thing, and Thing in turn was defined in terms of Ordered[Thing]; a circular definition!

It is of course not a circular definition. The appropriate interpretation was made obvious to me recently while reviewing some Scala code with a co-worker, who was using the Ordered trait in a non-canonical way. Instead of the usual use of Ordered as in the above class definition, his class definition looked similar to this:
case class Thing(val n:Int) extends Ordered[Any] {
    def compare(that: Any): Int = that match {
        case i:Int => this.n - i
        case x:Thing => this.n - x.n
        case _ => throw new IllegalArgumentException("bad type")
    }
}
The reason he did this was because he wanted to be able to compare a Thing - which has an Int value as part of its definition - against either a Thing or an Int. The smallest common superclass of Thing and Int is Any, so his compare method had to accept an argument of type Any, which in turn meant the Ordered trait must be Ordered[Any].

This somewhat unusual use of Ordered led us to another small problem. He had an Array[Thing], sorted according to Thing.compare, on which he wanted to do a binary search. We couldn't find a binary search built in to Scala, but it was simple enough to find one on the web. We grabbed the Scala implementation of binary search from RosettaCode.org (and changed the type of the argument from IndexedSeq[A] to Array[A] since we were using Scala 2.7):
def binarySearch[A <% Ordered[A]](a: Array[A], v: A) = {
  def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
    case _ if high < low => None
    case mid if a(mid) > v => recurse(low, mid - 1)
    case mid if a(mid) < v => recurse(mid + 1, high)
    case mid => Some(mid)
  }
  recurse(0, a.size - 1)
}
Our code to call the binarySearch method looked something like this:
val a:Array[Thing] = Array(Thing(1), Thing(3), Thing(5), Thing(6))
val x = binarySearch(a,3)
It failed to compile, with an error like this REPL output:
<console>:7: error: type mismatch;
 found   : Array[Thing]
 required: Array[Any]
       val x = binarySearch(a,3)
                            ^
<console>:7: error: no implicit argument matching parameter type (Any) => Ordered[Any] was found.
       val x = binarySearch(a,3)
               ^
The cause of this pair of error messages may be obvious to some people, but we scratched our heads a while trying to figure out what we had done wrong. Eventually we realized that the binarySearch method was making the assumption that the element type of the array was same as the type of the sort; in other words, the binarySearch method only worked on arrays of elements where each element, of type A, implemented Ordered[A]. Since our Thing class did not do that, we were getting a type mismatch when trying to pass it to binarySearch.

The solution was to modify binarySearch to explicitly have two type parameters, one for the element type of the array (A) and one for the ordering type of those elements (B), i.e. the type of the values against which we can compare the array elements:
def binarySearch[A,B](a: Array[A with Ordered[B]], v: B) = {
  def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
    case _ if high < low => None
    case mid if a(mid) > v => recurse(low, mid - 1)
    case mid if a(mid) < v => recurse(mid + 1, high)
    case mid => Some(mid)
  }
  recurse(0, a.size - 1)
}
Going through this exercise helped me clearly see the distinction between the element type and the ordering type, and more generally to firmly excise the mistaken perception of circular dependency I mentioned at the start of this post. Now when I see class Foo extends Bar[Foo], it's easy for me to remember that just means that class Foo implements methods, as declared in Bar, that happen to take arguments of type Foo [2].

Footnotes

[1] Using a straight subtraction like this for the comparison will fail in extreme cases, such as if the first value is MAX_VALUE and the second value is negative; however, in the interest of keeping the code example simple, I have used this very short and understandable code snippet.

[2] Yes, I know this is not a very precise statement: Bar[Foo] might only define variables rather than methods, or the methods might take arguments of type List[Foo] rather than Foo, or any of a number of other variations.

Updated 2010-07-10 to escape angle brackets as pointed out by tolund.

6 comments:

Johannes said...

A <% Ordered means even a different thing, than you described.

The original signature

def binarySearch[A <% Ordered[A]](a: IndexedSeq[A], v: A)

is short for

def binarySearch[A](a: IndexedSeq[A], v: A)(implicit evidence: A => Ordered[A])

and this means that you can pass into binarySearch any sequence of elements, as long as there is an implicit value in scope which converts any value of type A into an Ordered[A]. This provides a much greater flexibility how and where to implement the order of elements of a type than the simple way you showed by implementing Ordered directly by its elements.

So you could provide a order for our elements by defining

implicit val orderedThing: Thing => Ordered[Thing] = x => new Ordered { /* implementation as before */ }

somewhere outside of Thing.

Of course, it should work as well in the case where Thing just extends Ordered[Thing]. And indeed it does, because of the implicit identity being always defined.

The problems which occurred in your code (or your co-worker's) had another problem: Ordered[A] is invariant in A. This means an Ordered[Thing] is not an Ordered[Any] and vice versa. And furthermore, differently to Java, where an array of Strings, String[], actually is an array of Objects, Object[], this is not the case in Scala.

And that's the cause of the error message. In

binarySearch(a,3)

Scala infers type Any for A. But 'a' is no Array[Any] and there is no ordering available which can compare any values of type Any.

The root cause of your problems here is that you are working around the type-system - and that's the misconception: you are using Ordered[X] as a mechanism for complete polymorphic comparison. But by extending Ordered[X] you are, in fact, signing a contract: My class can compare to all values of type X. But: Scala makes it easy to break such contracts by casting (hidden in match/case) and by throwing exceptions. In your example you have no static type safety any more, because things like that compile, too:

binarySearch(a, "test") // throws a runtime exception

There are two more type-aware solutions:

1. Use your first version and when searching always create an example object for which you know how to compare. I.e. always use 'binarySearch(a, Thing(4)' instead of 'binarySearch(a, 4)'.

2. Use implicits to your advantage.

Here's a version which tries to respect types:

def binarySearch[B, A <% Ordered[B]](a: Array[A], v: B) = {
def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
case _ if high < low => None
case mid if a(mid) > v => recurse(low, mid - 1)
case mid if a(mid) < v => recurse(mid + 1, high)
case mid => Some(mid)
}
recurse(0, a.size - 1)
}

case class Thing(val n:Int)

implicit val compThingToThing: Thing => Ordered[Thing] =
t => new Ordered[Thing] {
def compare(that: Thing): Int = { t.n - that.n }
}

implicit val compThingToInt: Thing => Ordered[Int] =
t => new Ordered[Int] {
def compare(that: Int): Int = { t.n - that }
}


val a:Array[Thing] = Array(Thing(1), Thing(3), Thing(5), Thing(6))

binarySearch(a, Thing(5)) // compiles, compThingToThing is available
binarySearch(a, 5) // compiles, compThingToInt is available
binarySearch(a, "test") // doesn't compile, it isn't known how to compare Things to strings

The implicit values are here evidence (and implementation) of the fact that we can compare Things to other things of a specific type. Using this design, you can add other comparators later by type without having to fall back to casting and throwing exceptions and don't lose type-safety either.

James Iry said...

Have fun with this one: http://lambda-the-ultimate.org/node/3942#comment-59763

Unknown said...

Hmm. It seems like what you want is: case class Thing(val n: Int) extends Ordered[Thing] with Ordered[Int] {...} instead of using Ordered[Any]

I'm not sure why that doesn't work, actually. In that way, Ordered is different from Java's Comparable.

Anonymous said...
This comment has been removed by a blog administrator.
Jim McBeath said...

gambistics: Thanks, your comment raises a lot of good points.

Agreed, our implementation is not as general as it could be. As it happens, the application was an experiment to see if we could implement a Scala version of an application that deals with arrays that can run as quickly as a reference Java version. We had been having problems with too many objects being created by implicit conversions, so we were avoiding using them inside loops and with arrays.

Regarding working around the type system: again, this is an attempt to improve performance. It would be nice if there were a more efficient way to represent that we can accept one of two disjoint types, and only those types. Perhaps after the compiler gets more optimizations.

James: Thanks for the link, I like that example. I found the accompanying comments to be interesting as well.

Chris: You can't do this because type erasure makes both Ordered traits look the same. I am still hoping that Kevin Wright's dynamic mixins will allow this.

Unknown said...

"Chris: You can't do this because type erasure makes both Ordered traits look the same...."

You're right. I had thought that this would work in Java with Comparable, but it has the same limitation of course (and for the same reason). It's a pity because the methods being implemented are not ambiguous.