Scala The SortedMap.map method returns an unsorted map if the static type is Map.

Question

I came across some unauthorized weirdness working with Scala SortedMap [A, B]. If I declare a link to SortedMap [A, B] "a" of type Map [A, B], then operations with the map on "a" will lead to the implementation of an unsorted map.

Example:

import scala.collection.immutable._ object Test extends App { val a: Map[String, String] = SortedMap[String, String]("a" -> "s", "b" -> "t", "c" -> "u", "d" -> "v", "e" -> "w", "f" -> "x") println(a.getClass+": "+a) val b = a map {x => x} // identity println(b.getClass+": "+b) } 

The conclusion above:

class scala.collection.immutable.TreeMap: Map (a → s, b → t, c → u, d → v, e → w, f → x)
class scala.collection.immutable.HashMap $ HashTrieMap: Map (e → w, f → x, a → s, b → t, c → u, d → v)

The order of the key / value pairs before and after the identity conversion does not match.

The strange thing is that removing the type declaration from "a" makes this problem go away. This is fine in the toy example, but makes SortedMap [A, B] unsuitable for passing to methods that expect the parameters of the map [A, B].

In general, I would expect higher-order functions, such as "map" and "filter", to not change the fundamental properties of the sets to which they apply.

Does anyone know why a “card” behaves like this?

Answer 1

The map method, like most collection methods, is not specifically defined for SortedMap . It is defined in a higher level class ( TraversableLike ) and uses the "builder" to convert the result to the correct return type.

So, how does it determine what the “correct” return type is? Well, he is trying to return you a return type that started as. When you tell Scala that you have a Map[String,String] and ask for its map , then the builder should figure out how to "build" the return type. Since you told Scala that the input was Map[String,String] , the builder decides to build Map[String,String] for you. The builder does not know that you need a SortedMap , so it does not give you one.

The reason it works when you leave an annotation of type Map[String,String] is because Scala indicates that type a is equal to SortedMap[String,String] . That way, when you call map , you call it on SortedMap , and the builder knows how to build a SortedMap to return.

As far as you argue that methods should not alter "fundamental properties", I think you are looking at it from the wrong angle. These methods will always return you an object corresponding to the specified type. This is a type that defines the behavior of the builder, not the base implementation. When you think about it, this is the type that forms the contract for how the methods should behave.

Why do we need this?

Why is this the preferred behavior? Consider a specific example. Say we have SortedMap[Int,String]

 val sortedMap = SortedMap[Int, String](1 -> "s", 2 -> "t", 3 -> "u", 4 -> "v") 

If I were to map over it with a function that modifies the keys, I risk losing elements when their keys collide:

 scala> sortedMap.map { case (k, v) => (k / 2, v) } res3: SortedMap[Int,String] = Map(0 -> s, 1 -> u, 2 -> v) 

But hey, that's fine. This is a map after all, and I know this is a map , so I should expect this behavior.

Now let's say that we have a function that accepts Iterable pairs:

 def f(iterable: Iterable[(Int, String)]) = iterable.map { case (k, v) => (k / 2, v) } 

Since this function has nothing to do with map s, it would be very surprising if the result of this function had fewer elements than the input. In the end, the map on Iterable should display the displayed version of each element. But a map is Iterable pairs, so we can pass it to this function. So what happens in Scala when we do?

 scala> f(sortedMap) res4: Iterable[(Int, String)] = List((0,s), (1,t), (1,u), (2,v)) 

Look at this! No items are lost! In other words, Scala will not surprise us by violating our expectations about how a map on Iterable should work. If instead the builder tried to create a SortedMap based on the fact that the input was a SortedMap , then our function f would have unexpected results, and that would be bad.

So, the moral of this story: use types to talk about the structure of collections, how to handle your data. If you want your code to expect the map to be sorted, you must enter it as SortedMap .

Answer 2

Signature map :

def map[B, That](f: ((A, B)) ⇒ B)(implicit bf: CanBuildFrom[Map[A, B], B, That]): That

The implicit parameter bf used to build the resulting collection. Therefore, in your example, since type a is Map[String, String] , type bf :

val cbf = implicitly[CanBuildFrom[Map[String, String], (String, String), Map[String, String]]]

Which only builds a Map[String, String] , which does not have any SortedMap properties. Cm:

cbf() ++= List("b" -> "c", "e" -> "g", "a" -> "b") result

For more information, see this wonderful article: http://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html

Answer 3

As dyross points out, this is a Builder that is selected (via CanBuildFrom) based on the target type, which defines the collection class that you get from the map operation. Now this may not be the behavior you wanted, but it, for example, allows you to select the target type:

 val b: SortedMap[String, String] = a.map(x => x)(collection.breakOut) 

( breakOut gives a generic CanBuildFrom whose type is determined by context, i.e., an annotation of our type.)

Thus, you can add some type parameters that allow you to accept any kind of map or trace (see this question ), which will allow you to perform a map operation in your method, while maintaining the correct type information, but as you can see, it doesn’t simply.

I think a much simpler approach is to define the functions that you apply to your collections using the map , flatMap , etc. collection methods, and not by sending the collection itself to the method.

i.e. instead

 def f[Complex type parameters](xs: ...)(complex implicits) = ... val result = f(xs) 

do

 val f: X => Y = ... val results = xs map f 

Answer 4

In short: you explicitly declared that a is of type Map , and the Scala framework tries very hard for higher-order functions, such as Map and filter , so as not to change the fundamental properties to which they apply, therefore it will also return a Map , since it is you obviously told you what you want.