Why do mutable and immutable ListMaps have different orders in Scala?

Question

Why does the immutable version of the ListMap store in ascending order, while mutable version stores in descending order?

Here is a test that you can use if you got scalatest-1.6.1.jar and junit-4.9.jar

  @Test def StackoverflowQuestion()
  {
    val map = Map("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18)
    val sortedIMMUTABLEMap = collection.immutable.ListMap[String, Int](map.toList.sortBy[Int](_._2): _*)
    println("head : " + sortedIMMUTABLEMap.head._2)
    println("last : " + sortedIMMUTABLEMap.last._2)
    sortedIMMUTABLEMap.foreach(X => println(X))
    assert(sortedIMMUTABLEMap.head._2 < sortedIMMUTABLEMap.last._2)

    val sortedMUTABLEMap = collection.mutable.ListMap[String, Int](map.toList.sortBy[Int](_._2): _*)
    println("head : " + sortedMUTABLEMap.head._2)
    println("last : " + sortedMUTABLEMap.last._2)
    sortedMUTABLEMap.foreach(X => println(X))
    assert(sortedMUTABLEMap.head._2 > sortedMUTABLEMap.last._2)
  }

Heres the output of the PASSING test :

head : 2
last : 18
(C,2)
(A,5)
(D,9)
(B,12)
(E,18)
head : 18
last : 2
(E,18)
(B,12)
(D,9)
(A,5)
(C,2)

Answer 1

The symptoms can be simplified to:

scala> collection.mutable.ListMap(1 -> "one", 2 -> "two").foreach(println)
(2,two)
(1,one)

scala> collection.immutable.ListMap(1 -> "one", 2 -> "two").foreach(println)
(1,one)
(2,two)

The "sorting" in your code is not the core of the issue, your call to ListMap is using the ListMap.apply call from the companion object that constructs a list map backed by a mutable or immutable list. The rule is that the insertion order will be preserved.

The difference seems to be that mutable list is backed by an immutable list and insert happens at the front. So that's why when iterating you get LIFO behavior. I'm still looking at the immutable one but I bet the inserts are effectively at the back. Edit, I'm changing my mind: insert are probably at the front, but it seems the immutable.ListMap.iterator method decides to reverse the result with a toList.reverseIterator on the returned iterator. I think it worth bringing it in the mailing list.

Could the documentation be better? Certainly. Is there pain? Not really, I don't let it happen. If the documentation is incomplete, it's wise to test the behavior or go look up at the source before picking a structure versus another one.

Actually, there can be pain if the Scala team decides to change behavior at a later time and feel they can because the behavior is effectively undocumented and there is no contract.

---

To address your use case explained in the the comment, say you've collected the string frequency count in a map (mutable or immutable):

val map = Map("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18, "B" -> 5)

Since you only need to sort once at the end, you can convert the tuples from the map to a seq and then sort:

map.toSeq.sortBy(_._2)
// Seq[(java.lang.String, Int)] = ArrayBuffer((C,2), (A,5), (B,5), (D,9), (E,18))

Answer 2

As I see it neither ListMap claims to be a sorted map, just a map implemented with a List. In fact I don't see anything in their contract that says anything about preserving the insertion order.

Programming in Scala explains that ListMap may be of use if the early elements are more likely to be accessed, but that otherwise it has little advantage over Map.