SortedSet map does not always preserve element ordering in result?

Question

Given the following Scala 2.9.2 code:

Updated with non-working example

import collection.immutable.SortedSet

case class Bar(s: String)

trait Foo {
  val stuff: SortedSet[String]
  def makeBars(bs: Map[String, String])
    = stuff.map(k => Bar(bs.getOrElse(k, "-"))).toList
}

case class Bazz(rawStuff: List[String]) extends Foo {
  val stuff = SortedSet(rawStuff: _*)
}


// test it out....
val b = Bazz(List("A","B","C"))
b.makeBars(Map("A"->"1","B"->"2","C"->"3"))
// List[Bar] = List(Bar(1), Bar(2), Bar(3))
// Looks good?

// Make a really big list not in order. This is why we pass it to a SortedSet...    
val data =  Stream.continually(util.Random.shuffle(List("A","B","C","D","E","F"))).take(100).toList
val b2 = Bazz(data.flatten)

// And how about a sparse map...?
val bs = util.Random.shuffle(Map("A" -> "1", "B" -> "2", "E" -> "5").toList).toMap
b2.makeBars(bs)
// res24: List[Bar] = List(Bar(1), Bar(2), Bar(-), Bar(5))

I've discovered that, in some cases, the makeBars method of classes extending Foo does not return a sorted List. In fact, the list ordering does not reflect the ordering of the SortedSet

What am I missing about the above code where Scala will not always map a SortedSet to a List with elements ordered by the SortedSet ordering?

Answer 1

You're being surprised by implicit resolution.

The map method requires a CanBuildFrom instance that's compatible with the target collection type (in simple cases, identical to the source collection type) and the mapper function's return type.

In the particular case of SortedSet, its implicit CanBuildFrom requires that an Ordering[A] (where A is the return type of the mapper function) be available. When your map function returns something that the compiler already knows how to find an Ordering for, you're good:

scala> val ss = collection.immutable.SortedSet(10,9,8,7,6,5,4,3,2,1)
ss: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 3, 4, 5, 
                                                        6, 7, 8, 9, 10)

scala> val result1 = ss.map(_ * 2)
result1: scala.collection.immutable.SortedSet[Int] = TreeSet(2, 4, 6, 8, 10, 
                                                            12, 14, 16, 18, 20) 
                 // still sorted because Ordering[Int] is readily available

scala> val result2 = ss.map(_ + " is a number")
result2: scala.collection.immutable.SortedSet[String] = TreeSet(1 is a number, 
                                                                10 is a number, 
                                                                2 is a number, 
                                                                3 is a number, 
                                                                4 is a number, 
                                                                5 is a number, 
                                                                6 is a number, 
                                                                7 is a number, 
                                                                8 is a number, 
                                                                9 is a number) 
// The default Ordering[String] is an "asciibetical" sort, 
// so 10 comes between 1 and 2. :)

However, when your mapper function turns out to return a type for which no Ordering is known, the implicit on SortedSet doesn't match (specifically, no value can be found for its implicit parameter), so the compiler looks "upward" for a compatible CanBuildFrom and finds the generic one from Set.

scala> case class Foo(i: Int)
defined class Foo

scala> val result3 = ss.map(Foo(_))
result3: scala.collection.immutable.Set[Foo] = Set(Foo(10), Foo(4), Foo(6), Foo(7), Foo(1), Foo(3), Foo(5), Foo(8), Foo(9), Foo(2))

// The default Set is a hash set, therefore ordering is not preserved

Of course, you can get around this by simply supplying an instance of Ordering[Foo] that does whatever you expect:

scala> implicit val fooIsOrdered: Ordering[Foo] = Ordering.by(_.i)
fooIsOrdered: Ordering[Foo] = scala.math.Ordering$$anon$9@7512dbf2

scala> val result4 = ss.map(Foo(_))
result4: scala.collection.immutable.SortedSet[Foo] = TreeSet(Foo(1), Foo(2), 
                                                       Foo(3), Foo(4), Foo(5), 
                                                       Foo(6), Foo(7), Foo(8), 
                                                       Foo(9), Foo(10))
  // And we're back!

Finally, note that toy examples often don't exhibit the problem, because the Scala collection library has special implementations for small (n <= 6) Sets and Maps.