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

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.

Answer 2

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.