Difference between List and Set variance?

127 views
Skip to first unread message

Meredith Gregory

unread,
May 28, 2011, 6:29:28 PM5/28/11
to scala-user
Dear Scalarazzi,

i was surprised by the following.

Best wishes,

--greg

Welcome to Scala version 2.8.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_24).
Type in expressions to have them evaluated.
Type :help for more information.

scala> trait GCG[+A] { def left : List[Either[A,GCG[A]]]; def right : List[Either[A,GCG[A]]] }
defined trait GCG

scala> trait GCG2[+A] { def left : Set[Either[A,GCG[A]]]; def right : Set[Either[A,GCG[A]]] }
<console>:6: error: covariant type A occurs in invariant position in type => Set[Either[A,GCG[A]]] of method left
       trait GCG2[+A] { def left : Set[Either[A,GCG[A]]]; def right : Set[Either[A,GCG[A]]] }
                            ^
<console>:6: error: covariant type A occurs in invariant position in type => Set[Either[A,GCG[A]]] of method right
       trait GCG2[+A] { def left : Set[Either[A,GCG[A]]]; def right : Set[Either[A,GCG[A]]] }
                                                              ^

scala> 

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW

Meredith Gregory

unread,
May 28, 2011, 6:33:28 PM5/28/11
to scala-user
P.S. i guess this must be intentional because it was preserved from 2.8.1 to 2.9

Welcome to Scala version 2.9.0.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_24).
Type in expressions to have them evaluated.
Type :help for more information.

scala> trait GCG[+A] { def left : List[Either[A,GCG[A]]]; def right : List[Either[A,GCG[A]]] }
defined trait GCG

scala> trait GCG2[+A] { def left : Set[Either[A,GCG[A]]]; def right : Set[Either[A,GCG[A]]] }
<console>:8: error: covariant type A occurs in invariant position in type => Set[Either[A,GCG[A]]] of method left
       trait GCG2[+A] { def left : Set[Either[A,GCG[A]]]; def right : Set[Either[A,GCG[A]]] }
                            ^
<console>:8: error: covariant type A occurs in invariant position in type => Set[Either[A,GCG[A]]] of method right
       trait GCG2[+A] { def left : Set[Either[A,GCG[A]]]; def right : Set[Either[A,GCG[A]]] }
                                                              ^

scala> 

David Hall

unread,
May 28, 2011, 6:49:06 PM5/28/11
to Meredith Gregory, scala-user
Set[T] extends T=>Boolean so it can't be covariant.

-- David

On Sat, May 28, 2011 at 3:33 PM, Meredith Gregory

Seth Tisue

unread,
May 28, 2011, 6:49:47 PM5/28/11
to scala-user
>>>>> "Meredith" == Meredith Gregory <lgreg.m...@gmail.com> writes:

Meredith> Dear Scalarazzi, i was surprised by the following.

http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-not-covariant-in-its-type

I don't think the question was ever fully answered. Daniel makes it
clear the issue is the contains method. For both List and Set, you can
either have covariance, or you can have a contains method that takes an
A (instead of Any), but you can't have both.

In the case of List, covariance was chosen, and List.contains takes Any.
In the case of Set, invariance was chosen, and Set.contains takes A.

The question remains: why was this design decision made?

--
Seth Tisue | Northwestern University | http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/

Meredith Gregory

unread,
May 28, 2011, 7:14:13 PM5/28/11
to David Hall, scala-user
Dear David, et al,

First of all, thank you for your answers!

This particular situation strikes me as a case where inheritance is once again being very ... um... helpful. If the choice was made to have an interpretation of Set as Function (via a consumer of Set that produced this interpretation, such as trait SetsAreFunctions[S,T] { def asFunction( s : Set[S] ) : S => T } ) then one could make a lot of interesting choices. For example, Fuzzy Sets might ask for an interpretation Set[T] => T => Float. Finite sets could be defined as partial functions on infinite domains. Etc.

Moreover, the example used to justify the design decision under discussion here doesn't actually distinguish Set from List, imho. There is no compelling a priori reason to prefer the interpretation taking Set[T] to T => Boolean that would exclude demanding the same of List[T]. 

A good friend of mine suggests that being available is preferable to being helpful. In this case, i'm quite certain i would prefer if inheritance were merely available, and not quite so helpful. i just spent a great deal of time converting some code samples (that really needed Set semantics, but were originally expressed using List) from List to Set. Only to find at the last moment that i have two choices in front of me
  • put everything back to using List and redo set semantics in the places where i need to suppress duplication and ignore order (obviously, i'm getting a lot of reuse value from the inheritance here!); or
  • implement my collection type that has set semantics and corresponding variance (another delightful moment of productivity and reuse value i've derived from the helpfulness of inheritance)

Best wishes,

--greg

Kris Nuttycombe

unread,
May 28, 2011, 7:23:28 PM5/28/11
to Meredith Gregory, David Hall, scala-user
I'd like to chime in that I too think inheritance from the various
function types (for Map, List, Set, etc.) is wrongheaded and overly
limiting; implicits would be vastly preferable and could be
implemented without breaking source compatibility in most cases, as
was done with the collections library in 2.8.0. Much like equality,
one very frequently wants function semantics of collections to be
contextual and unrelated to the inheritance hierarchy.

Is there any chance of such a change being considered?

Kris

Meredith Gregory

unread,
May 28, 2011, 7:26:22 PM5/28/11
to David Hall, scala-user
P.S. The irony of this particular situation is just too sweet not to share more. i was in the middle of writing up a blog entry from material that i might end up cutting from the book. The subject matter is precisely a critique of this sort of design choice -- but made from the positive side by showing the benefits of organizing things as i have suggested below. You can see a draft of the entry here. i might as well use the moment to get some feedback on the draft while it's in progress.

Raoul Duke

unread,
May 28, 2011, 8:45:09 PM5/28/11
to scala-user
On Sat, May 28, 2011 at 4:23 PM, Kris Nuttycombe
<kris.nu...@gmail.com> wrote:
> limiting; implicits would be vastly preferable and could be
> implemented without breaking source compatibility in most cases, as

mmm, makes me think of typeclasses.

Meredith Gregory

unread,
May 29, 2011, 3:43:34 PM5/29/11
to Kris Nuttycombe, martin odersky, David Hall, scala-user
Dear Martin,

i think Kris' question has some merit. What's your take?

Best wishes,

--greg

On Sat, May 28, 2011 at 4:23 PM, Kris Nuttycombe <kris.nu...@gmail.com> wrote:

martin odersky

unread,
May 29, 2011, 5:09:21 PM5/29/11
to Kris Nuttycombe, Meredith Gregory, David Hall, scala-user
I think it's too late for that. We really have to take binary compatibility more seriously than up to now. And that means more or less freezing collections. Some small improvements, maybe, but there will be no more changes in the design.

 -- Martin

martin odersky

unread,
May 29, 2011, 5:13:04 PM5/29/11
to Kris Nuttycombe, Meredith Gregory, David Hall, scala-user
On the issue of sets, I believe the non-variance stems also from the implementations. Common sets are implemented as hashtables, which are non-variant arrays of the key type. I agree it's a slighly annoying irregularity.

 -- Martin
--
----------------------------------------------
Martin Odersky
Prof., EPFL and CEO, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

Meredith Gregory

unread,
May 29, 2011, 5:54:32 PM5/29/11
to martin odersky, Kris Nuttycombe, David Hall, scala-user
Dear Martin,

Thanks for your input! If i understand correctly, it will be up to the community to grow some separate Set-like collections with consistent variance; and, if needed, provide views of these collections as functions. That sounds like a worthy task!

Also, just for my own understanding, can you provide pointers to information about the approach to binary compatibility? i'd like to verify for myself that Kris proposal cannot be made to work in a way that supports binary compatibility.

Best wishes,

--greg

martin odersky

unread,
May 29, 2011, 6:18:47 PM5/29/11
to Meredith Gregory, Kris Nuttycombe, David Hall, scala-user, Mirco Dotta
On Sun, May 29, 2011 at 11:54 PM, Meredith Gregory <lgreg.m...@gmail.com> wrote:
Dear Martin,

Thanks for your input! If i understand correctly, it will be up to the community to grow some separate Set-like collections with consistent variance; and, if needed, provide views of these collections as functions. That sounds like a worthy task!

Also, just for my own understanding, can you provide pointers to information about the approach to binary compatibility?

Mirco Dotta has recently categorized what incompatibilities can arise. He might be the best source to give more info.

Cheers

 -- Martin

Mirco Dotta

unread,
May 30, 2011, 2:56:41 AM5/30/11
to Meredith Gregory, martin odersky, Kris Nuttycombe, David Hall, scala-user

> Also, just for my own understanding, can you provide pointers to information about the approach to binary compatibility?


We have developed a tool that will help you diagnose binary incompatibilities. We plan to get it out as a beta during Scala Days
(so just a few days from now!).

As for more detailed information on the sort of binary incompatibilities that the tool checks, I'm working on a document that I hope
will be soon public. It should help taking the right decisions when evolving your classes and traits. The form is similar to
Java's binary compatibility document (http://java.sun.com/docs/books/jls/second_edition/html/binaryComp.doc.html).

Of course if you have specific questions I'll be happy to answer them.

Cheers,
Mirco


Vlad Patryshev

unread,
May 30, 2011, 3:40:53 AM5/30/11
to Meredith Gregory, scala-user
While it is easy to turn an obviously invariant Set[A] to contravariant [A->Boolean], it might make sense to have something covariant... something like Iterable[+A].

What's interesting is how we can casually disambiguate (between) these two functors. And whether it is feasible to disambiguate in current programming practice. What we call "sets" in Scala are not sets in any scientific sense anyway, are they? What Set[A] means is a "powertype", right?

Thanks,
-Vlad

Meredith Gregory

unread,
May 30, 2011, 8:21:51 AM5/30/11
to Vlad Patryshev, scala-user
Dear Vlad,

To my mind there are several possible interpretations of Set[A]. One is that it simply is a concrete specialization of A => Boolean. Another is that it is a duplicate-free, order-insensitive collection. Another is that it is a Set in the sense of FM-Set Theory, i.e. a Set with atoms where the type of atoms is A.

Best wishes,

--greg

Meredith Gregory

unread,
May 30, 2011, 8:26:50 AM5/30/11
to Mirco Dotta, martin odersky, Kris Nuttycombe, David Hall, scala-user
Dear Mirco,

Thanks! i'm looking forward to your document and tool!

Best wishes,

--greg

Luc Duponcheel

unread,
May 31, 2011, 3:12:13 AM5/31/11
to Vlad Patryshev, Meredith Gregory, scala-user
Hi,

is the original question (replacing inheritance with implicits)
not somehow circumventing this variance issue in the first place?

scala> implicit def toPow[X](set: Set[X]): Function[X, Boolean] = new Function[X, Boolean] {
     |  def apply(x: X) = set.contains(x)
     | }
toPow: [X](set: Set[X])(X) => Boolean

scala> implicit def toTrav[X](set: Set[X]): Traversable[X] = new Traversable[X] {
     |  def foreach[U](f: X => U): Unit = set.foreach(f)
     | }
toTrav: [X](set: Set[X])Traversable[X]


maybe I'm plain wrong here

I mean: variance issues will eventually pop up anyway
(and, if yes, then, maybe, it makes sense that type inference would be less strict when implicits are involved than when inheritance is involved (?))

... just a wild thought ...

Luc
--
   __~O
  -\ <,
(*)/ (*)

reality goes far beyond imagination

Vlad Patryshev

unread,
May 31, 2011, 10:39:28 PM5/31/11
to Luc Duponcheel, Meredith Gregory, scala-user
Right, Traversable is covariant, pow is contravariant, but what is Set? Is it, hmm, a functor? Seems like it is not.
Thanks,
-Vlad

Meredith Gregory

unread,
Jun 1, 2011, 2:02:38 AM6/1/11
to Vlad Patryshev, Luc Duponcheel, scala-user
Dear Vlad,

i guess the point is that it is not one functor. There are many reasonable functors, each with different characteristics. This is why inheritance gets in the way. It's not flexible enough to model the range of useful contexts. That's why the implicits route has now been proposed by no less than three parties: myself, Kris and Luc.

Best wishes,

--greg

Meredith Gregory

unread,
Jun 2, 2011, 5:26:54 PM6/2/11
to scala-user, Luc Duponcheel, Vlad Patryshev
Dear All,

So, i looked into this a bit more, from the perspective of where to inject a collection with Set-like capabilities (order insensitive, no duplicates; or, equationally, respecting S + S = S and S1 + S2 = S2 + S1) and not only is SetLike invariant, but Subtractable is also invariant. Subtractable extends AnyRef, so i don't understand the reason for this choice of variance constraint.  

Best wishes,

--greg
Reply all
Reply to author
Forward
0 new messages