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?

Accepted Answer

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.

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

Solution

Problem

Related problems