Why is Scala an immutable set not covariant in its type?

Question

EDIT : rewrote this question based on original answer

The scala.collection.immutable.Set class scala.collection.immutable.Set not covariant in its type parameter. Why is this?

 import scala.collection.immutable._ def foo(s: Set[CharSequence]): Unit = { println(s) } def bar(): Unit = { val s: Set[String] = Set("Hello", "World"); foo(s); //DOES NOT COMPILE, regardless of whether type is declared //explicitly in the val s declaration } 

Answer 1

Set is invariant in its type parameter due to the concept behind sets as functions. The following signatures should clarify the situation slightly:

 trait Set[A] extends (A=>Boolean) { def apply(e: A): Boolean } 

If Set were covariant in A , the apply method would not be able to take a parameter of type A due to the contravariance of the functions. Set could potentially be contravariant in A , but it also causes problems when you want to do things like this:

 def elements: Iterable[A] 

In short, the best solution is to preserve the invariance of things even for an unchanged data structure. You will notice that immutable.Map also invariant in one of its type parameters.

Answer 2

at http://www.scala-lang.org/node/9764 Martin Odersky writes:

"On the issue of sets, I believe that unevenness also stems from implementations. General sets are implemented as hashtables, which are non-invariant arrays of key type. I agree with this slightly annoying irregularity."

So, it seems that all our efforts to build a fundamental reason for this were wrong :-)

Answer 3

EDIT : for someone wondering why this answer seems a little off topic, this is because I (the questionnaire) changed the question.

Scala type inference is good enough to realize that you want CharSequences, not Strings in some situations. In particular, the following works for me in 2.7.3:

 import scala.collections.immutable._ def findCharSequences(): Set[CharSequence] = Set("Hello", "World") 

How to create immutable. HashSets directly: not necessary. How to optimize the implementation, immutable. HashSets of less than 5 elements are not actually immutable instances. Hashset. This is either EmptySet, Set1, Set2, Set3, or Set4. These subclasses of classes are immutable. Install, but not required. Hashset.