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!

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.