How do I form the union of scala SortedMaps?

Question

(I'm using Scala nightlies, and see the same behaviour in 2.8.0b1 RC4. I'm a Scala newcomer.)

I have two SortedMaps that I'd like to form the union of. Here's the code I'd like to use:

import scala.collection._

object ViewBoundExample {
    class X
    def combine[Y](a: SortedMap[X, Y], b: SortedMap[X, Y]): SortedMap[X, Y] = {
        a ++ b
    }
    implicit def orderedX(x: X): Ordered[X] = new Ordered[X] { def compare(that: X) = 0 }
}

The idea here is the 'implicit' statement means Xs can be converted to Ordered[X]s, and then it makes sense combine SortedMaps into another SortedMap, rather than just a map.

When I compile, I get

sieversii:scala-2.8.0.Beta1-RC4 scott$ bin/scalac -versionScala compiler version
2.8.0.Beta1-RC4 -- Copyright 2002-2010, LAMP/EPFL

sieversii:scala-2.8.0.Beta1-RC4 scott$ bin/scalac ViewBoundExample.scala
ViewBoundExample.scala:8: error: type arguments [ViewBoundExample.X] do not
    conform to method ordered's type parameter bounds [A <: scala.math.Ordered[A]]
        a ++ b
          ^
one error found

It seems my problem would go away if that type parameter bound was [A <% scala.math.Ordered[A]], rather than [A <: scala.math.Ordered[A]]. Unfortunately, I can't even work out where the method 'ordered' lives! Can anyone help me track it down?

Failing that, what am I meant to do to produce the union of two SortedMaps? If I remove the return type of combine (or change it to Map) everything works fine --- but then I can't rely on the return being sorted!

Denys

Was combine supposed to be a method of X? – Kyongkyoto

No -- this code was just a minimal version of something I was working on when I ran into this problem. In the original, X is some type from another (java) library. Combine was a private utility method in a new (scala) class I was working on; it's not intended to look like plausible code, just reproduce the compiler output! – Denys

Answer 1

Currently, what you are using is the scala.collection.SortedMap trait, whose ++ method is inherited from the MapLike trait. Therefore, you see the following behaviour:

scala> import scala.collection.SortedMap
import scala.collection.SortedMap

scala> val a = SortedMap(1->2, 3->4)
a: scala.collection.SortedMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> val b = SortedMap(2->3, 4->5)
b: scala.collection.SortedMap[Int,Int] = Map(2 -> 3, 4 -> 5)

scala> a ++ b
res0: scala.collection.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

scala> b ++ a
res1: scala.collection.Map[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

The type of the return result of ++ is a Map[Int, Int], because this would be the only type it makes sense the ++ method of a MapLike object to return. It seems that ++ keeps the sorted property of the SortedMap, which I guess it is because ++ uses abstract methods to do the concatenation, and those abstract methods are defined as to keep the order of the map.

To have the union of two sorted maps, I suggest you use scala.collection.immutable.SortedMap.

scala> import scala.collection.immutable.SortedMap
import scala.collection.immutable.SortedMap

scala> val a = SortedMap(1->2, 3->4)
a: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 3 -> 4)

scala> val b = SortedMap(2->3, 4->5)
b: scala.collection.immutable.SortedMap[Int,Int] = Map(2 -> 3, 4 -> 5)

scala> a ++ b
res2: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

scala> b ++ a
res3: scala.collection.immutable.SortedMap[Int,Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)

This implementation of the SortedMap trait declares a ++ method which returns a SortedMap.

Now a couple of answers to your questions about the type bounds:

• Ordered[T] is a trait which if mixed in a class it specifies that that class can be compared using <, >, =, >=, <=. You just have to define the abstract method compare(that: T) which returns -1 for this < that, 1 for this > that and 0 for this == that. Then all other methods are implemented in the trait based on the result of compare.

• T <% U represents a view bound in Scala. This means that type T is either a subtype of U or it can be implicitly converted to U by an implicit conversion in scope. The code works if you put <% but not with <: as X is not a subtype of Ordered[X] but can be implicitly converted to Ordered[X] using the OrderedX implicit conversion.

Edit: Regarding your comment. If you are using the scala.collection.immutable.SortedMap, you are still programming to an interface not to an implementation, as the immutable SortedMap is defined as a trait. You can view it as a more specialised trait of scala.collection.SortedMap, which provides additional operations (like the ++ which returns a SortedMap) and the property of being immutable. This is in line with the Scala philosophy - prefer immutability - therefore I don't see any problem of using the immutable SortedMap. In this case you can guarantee the fact that the result will definitely be sorted, and this can't be changed as the collection is immutable.

Though, I still find it strange that the scala.collection.SortedMap does not provide a ++ method witch returns a SortedMap as a result. All the limited testing I have done seem to suggest that the result of a concatenation of two scala.collection.SortedMaps indeed produces a map which keeps the sorted property.

Recourse

My Java experience makes my feel dirty using this solution, but I'm unsure if it's appropriate to carry the prejudice across. I'd never write "ArrayList<X> list = new ArrayList<X>();", because there's no point exposing the particular implementation of "list". Should I feel this way about reaching into the "scala.collection.immutables._" package? I'd sort of hoped that I'd never have to do this for the types of my variables, only when creating instances. – Denys

I have edited the answer to provide a small discussion about your comment. It is a valid concern, but I won't worry much. You are not exposing implementation, you are just requiring more properties for the passed arguments. – Recourse

Scott, you might be interested in #1722637 to understand better the design of Scala's collections. I rarely use anything other than Traversable myself, but sometimes the algorithm calls for something giving specific performance guarantees. And, yet, even a List isn't really what it appears to be -- many times it is actually a "view" over a ListBuffer. – Kyongkyoto

Answer 2

Have you picked a tough nut to crack as a beginner to Scala! :-)

Ok, brief tour, don't expect to fully understand it right now. First, note that the problem happens at the method ++. Searching for its definition, we find it at the trait MapLike, receiving either an Iterator or a Traversable. Since y is a SortedMap, then it is the Traversable version being used.

Note in its extensive type signature that there is a CanBuildFrom being passed. It is being passed implicitly, so you don't normally need to worry about it. However, to understand what is going on, this time you do.

You can locate CanBuildFrom by either clicking on it where it appears in the definition of ++, or by filtering. As mentioned by Randall on the comments, there's an unmarked blank field on the upper left of the scaladoc page. You just have to click there and type, and it will return matches for whatever it is you typed.

So, look up the trait CanBuildFrom on ScalaDoc and select it. It has a large number of subclasses, each one responsible for building a specific type of collection. Search for and click on the subclass SortedMapCanBuildFrom. This is the class of the object you need to produce a SortedMap from a Traversable. Note on the instance constructor (the constructor for the class) that it receives an implicit Ordering parameter. Now we are getting closer.

This time, use the filter filter to search for Ordering. Its companion object (click on the small "o" the name) hosts an implicit that will generate Orderings, as companion objects are examined for implicits generating instances or conversions for that class. It is defined inside the trait LowPriorityOrderingImplicits, which object Ordering extends, and looking at it you'll see the method ordered[A <: Ordered[A]], which will produce the Ordering required... or would produce it, if only there wasn't a problem.

One might assume the implicit conversion from X to Ordered[X] would be enough, just as I had before looking more carefully into this. That, however, is a conversion of objects, and ordered expects to receive a type which is a subtype of Ordered[X]. While one can convert an object of type X to an object of type Ordered[X], X, itself, is not a subtype of Ordered[X], so it can't be passed as a parameter to ordered.

On the other hand, you can create an implicit val Ordering[X], instead of the def Ordered[X], and you'll get around the problem. Specifically:

object ViewBoundExample {
    class X
    def combine[Y](a: SortedMap[X, Y], b: SortedMap[X, Y]): SortedMap[X, Y] = {
        a ++ b
    }
    implicit val orderingX = new Ordering[X] { def compare(x: X, y: X) = 0 }
}

I think most people initial reaction to Ordered/Ordering must be one of perplexity: why have classes for the same thing? The former extends java.lang.Comparable, whereas the latter extends java.util.Comparator. Alas, the type signature for compare pretty much sums the main difference:

def compare(that: A): Int     // Ordered
def compare(x: T, y: T): Int  // Ordering

The use of an Ordered[A] requires for either A to extend Ordered[A], which would require one to be able to modify A's definition, or to pass along a method which can convert an A into an Ordered[A]. Scala is perfectly capable of doing the latter easily, but then you have to convert each instance before comparing.

On the other hand, the use of Ordering[A] requires the creation of a single object, such as demonstrated above. When you use it, you just pass two objects of type A to compare -- no objects get created in the process.

So there are some performance gains to be had, but there is a much more important reason for Scala's preference for Ordering over Ordered. Look again on the companion object to Ordering. You'll note that there are several implicits for many of Scala classes defined in there. You may recall I mentioned earlier that an implicit for class T will be searched for inside the companion object of T, and that's exactly what is going on.

This could be done for Ordered as well. However, and this is the sticking point, that means every method supporting both Ordering and Ordered would fail! That's because Scala would look for an implicit to make it work, and would find two: one for Ordering, one for Ordered. Being unable to decide which is it you wanted, Scala gives up with an error message. So, a choice had to be made, and Ordering had more going on for it.

Duh, I forgot to explain why the signature isn't defined as ordered[A <% Ordered[A]], instead of ordered[A <: Ordered[A]]. I suspect doing so would cause the double implicits failure I have mentioned before, but I'll ask the guy who actually did this stuff and had the double implicit problems whether this particular method is problematic.

Kyongkyoto

Oh... I haven't noticed that you've posted an answer before me. Apparently SO hasn't given me the "new answer" pop up. I'll leave my answer there as well, but +1 for your nice investigation through the API :). – Recourse

Thanks Daniel, this is a great answer -- I wish I could accept both yours and Flaviu's. I accepted his as it's an "easier" answer to achieving my purpose, but I very much appreciate the walk through the API! – Denys

So --- why isn't the signature of LowPriorityOrderingImplicits.ordered defined as ordered[A <% Ordered[A]] instead, i.e. using a view bound? – Denys

@Scott: I don't mind you accepting Flaviu's answer. At any rate, I'll augment my answer with a discussion on the relative merits of Ordered and Ordering. – Kyongkyoto

Since to me it is not obvious, I'll point out that the "filter" Daniel mentions at the beginning of paragraph 6 is the completely uncued white area at the very top of the left-hand pane where packages and their classes (& traits & objects) are listed. Click there and type a case-sensitive RE (treated as unanchored) to filter the package / trait / class / object list. – Summons