Type error not detected in "contains" method

Libraries
1

I have this test code:

object Main:

  trait X0
  class X1(name: String) extends X0
  class X2(name: String) extends X1(name)

  {
    val seq = Seq[X1]()

    seq.contains(3.1415926)  //compiles
    seq.contains("a") //compiles
    seq.contains(X1("a"): X0) //compiles
    seq.contains(X1("a"))
    seq.contains(X2("a"))
  }

  {
    case class MySeq[A]():
      def contains[A1 <: A](a: A1): Boolean = false

    val seq = MySeq[X1]()

    seq.contains(3.1415926) // does not compile
    seq.contains("a")  // does not compile
    seq.contains(X1("a"): X0)  // does not compile
    seq.contains(X1("a"))
    seq.contains(X2("a"))
  }

The signature of “contains” of Seq is:

def contains[A1 >: A](elem: A1): Boolean

Beause of this, checking for the existence of a double, a string, or type X0 is allowed.

If the signature was changed to:

def contains[A1 <: A](elem: A1): Boolean

as I do in the MySeq class, then testing with these invalid types is not possible, the code does not compile, which seems like the proper behavior.

Is this a bug?

Thank you.

2

I don’t think it’s a bug; it’s a design decision of the Seq class I think (to have A1 >: A). It’s due to covariance as BalmungSan mentioned.

Variance of collections is a design choice; for example in Java, Array is treated covariant, which leads to issues in the type system when combined with mutation. In Scala, immutable collections like List, Seq, ArraySeq etc. are covariant, mutable ones like Array, ArrayBuffer are invariant to avoid those issues. (Programming in Scala 5th Edition for further reading)

3

No, is not a bug, it is “working as expected”.

Since the real Seq is covariant (contrary to your MySeq) then the signature you propose is invalid due to Liskov.

A simple way to understand why that is the case is the following:

val numbers: Seq[Int] = Seq(1, 2, 3)
val things: Seq[Any] = numbers // Valid due to covariance.
things.contains("foo") // Valid due subtyping.

Since the previous code MUST compile, then Seq.contains MUST already support Any type.

A common way to avoid most instances of this mistake is using a lint warning everytime the compiler infers Any.

You may also use a more restrictive version of contains based on a Eq typeclass provided by cats.

Another discussion would be if Seqs should be covariant or not, or if subtyping was a good idea or not. But those two would lead to very different programming languages than Scala.

1 Like
4

Many thanks. I’ve been using Scala for many years, and I just realized that Seq was covariant. I am very surprised, as this can lead to a great deal of undetected programming errors. If all Scala collections are like this, I would say that we have a huge issue. If I want the behavior expressed in my “MySeq” type, should I use cats as you mentioned? Thanks! J

5

You may also want to read through the “multiversal equality” document to learn more about equality in general and how Scala now offers a more sophisticated mechanism to compare for equality.

https://docs.scala-lang.org/scala3/reference/contextual/multiversal-equality.html

3 Likes
6

Demonstrating the lint (thanks BalmungSan):

$ scala -Xlint
Welcome to Scala 2.13.14 (OpenJDK 64-Bit Server VM, Java 21.0.2).
Type in expressions for evaluation. Or try :help.

scala> "abc".contains("b")
val res0: Boolean = true

scala> "abc".contains('b'.toInt)
             ^
       warning: a type was inferred to be `AnyVal`; this may indicate a programming error.
val res1: Boolean = true

scala> "abc".contains('b')
val res2: Boolean = true

scala>

Just a moment ago, I avoided contains on String and just used indexOf which is unproblematic. It turned out I needed the index anyway, in order to detect last position for this behavior:

scala> "ab".split('b')
val res3: Array[String] = Array(a)

It looks like Scala 3 does not have the lint yet.

2 Likes
7

Well, note that usually, this is what you would expect since follows the “natural” order of subtyping.
A List of Dogs is a List of Pets.

Well yes, but not really.
First, as mentioned before, the lint for “infer Any” will catch most instances of this mistake.
Second, good testing would usually catch the remaining instances.
Third, folks are usually already conditioned to look for this, this is not different from 1 == "foo".

Now, having said that, yeah I agree it would be great if the type system could catch this.
But this is just a consequence of subtyping.

Yes, you may use contains_ from cats.
Eventually, the stdlib may support something similar, as @alex.boisvert mentioned; but that would need a couple of years.

1 Like
8

I changed the code with:

trait X0 derives CanEqual

And added these options in SBT:

scalacOptions ++= Seq(
“-language:strictEquality”,
“-Xlint:infer-any”
)

And when I compile the code, all calls to “contains” are accepted, no warnings, no errors.

Does it mean that there is no way to detect this issue on the standard “contains” methods of the Scala collections?

Thank you to everyone.

9

I downloaded the Scala3 project, and the string “infer-any” does not appear in the code. So Xlint is just ignored.

Any way to make “contains” safer for Scala 3?

10

This does not work for Scala 3.

11

:crying_cat_face:

3 Likes