Proposal: Make Set covariant


#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).