Proposal: Make Set covariant


#13

I object making contains an extension method for Set. It is the essential operation of sets.

Making Seq#contains an extension method is good, as it is not part of the core definition of a sequence.

If we do Map[K, +V] (invariance on K) then I think it naturally entails that Set[K] is invariant on K. Unless we want to do Map[+K, +V], not <: (K => V)?


#14

How would that work? I remember trying to define a contains extension method for a covariant set-like data type. I tried all kinds of tricks (such as various implicit evidence schemes) to prevent it from upcasting the type argument on application, but did not find any way to do it – which is actually a testament to the completeness of the compiler’s type inference.

EDIT: as pointed out by @Jasper-M it turns out that this works and is probably a good solution to the problem.


#15

Maybe I’m misunderstanding you, but what doesn’t work about:

implicit class HasSyntax[A](private val self: Seq[A]) extends AnyVal {
  def has(a: A): Boolean = self.contains(a )
}
scala> List(1,2,3).contains("a")
res9: Boolean = false

scala> List(1,2,3).has("a")
                       ^
       error: type mismatch;
        found   : String("a")
        required: Int

#16

I can image that @LPTK does not like that self must have a suitable contains method that can be called by the extension ops:

trait Container[+A] {
  private[Container] def permissiveContains[B >: A](b: B): Boolean
}

object Container {

  implicit class ContainerOps[A](val container: Container[A]) {
    def contains(a: A): Boolean = container.permissiveContains(a)
  }

}


#17

Hmm… strange. I must have misremembered my old experiments, then. Please disregard my objection :slight_smile:


#18

I checked. The no-covariance trick works in Scala 2 but not in Dotty, so probably @LPTK did the experiments in Dotty. Dotty’s type inference is more global, so that it can handle the case. This is good in principle, but it does deprive us of the trick in question.


#19

There is a way that seems to work in both. I don’t like it, but still.

implicit class HasSyntax[A](val s: Seq[A]) extends AnyVal {
  def has[B](a: B)(implicit ev: B <:< A): Boolean = s contains a
}

So, we’ve almost repeated that Seq is covariant by using <:< here.

Then those work well:

def u[A](s: Seq[A], a: A) = s has a // compiles :-)
def v(s: Seq[Int]) = s has 5 // compiles :-)

And even artificially introduced method-like covariancy works:

trait A
trait B extends A
  
def v(s: Seq[A], b: B) = s has b // compiles :-)

And this does not compile both in Scala 2 and Dotty:

def w(s: Seq[Int]) = s has "your mom" // does not compile :-)

But all this stuff that can be done only through extension methods (which seems to be not intended for this naturally) looks really weird. Isn’t there any way to set type inference bounds during declaration of methods/arguments? It looks like those cheats we are doing through extension methods should be done when declaring a class (but maybe I have the wrong feeling).


#20

I believe Kotlin has an escape hatch that allows the programmer to say “No really, allow this use of the type paramter in a variance incorrect location.” I’m not really a fan of this approach (basically break the type system to allow something that is incorrect, but “useful”). But if we are able to make it happen with extension methods anyway then maybe it’s a reasonable thing to do.

(PS: I was unable to find documentation of the Kotlin escape hatch, but I specifically remember hearing about it in a talk.)


#21

Scala has @scala.annotation.uncheckedVariance for that purpose. But I think people prefer to use that one only for internals.


#22

We can’t use @uncheckedVariance for contains because it would be unsafe, see https://github.com/scala/collection-strawman/issues/100#issuecomment-309064448


#23

@buzden Ah, that’s quite ingenious! Using the proposed extension clause syntax it also looks less heinous than with implicit class:

extension hasOp[A] for Seq[A] {
  def has[B](a: B)(implicit ev: B <:< A): Boolean = s contains a
}

#24

Omg, the gates of hell are open again.

There’s probably no way to define two functors.


#25

I think here for contains we have different situation – we do not want to put it in the unchecked variance place, we want to “stop” type inference a little bit earlier, like if [B] type argument of Seq's contains is not involved in the whole expression type inference.

Well, maybe, these two are two sides of the same coin.

Did you mean this contains a instead of s contains a?


#26

this contains a, yes.


#27

I’m sorry if i’m out of context, i know it’s big.

But what’s wrong with this approach:

  • some operations are covariant, some are contravariant, group them in two traits
  • if something needs operations from both traits, it implements both and becomes invariant
  • but you can still view the invariant thing as either of those two so if you need covariant view, you lose the contravariant ops
@ trait ContravariantPart[-A] extends (A => Boolean) 
defined trait ContravariantPart

@ trait CovariantPart[+A] { def head: Option[A] } 
defined trait CovariantPart

@ trait InvariantThing[A] extends ContravariantPart[A] with CovariantPart[A] 
defined trait InvariantThing

@ lazy val thing: InvariantThing[String] = ??? 
thing: InvariantThing[String] = <lazy>

@ trait A; trait B extends A; trait C extends B 
defined trait A
defined trait B
defined trait C

@ lazy val thing: InvariantThing[B] = ??? 
thing: InvariantThing[B] = <lazy>

@ lazy val covariantViewOnThing: CovariantPart[A] = thing 
covariantViewOnThing: CovariantPart[A] = <lazy>

@ lazy val contravariantViewOnThing: ContravariantPart[C] = thing 
contravariantViewOnThing: ContravariantPart[C] = <lazy>

@ lazy val x: Option[A] = covariantViewOnThing.head 
x: Option[A] = <lazy>

@ lazy val y: Boolean = contravariantViewOnThing(??? : C) 
y: Boolean = <lazy>

#28

As far as I know, this is exactly what was proposed by @psp in his revolutionary attempt of collections library. His terms were extensional and intensional sets: one is for iterable (enumerable) set (covariant), another is for sets as a function of existence (contravariant), accordingly (here is a timestamped video where he talked about sets).

Parallel problem is whether should we have operations like union and element subtraction in all of types of such sets — do we always need or want to have all of them or it is an orthogonal thing and we should have all combinations available, i.e. six of such sets (three for extensional, intensional and invariant multiplied by simple and growable/subtractable).

I don’t know whether or not this highly grained division has big problems, but I have the general feeling that we don’t have both extensional and intensional property of a single set at the same time most of the time. So, it means that dividing them should work well.

Another question is whether or not it can be thought to change such a fundamental construct like a set in the language (looking at how much effort is spent on lighter change of the internal collections architecture when moving from 2.12 to 2.13). But, probably, now (when moving from Scala 2 to Scala 3) is the right moment to do this.


#29

I disagree. Our intent is that the Scala 3 std lib will be identical to the Scala 2.14 stdlib (to ease migration). 2.13 is a library release, so we did the library part of what we wanted to work towards for Scala 3. (We may tweak the std lib a tiny bit in 2.14 to improve compatibility.)

Scala 2.14 will be a compiler release, where we’ll align as much as possible post-typer with Scala 3. (Bytecode gen is already shared.)

The end goal: Scala 3 “only” changes the frontend (typer + macros).


#30

Oh, you are right. I meant generally “at some point on movement from 2.12 to 3”, I didn’t mean “from 2.14 to 3”.

And I understand that it seems that opportunity of such big changes to be done now (even if enough part of the community would agree that it’s worth to be done) is lost.


#31

Right, we agree then :slight_smile: We’ll be in feature freeze for the collections in a week :wink:


#32

The principled way is to introduce typeclass Eq[-A] in Scala core, and let Set[A] contains an Eq[A]. (similar to cats.kernel.Eq[A] but contravariant, have to wait for Dotty for fixing the problem of resolving a contravariant implicit).

I believe at the current stage we have to accept the status quo of universal equality and let it be. (I’m in favor of removing universal equality completely so that every == requires an implicit Eq[A], but this is not doable in the near future).