Why is Scala's immutable Set not covariant in its type?

Question

EDIT: Re-written this question based on original answer

The scala.collection.immutable.Set class is 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 because of the concept behind sets as functions. The following signatures should clarify things slightly:

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

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

def elements: Iterable[A]

In short, the best solution is to keep things invariant, even for the immutable data structure. You'll notice that immutable.Map is 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 the non-variance stems also from the implementations. Common sets are implemented as hashtables, which are non-variant arrays of the key type. I agree it's a slightly annoying irregularity."

So, it seems that all of our efforts to construct a principled reason for this were misguided :-)

Answer 3

EDIT: for anyone wondering why this answer seems slightly off-topic, this is because I (the questioner) have modified the question.

Scala's type inference is good enough to figure out that you want CharSequences and 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")

As to how to create immutable.HashSets directly: don't. As an implementation optimization, immutable.HashSets of less than 5 elements are not actually instances of immutable.HashSet. They are either EmptySet, Set1, Set2, Set3, or Set4. These classes subclass immutable.Set, but not immutable.HashSet.