background
List’s contains
accepts arbitrary type into the parameter, which has bitten many of us over the years.
https://twitter.com/mpilquist/status/1042954337222369281
Let’s see Seth’s question from 2010. Why does Seq.contains take an Any argument, instead of an argument of the sequence type?
scala> val l = List(1,2,3,4)
l: List[Int] = List(1, 2, 3, 4)
scala> l.contains("wat")
res3: Boolean = false
2.13.x definition of contains method looks like this: scala/src/library/scala/collection/Seq.scala at v2.13.0-M5 · scala/scala · GitHub
def contains[A1 >: A](elem: A1): Boolean = exists (_ == elem)
If we read the code’s intent, this should in theory prevent "wat"
from getting accepted because "wat"
does not satisfy String >: Int
test.
analysis
The common explanation for this phenomena is because Seq
is covariant. I think it’s a misleading argument since if we supply the type parameter A1
would actually do the job.
scala> l.contains[String]("wat")
^
error: type arguments [String] do not conform to method contains's type parameter bounds [A1 >: Int]
To me, this is a demonstration that the bug is actually in the type inferencer calculating least upper bound (LUB) too early. To quote Daniel Spiewak’s analysis from 2010:
The problem here is that we are calling the
contains
method passing a value of typeString
. Scala sees this and tries to infer a type forB
which is a supertype of bothString
andA
, which in this case is instantiated asInt
. The LUB for these two types isAny
(as shown earlier), and so the local type instantiation forcontains
will beAny => Boolean
. Thus, thecontains
method appears to not be type safe.
(Ed. I flipped String
and Int
to match our example)
In other words, we can retain the current covariant collection design, but maybe by fixing the type inference, we can try to fix this thing.
scalafix-noinfer
As a desperate workaround at the tooling layer I’ve started looking into linting tool trying to catch bad type inference. See stricter Scala with -Xlint, -Xfatal-warnings, and Scalafix. But it would be better if we didn’t have to do this.
Paul Phillips knew how to fix this in 2012
See scare-quoted “type-safe” contains method for covariant collections.
class MyCovariantCollection[+T, +CC[X] <: Seq[X]](xs: CC[T]) {
// Oops, our "evidence" seems to be useless, as what we want
// to know is that T1 <:< T, but of course we can't do that because
// of the variance position.
def contains[T1](x: T1)(implicit ev: T <:< T1): Boolean = xs contains x
}
Let’s try this out.
scala> val xs = new MyCovariantCollection(List(1, 2, 3))
xs: MyCovariantCollection[Int,List] = MyCovariantCollection@177ad340
scala> xs.contains("wat")
^
error: Cannot prove that Int <:< String.
It works!
Paul provides the explanation as follows:
// But wait! Unspecified implementation vagaries to the rescue!
object Test extends App {
val xs = new MyCovariantCollection(List(1, 2, 3))
assert(xs contains "abc", "I'm sure it's in there somewhere")
}
// Thank-you type inference algorithm! Pick the most specific
// type while resolving the first parameter list without regard
// for the fact that we are doomed once you see the second
// parameter list. That's what we want today.
Could we please use this trick for contains
?