scala - Why does Seq.contains accept type Any rather than the type parameter A?

Question

For example:

scala> val l:List[String] = List("one", "two")
l: List[String] = List(one, two)

scala> l.contains(1) //wish this didn't compile
res11: Boolean = false 

The various explanations of why things were done this way in Java don't seem to apply as much here, as Map and Set do implement the type-safe version of contains and friends. Is there any way to do a type-safe contains on a Seq short of cloning it into a Set?

Answer 1

The problem is that Seq is covariant in its type parameter. This makes a lot of sense for the majority of its functionality. As an immutable container, it really should be covariant. Unfortunately, this does get in the way when they have to define a method which takes some of the parameterized type. Consider the following example:

trait Seq[+A] {
  def apply(i: Int): A       // perfectly valid

  def contains(v: A): Boolean   // does not compile!
}

The problem is that functions are always contravariant in their parameter types and covariant in their return types. Thus, the apply method can return a value of type A because A is covariant along with the return type for apply. However, contains cannot take a value of type A because its parameter must be contravariant.

This problem can be solved in different ways. One option is to simply make A an invariant type parameter. This allows it to be used in both covariant and contravariant contexts. However, this design would mean that Seq[String] would not be a subtype of Seq[Any]. Another option (and the one most often used) is to employ a local type parameter which is bounded below by the covariant type. For example:

trait Seq[+A] {
  def +[B >: A](v: B): Seq[B]
}

This trick retains the Seq[String] <: Seq[Any] property as well as provides some very intuitive results when writing code which uses heterogeneous containers. For example:

val s: Seq[String] = ...
s + 1      // will be of type Seq[Any]

The results of the + function in this example is a value of type Seq[Any], because Any is the least upper-bound (LUB) for the types String and Int (in other words, the least-common supertype). If you think about it, this is exactly the behavior we would expect. If you create a sequence with both String and Int components, then its type should be Seq[Any].

Unfortunately, this trick, while applicable to methods like contains, produces some surprising results:

trait Seq[+A] {
  def contains[B >: A](v: B): Boolean    // compiles just fine
}

val s: Seq[String] = ...
s contains 1        // compiles!

The problem here is that we are calling the contains method passing a value of type Int. Scala sees this and tries to infer a type for B which is a supertype of both Int and A, which in this case is instantiated as String. The LUB for these two types is Any (as shown earlier), and so the local type instantiation for contains will be Any => Boolean. Thus, the contains method appears to not be type safe.

This result isn't an issue for Map or Set because neither of them are covariant in their parameter types:

trait Map[K, +V] {
  def contains(key: K): Boolean    // compiles
}

trait Set[A] {
  def contains(v: A): Boolean      // also compiles
}

So, long story short, the contains method on covariant container types cannot be restricted to only take values of the component type because of the way that functions types work (contravariant in their parameter types). This isn't really a limitation of Scala or bad implementation, it's a mathematical fact.

The consolation prize is that this really isn't an issue in practice. And, as the other answers have mentioned, you can always define your own implicit conversion which adds a "type-safe" contains-like method if you really need the extra check.