The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Difference between List and Set variance?
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 21 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options May 28 2011, 6:29 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Sat, 28 May 2011 15:29:28 -0700
Local: Sat, May 28 2011 6:29 pm
Subject: Difference between List and Set variance?

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.

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
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 6:33 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Sat, 28 May 2011 15:33:28 -0700
Local: Sat, May 28 2011 6:33 pm
Subject: Re: Difference between List and Set variance?

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.

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>

On Sat, May 28, 2011 at 3:29 PM, Meredith Gregory
<lgreg.mered...@gmail.com>wrote:

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 6:49 pm
From: David Hall <d...@cs.berkeley.edu>
Date: Sat, 28 May 2011 15:49:06 -0700
Local: Sat, May 28 2011 6:49 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?
Set[T] extends T=>Boolean so it can't be covariant.

-- David

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

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 6:49 pm
From: Seth Tisue <s...@tisue.net>
Date: Sat, 28 May 2011 18:49:47 -0400
Local: Sat, May 28 2011 6:49 pm
Subject: Re: [scala-user] Difference between List and Set variance?

>>>>> "Meredith" == Meredith Gregory <lgreg.mered...@gmail.com> writes:

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

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.

--
Seth Tisue | Northwestern University | http://tisue.net

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 7:14 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Sat, 28 May 2011 16:14:13 -0700
Local: Sat, May 28 2011 7:14 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

Dear David, et al,

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

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 7:23 pm
From: Kris Nuttycombe <kris.nuttyco...@gmail.com>
Date: Sat, 28 May 2011 17:23:28 -0600
Local: Sat, May 28 2011 7:23 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?
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

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 7:26 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Sat, 28 May 2011 16:26:22 -0700
Local: Sat, May 28 2011 7:26 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

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
i might as well use the moment to get some feedback on the draft while it's
in progress.

On Sat, May 28, 2011 at 4:14 PM, Meredith Gregory
<lgreg.mered...@gmail.com>wrote:

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 28 2011, 8:45 pm
From: Raoul Duke <rao...@gmail.com>
Date: Sat, 28 May 2011 17:45:09 -0700
Local: Sat, May 28 2011 8:45 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?
On Sat, May 28, 2011 at 4:23 PM, Kris Nuttycombe

<kris.nuttyco...@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.

To post a message you must first join this group.
You do not have the permission required to post.
More options May 29 2011, 3:43 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Sun, 29 May 2011 12:43:34 -0700
Local: Sun, May 29 2011 3:43 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

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.nuttyco...@gmail.com>wrote:

> 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

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 29 2011, 5:09 pm
From: martin odersky <martin.oder...@epfl.ch>
Date: Sun, 29 May 2011 23:09:21 +0200
Local: Sun, May 29 2011 5:09 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

On Sun, May 29, 2011 at 1:23 AM, Kris Nuttycombe
<kris.nuttyco...@gmail.com>wrote:

> 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?

> 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

To post a message you must first join this group.
You do not have the permission required to post.
More options May 29 2011, 5:13 pm
From: martin odersky <martin.oder...@epfl.ch>
Date: Sun, 29 May 2011 23:13:04 +0200
Local: Sun, May 29 2011 5:13 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

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

On Sun, May 29, 2011 at 11:09 PM, martin odersky <martin.oder...@epfl.ch>wrote:

--
----------------------------------------------
Martin Odersky
Prof., EPFL <http://www.epfl.ch> and CEO, Typesafe <http://www.typesafe.com>
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

To post a message you must first join this group.
You do not have the permission required to post.
More options May 29 2011, 5:54 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Sun, 29 May 2011 14:54:32 -0700
Local: Sun, May 29 2011 5:54 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

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

On Sun, May 29, 2011 at 2:13 PM, martin odersky <martin.oder...@epfl.ch>wrote:

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 29 2011, 6:18 pm
From: martin odersky <martin.oder...@epfl.ch>
Date: Mon, 30 May 2011 00:18:47 +0200
Local: Sun, May 29 2011 6:18 pm
Subject: Re: [scala-user] Re: Difference between List and Set variance?

On Sun, May 29, 2011 at 11:54 PM, Meredith Gregory <lgreg.mered...@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

Cheers

-- Martin

To post a message you must first join this group.
You do not have the permission required to post.
More options May 30 2011, 2:56 am
From: Mirco Dotta <mirco.do...@gmail.com>
Date: Mon, 30 May 2011 08:56:41 +0200
Local: Mon, May 30 2011 2:56 am
Subject: Re: [scala-user] Re: Difference between List and Set variance?

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

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

Cheers,
Mirco

To post a message you must first join this group.
You do not have the permission required to post.
More options May 30 2011, 3:40 am
Date: Mon, 30 May 2011 00:40:53 -0700
Local: Mon, May 30 2011 3:40 am
Subject: Re: [scala-user] Difference between List and Set variance?

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,

On Sat, May 28, 2011 at 3:29 PM, Meredith Gregory
<lgreg.mered...@gmail.com>wrote:

To post a message you must first join this group.
You do not have the permission required to post.
More options May 30 2011, 8:21 am
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Mon, 30 May 2011 05:21:51 -0700
Local: Mon, May 30 2011 8:21 am
Subject: Re: [scala-user] Difference between List and Set variance?

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

On Mon, May 30, 2011 at 12:40 AM, Vlad Patryshev <vpatrys...@gmail.com>wrote:

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 30 2011, 8:26 am
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Mon, 30 May 2011 05:26:50 -0700
Local: Mon, May 30 2011 8:26 am
Subject: Re: [scala-user] Re: Difference between List and Set variance?

Dear Mirco,

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

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options May 31 2011, 3:12 am
From: Luc Duponcheel <luc.duponch...@gmail.com>
Date: Tue, 31 May 2011 09:12:13 +0200
Local: Tues, May 31 2011 3:12 am
Subject: Re: [scala-user] Difference between List and Set variance?

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

On Mon, May 30, 2011 at 9:40 AM, Vlad Patryshev <vpatrys...@gmail.com>wrote:

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

reality goes far beyond imagination

To post a message you must first join this group.
You do not have the permission required to post.
More options May 31 2011, 10:39 pm
Date: Tue, 31 May 2011 19:39:28 -0700
Local: Tues, May 31 2011 10:39 pm
Subject: Re: [scala-user] Difference between List and Set variance?

Right, Traversable is covariant, pow is contravariant, but what is Set? Is
it, hmm, a functor? Seems like it is not.
Thanks,

On Tue, May 31, 2011 at 12:12 AM, Luc Duponcheel
<luc.duponch...@gmail.com>wrote:

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 1 2011, 2:02 am
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Tue, 31 May 2011 23:02:38 -0700
Local: Wed, Jun 1 2011 2:02 am
Subject: Re: [scala-user] Difference between List and Set variance?

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

On Tue, May 31, 2011 at 7:39 PM, Vlad Patryshev <vpatrys...@gmail.com>wrote:

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

To post a message you must first join this group.
You do not have the permission required to post.
More options Jun 2 2011, 5:26 pm
From: Meredith Gregory <lgreg.mered...@gmail.com>
Date: Thu, 2 Jun 2011 14:26:54 -0700
Local: Thurs, Jun 2 2011 5:26 pm
Subject: Re: [scala-user] Difference between List and Set variance?

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

On Tue, May 31, 2011 at 11:02 PM, Meredith Gregory <lgreg.mered...@gmail.com

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740