title: Scala SortedMap.map method returns non-sorted map when static type is Map
body: <p>I encountered some unauthorized strangeness working with Scala's SortedMap[A,B].  If I declare the reference to SortedMap[A,B] "a" to be of type Map[A,B], then map operations on "a" will produce a non-sorted map implementation.  </p>
  
  <p>Example:</p>
  
  <pre><code>import scala.collection.immutable._
  
  object Test extends App {
      val a: Map[String, String] = SortedMap[String, String]("a" -&gt; "s", "b" -&gt; "t", "c" -&gt; "u", "d" -&gt; "v", "e" -&gt; "w", "f" -&gt; "x")
      println(a.getClass+": "+a)
  
      val b = a map {x =&gt; x}  // identity
      println(b.getClass+": "+b)
  }
  </code></pre>
  
  <p>The output of the above is: </p>
  
  <blockquote>
    <p>class scala.collection.immutable.TreeMap: Map(a -> s, b -> t, c -> u, d -> v, e -> w, f -> x)<br>
    class scala.collection.immutable.HashMap$HashTrieMap: Map(e -> w, f -> x, a -> s, b -> t, c -> u, d -> v)</p>
  </blockquote>
  
  <p>The order of key/value pairs before and after the identity transformation is not the same.  </p>
  
  <p>The strange thing is that removing the type declaration from "a" makes this issue go away.  That's fine in a toy example, but makes SortedMap[A,B] unusable for passing to methods that expect Map[A,B] parameters.</p>
  
  <p>In general, I would expect higher order functions such as "map" and "filter" to not change the fundamental properties of the collections they are applied to.</p>
  
  <p>Does anyone know why "map" is behaving like this?</p>