TreeSet.map losing its ordering when used as Iterable

[jrudolph]

(Seems like this has to be a well-known issue/puzzler but I couldn't find one with superficial searching)

It seems that TreeSet is not working as expected when it is used as an Iterable.

Welcome to Scala 2.13.1 (OpenJDK 64-Bit Server VM, Java 1.8.0_252).

scala> import scala.collection.immutable.TreeSet
import scala.collection.immutable.TreeSet

// as expected
scala> TreeSet[Long](5,3,2,12,38,2,6,2).map(identity).mkString(", ")
res0: String = 2, 3, 5, 6, 12, 38

// unexpected
scala> (TreeSet[Long](5,3,2,12,38,2,6,2): Iterable[Long]).map(identity).mkString(", ")
res1: String = 5, 6, 38, 2, 12, 3

The underlying assumption is that for all i: Iterable[T] where the implementing collection is sorted this property should be valid:

i.toList == i.map(identity).toList

Without the constraint "where the implementing collection is sorted", it is not expected to be true because Iterable can be implemented for unsorted collections.

Above I used the vague phrase "not working as expected" because the behavior is not explicitly specified (TreeSet does not specify how it implements Iterable which is a common problem of inheritance) and in absence of a specification it should do the least surprising thing.

Was observed here: spray/spray-json#329

[swsnr]

I'd like to point out that i.toList == i.map(identity).toList wouldn't help with the spray-json issue you linked, because the affected code in spray-json maps into another domain (JSON values) so it's not really .map(identity).

For spray json you'd actually need something along the lines of "for all pure functions f: A => B and all i:

i.toList.map(f) == i.map(f).toList

In other words map should preserve the ordering of the source domain A and not order by the ordering of the target domain B.

I'm not sure whether that's better than the current behaviour: In terms of B the collection would still be unordered, just in a different way than it is now.

That said having (TreeSet[Long](5,3,2,12,38,2,6,2): Iterable[Long]).map(f) move to a hashed Set which has no real order at all is somewhat surprising 🙂

[jrudolph]

I'd like to point out that i.toList == i.map(identity).toList wouldn't help with the spray-json issue you linked, because the affected code in spray-json maps into another domain (JSON values) so it's not really .map(identity).

There are two map methods on TreeSet, one that takes an ordering of the codomain to return another TreeSet. Then the one inherited from Iterable. I'm only talking about the one inherited from Iterable.

There's no way to tell the map method inherited from Iterable what the ordering of the codomain should be so it returns a HashSet.

I guess the reason it was done that way was to keep compatibility with the previous CanBuildFrom construction from Scala 2.12 and before. The point of CanBuildFrom was to return "the right thing implicitly" (which was hotly debated).

There are a few reasons that the current behavior might never change:

• There might not be a consensus that the behavior is bad
• Even if there were, it cannot be changed due to binary compatibility constraints that are particularly hard to fix because of the inheritance hierarchy.

The workaround for Sets is to mostly ignore that Sets inherit from Iterable but in particular the domain changing methods like map and rather the use the methods from the iterator it returns. I guess there could be something like a Set.toSafeIterable that returns a plain Iterable on which methods will work without surprises.

def toSafeIterable[T](s: Set[T]): Iterable[T] = new Iterable[T] { def iterator: Iterator[T] = s.iterator }

[SethTisue]

in the same vein: scala/scala-parallel-collections#101 (but the thing lost is parallelism instead of ordering)

[swsnr]

This problem exists on 2.12 and 2.13; we hit the original spray issue with both Scala versions.

The linked parallel collections issue is 2.13 only.

[Jasper-M]

IIUC the only fix for this would be to add overloads of map to Iterable just for this use case. Simplified:

def map[B](f: A => B): Iterable[B]
def map(f: A => A)(implicit d: DummyImplicit): Iterable[A]

Otherwise you can never distinguish between the case where you can keep the ordering and where you can't. If you want to keep getting a TreeSet back even for the A => B case you'd have to add the overload that takes an Ordering to Iterable which would make even less sense.

[julienrf]

The problem comes from the fact that TreeSet has several overloads of map:

When you call map, the compiler selects the overload that returns a TreeSet, because it is “more specfiic” by the overload resolution rules.

However, if you upcast the TreeSet to Iterable, then the compiler sees only one map operation, which returns an unsorted set.

On Scala 2.12, the situation was different but the result was the same (the source collection type was part of the CanBuildFrom argument to compute the resulting collection).

Unfortunately, I don’t see how we could fix this. I think we should live with this issue but maybe document it better?

[jrudolph]

There's also this issue:

scala> (TreeSet(5,3,2,12,38,2,6,2): Iterable[Int]).map(_ => 5).toList
res1: List[Int] = List(5)

So, there we have an it: Iterable[T] where this isn't true for all f:

it.size == it.map(f).size

[julienrf]

So, there we have an it: Iterable[T] where this isn't true for all f:

it.size == it.map(f).size

This property is not true for all iterables, only for seqs.

[swsnr]

Shouldn't iteration be size- and order-preserving? At least that's my perhaps naive intuitive expectation 🤷

[julienrf]

This is not the case on Iterable, because sets and maps don’t necessarily have a specific iteration order.

[swsnr]

Still, I find it surprising if order gets lost for types which are ordered initially, and I'm also surprised that it.size == it.map(f).size doesn't hold for all iterables. Looks like I assumed a lot of things about iterables which aren't true in the general case; I'd love to see this documented in the scaladoc for Iterable.

[Jasper-M]

I find it surprising if order gets lost for types which are ordered initially, and I'm also surprised that it.size == it.map(f).size doesn't hold for all iterables

Though it would be impossible for both those expectations to hold. You can't have it.map(_ => 5) return a TreeSet and always preserve the size.