Scala Sets contain the same elements, but sameElements() returns false

Question

Whilst working through the Scala exercises on Iterables, I encountered the following strange behaviour:

val xs = Set(5,4,3,2,1)
val ys = Set(1,2,3,4,5)
xs sameElements ys       // true

val xs = Set(3,2,1)
val ys = Set(1,2,3)
xs sameElements ys       // false - WAT?!

Surely these Sets have the same elements, and should ignore ordering; and why does this work as expected only for the larger set?

Answer 1

The Scala collections library provides specialised implementations for Sets of fewer than 5 values (see the source). The iterators for these implementations return elements in the order in which they were added, rather than the consistent, hash-based ordering used for larger Sets.

Furthermore, sameElements (scaladoc) is defined on Iterables (it is implemented in IterableLike - see the source); it returns true only if the iterators return the same elements in the same order.

So although Set(1,2,3) and Set(3,2,1) ought to be equivalent, their iterators are different, therefore sameElements returns false.

This behaviour is surprising, and arguably a bug since it violates the mathematical expectations for a Set (but only for certain sizes of Set!).

As I.K. points out in the comments, == works fine if you are just comparing Sets with one another, i.e. Set(1,2,3) == Set(3,2,1). However, sameElements is more general in that it can compare the elements of any two iterables. For example, List(1, 2, 3) == Array(1, 2, 3) is false, but List(1, 2, 3) sameElements Array(1, 2, 3) is true.

More generally, equality can be confusing - note that:

List(1,2,3) == Vector(1,2,3)
List(1,2,3) != Set(1,2,3)
List(1,2,3) != Array(1,2,3)      
Array(1,2,3) != Array(1,2,3)

I have submitted a fix for the Scala exercises that explains the sameElements problem.