How to create a scala SortedMaps pool?

Question

(I use Scala nightlies, and I see the same behavior in 2.8.0b1 RC4. I am new to Scala.)

I have two SortedMap that I would like to form a union. Here is the code I would 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 that the expression “implicit” means that X can be converted to Ordered[X] s, and then it makes sense to combine the SortedMap into another SortedMap , not just the 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 type parameter bounds [A <: scala.math.Ordered[A]] a ++ b ^ one error found 

My problem seems to disappear if this parameter parameter parameter is [A <% scala.math.Ordered[A]] and not [A <: scala.math.Ordered[A]] . Unfortunately, I can’t even figure out where the "ordered" method lives! Can someone help me track it?

Otherwise, what I wanted to do to create a union of two SortedMap s? If I delete the return type of the combine (or change it to Map ), everything works fine, but I cannot rely on sorting the return value!

Answer 1

What you are currently using is a sign of scala.collection.SortedMap , the ++ method inherits from the MapLike sign. Therefore, you see the following behavior:

 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 returned ++ result is Map[Int, Int] , because it will be the only type that makes sense to return the ++ method of the MapLike object. ++ seems to preserve the sorted SortedMap property, which I believe is due to the fact that ++ uses abstract methods to perform concatenation, and these abstract methods are defined as preserving the order of the map.

To have a union of two sorted cards, 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 declares a ++ method that returns a SortedMap .

Now a few answers to your questions about type boundaries:

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

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

Edit: Regarding your comment. If you use scala.collection.immutable.SortedMap , you are still programming the interface not for implementation, since the immutable SortedMap is defined as trait . You can think of it as a more specialized feature of scala.collection.SortedMap , which provides additional operations (like ++ , which returns SortedMap ), and the property is immutable. This is in line with Scala's philosophy of preferring immutability - so I don't see a problem using immutable SortedMap . In this case, you can guarantee that the result will definitely be sorted, and this cannot be changed since the collection is immutable.

Although it still seems strange to me that scala.collection.SortedMap does not provide a ++ method that returns a SortedMap . All the limited testing I did seems to suggest that the result of concatenating two scala.collection.SortedMap really creates a map that saves the sorted property.

Answer 2

You have chosen a tough nut to crack as a beginner before Scala! :-)

Well, a short tour, don't expect to fully understand this now. First, note that the problem occurs with the ++ method. Searching for its definition, we find it based on MapLike , getting either Iterator or Traversable . Since y is a SortedMap , the version of Traversable .

Pay attention to your extensive type signature that is passed to CanBuildFrom . This is passed implicitly, so you usually don't need to worry about it. However, to understand what is happening, this time you do.

You can find CanBuildFrom by clicking on it where it appears in the ++ definition, or by filtering. As Randall mentioned in the comments, there is an unmarked blank box in the upper left corner of the skydock page. You just need to click there and enter, and it will return matches for what you typed.

So, find the CanBuildFrom on the ScalaDoc and select it. It has a large number of subclasses, each of which is responsible for creating a certain type of collection. Locate and click on the subclass of SortedMapCanBuildFrom . This is the class of the object that you want to create the SortedMap from Traversable . Notice the instance constructor (constructor for the class) that receives the 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” name) contains the implicit that Ordering s will generate, since companion objects will be examined for implications that generate instances or transformations for this class. It is defined inside the LowPriorityOrderingImplicits attribute, the Ordering object expands, and looking at it, you will see the ordered[A <: Ordered[A]] method that will generate the required Ordering ... or create it, unless there was a problem.

It can be assumed that an implicit conversion from X to Ordered[X] would be sufficient, as before, before exploring this more thoroughly. This, however, is a conversion of objects, and ordered expects to get a type that is a subtype of Ordered[X] . Although you can convert an object of type X to an object of type Ordered[X] , X , by itself, is not a subtype of Ordered[X] , so it cannot be passed as an argument to ordered .

Alternatively, you can create an implicit val Ordering[X] instead of def Ordered[X] and you will run into a problem. In particular:

 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 that most people who start a reaction to ordered / Ordering should be perplexed: why are classes for the same thing? The first applies to java.lang.Comparable , and the second to java.util.Comparator . Alas, the type signature for compare pretty much sums up the main difference:

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

Using Ordered[A] requires either A extend Ordered[A] , which requires it to modify the definition of A or to pass a method that can convert A to Ordered[A] . Scala is very good at making the latter easy, but then you need to convert each instance before comparing.

On the other hand, using Ordering[A] requires the creation of a single object, such as the one shown above. When you use it, you simply pass two objects of type A - compare - no objects are created in the process.

Thus, there are some performance benefits, but there is a much more important reason for Scala to prefer Ordering over ordered . Look again at the companion object on Ordering . You will notice that for many of the Scala classes defined in it, there are several implications. You may recall that you mentioned earlier that an implicit class T will be searched for an object T , and what exactly is happening.

This can be done for ordered . However, this is the anchor point, this means that every method that supports both Ordering and ordered will not work! This is because Scala will look for implicit to make it work, and will find two: one for Ordering , one for ordered . Unable to decide what you need, Scala refuses an error message. Thus, a choice had to be made, and Ordering had more opportunities for this.

Du, I forgot to explain why the signature is not defined as ordered[A <% Ordered[A]] , but not ordered[A <: Ordered[A]] . I suspect this will lead to a double implicit failure, which I mentioned earlier, but I will ask the guy who really did this and had double implicit problems whether this particular method is problematic.