- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# Why Set aren't covariant

Thu, 2009-07-23, 11:37

In this

http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-no...

post

an answer says that Set are invariant in its type parameter because of the

concept behind sets as functions.

Then the author of the question asked what advantages does "a set as a

function" has over a "set as a collection" ?

I'm just wondering the same thing as I end up quite often using a List

rather than a Set (in places where a Set would be more appropriate and more

meaningful) because of the variance difference.

Does anyone has an answer to that ?

If this has to remain like that how would you work around this problem ?

Thu, 2009-07-23, 13:57

#2
Re: Why Set aren't covariant

I'm not sure to understand why the contains method is contravariant. Actually

I don't think it has a type parameter.

Then, the "set as a function" means that in scala implementation, a set is a

function. Since a function has a contravariant type parameter, the set type

parameter can't be covariant. At best it can be invariant.

The question is, why do we need to define a set as a function and not as a

kind of collection (no duplicate, no order) which could be covariant when

immutable.

Of course a contravariant set doesn't make sense.

David MacIver wrote:

>

> 2009/7/23 mustaghattack :

>>

>> In this

>> http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-no...

>> post

>> an answer says that Set are invariant in its type parameter because of

>> the

>> concept behind sets as functions.

>>

>> Then the author of the question asked what advantages does "a set as a

>> function" has over a "set as a collection" ?

>>

>> I'm just wondering the same thing as I end up quite often using a List

>> rather than a Set (in places where a Set would be more appropriate and

>> more

>> meaningful) because of the variance difference.

>>

>> Does anyone has an answer to that ?

>

> It's less about "set as a function" and more about "set as thing which

> has a contravariant method"

>

> The problem is that the Set[T] has the method

>

> def contains(t : T) : Boolean;

>

> So a Set[String] should have the method

>

> def contains(t : String) : Boolean;

>

> while a Set[Any] should have the method

>

> def contains(t : Any) : Boolean;

>

> Set[String] doesn't have the method which takes an Any (and it

> shouldn't, both for reasons of implementation and type safety), so it

> can't possibly be a Set[Any].

>

>> If this has to remain like that how would you work around this problem ?

>

> It's a feature, not a problem. :-) If you have a Set[S] and want to

> use it covariantly you're free to treat it as an Iterable[T] for any T

>>: S, just not a Set[T].

>

>

Thu, 2009-07-23, 14:17

#3
Re: Why Set aren't covariant

David already explained it quite nicely. In the contains method the type parameter is used in a contravariant position.

Now you can question the usefullness of getting a compile error (type missmatch) for:

val stringSet : Set[String] = ...

stringSet.contains(1)

^^^

But the problem is not the Set being a Function.

Kind regards,

Jan

2009/7/23 mustaghattack <biethb [at] gmail [dot] com>

Now you can question the usefullness of getting a compile error (type missmatch) for:

val stringSet : Set[String] = ...

stringSet.contains(1)

^^^

But the problem is not the Set being a Function.

Kind regards,

Jan

2009/7/23 mustaghattack <biethb [at] gmail [dot] com>

I'm not sure to understand why the contains method is contravariant. Actually

I don't think it has a type parameter.

Then, the "set as a function" means that in scala implementation, a set is a

function. Since a function has a contravariant type parameter, the set type

parameter can't be covariant. At best it can be invariant.

The question is, why do we need to define a set as a function and not as a

kind of collection (no duplicate, no order) which could be covariant when

immutable.

Of course a contravariant set doesn't make sense.

David MacIver wrote:

>

> 2009/7/23 mustaghattack <biethb [at] gmail [dot] com>:

>>

>> In this

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

>> post

>> an answer says that Set are invariant in its type parameter because of

>> the

>> concept behind sets as functions.

>>

>> Then the author of the question asked what advantages does "a set as a

>> function" has over a "set as a collection" ?

>>

>> I'm just wondering the same thing as I end up quite often using a List

>> rather than a Set (in places where a Set would be more appropriate and

>> more

>> meaningful) because of the variance difference.

>>

>> Does anyone has an answer to that ?

>

> It's less about "set as a function" and more about "set as thing which

> has a contravariant method"

>

> The problem is that the Set[T] has the method

>

> def contains(t : T) : Boolean;

>

> So a Set[String] should have the method

>

> def contains(t : String) : Boolean;

>

> while a Set[Any] should have the method

>

> def contains(t : Any) : Boolean;

>

> Set[String] doesn't have the method which takes an Any (and it

> shouldn't, both for reasons of implementation and type safety), so it

> can't possibly be a Set[Any].

>

>> If this has to remain like that how would you work around this problem ?

>

> It's a feature, not a problem. :-) If you have a Set[S] and want to

> use it covariantly you're free to treat it as an Iterable[T] for any T

>>: S, just not a Set[T].

>

>

--

View this message in context: http://www.nabble.com/Why-Set-aren%27t-covariant-tp24623221p24625028.html

Sent from the Scala - User mailing list archive at Nabble.com.

Thu, 2009-07-23, 14:17

#4
Re: Why Set aren't covariant

mustaghattack wrote:

> I'm not sure to understand why the contains method is contravariant. Actually

> I don't think it has a type parameter.

>

> Then, the "set as a function" means that in scala implementation, a set is a

> function. Since a function has a contravariant type parameter, the set type

> parameter can't be covariant. At best it can be invariant.

>

> The question is, why do we need to define a set as a function and not as a

> kind of collection (no duplicate, no order) which could be covariant when

> immutable.

>

> Of course a contravariant set doesn't make sense.

>

>

>

> David MacIver wrote:

>

>> 2009/7/23 mustaghattack :

>>

>>> In this

>>> http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-no...

>>> post

>>> an answer says that Set are invariant in its type parameter because of

>>> the

>>> concept behind sets as functions.

>>>

>>> Then the author of the question asked what advantages does "a set as a

>>> function" has over a "set as a collection" ?

>>>

>>> I'm just wondering the same thing as I end up quite often using a List

>>> rather than a Set (in places where a Set would be more appropriate and

>>> more

>>> meaningful) because of the variance difference.

>>>

>>> Does anyone has an answer to that ?

>>>

>> It's less about "set as a function" and more about "set as thing which

>> has a contravariant method"

>>

>> The problem is that the Set[T] has the method

>>

>> def contains(t : T) : Boolean;

>>

>> So a Set[String] should have the method

>>

>> def contains(t : String) : Boolean;

>>

>> while a Set[Any] should have the method

>>

>> def contains(t : Any) : Boolean;

>>

>> Set[String] doesn't have the method which takes an Any (and it

>> shouldn't, both for reasons of implementation and type safety), so it

>> can't possibly be a Set[Any].

>>

>>

>>> If this has to remain like that how would you work around this problem ?

>>>

>> It's a feature, not a problem. :-) If you have a Set[S] and want to

>> use it covariantly you're free to treat it as an Iterable[T] for any T

>>

>>> : S, just not a Set[T].

>>>

>>

>

>

Set is a type constructor. The Set type constructor is invariant in its

type argument (call it T). This is because T appears in a contravariant

position (contains) as well as a covariant position (e.g. elements).

This makes Set an exponential functor (ExpFunctor). An ExpFunctor cannot

be covariant.

To give some simpler examples:

case class IntCovariantFunctor[+A](f: Int => A)

case class IntContravariantFunctor[-A](f: A => Int)

case class IntExpFunctor[A](f: A => (Int, A))

Set is like IntExpFunctor. List is like IntCovariantFunctor. Set is not

like List with respect to variance.

Thu, 2009-07-23, 14:27

#5
Re: Why Set aren't covariant

Ok, sorry I must have missed the point but why do we want the contains method

to be contravariant ?

Tony Morris-4 wrote:

>

> mustaghattack wrote:

>> I'm not sure to understand why the contains method is contravariant.

>> Actually

>> I don't think it has a type parameter.

>>

>> Then, the "set as a function" means that in scala implementation, a set

>> is a

>> function. Since a function has a contravariant type parameter, the set

>> type

>> parameter can't be covariant. At best it can be invariant.

>>

>> The question is, why do we need to define a set as a function and not as

>> a

>> kind of collection (no duplicate, no order) which could be covariant when

>> immutable.

>>

>> Of course a contravariant set doesn't make sense.

>>

>>

>>

>> David MacIver wrote:

>>

>>> 2009/7/23 mustaghattack :

>>>

>>>> In this

>>>> http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-no...

>>>> post

>>>> an answer says that Set are invariant in its type parameter because of

>>>> the

>>>> concept behind sets as functions.

>>>>

>>>> Then the author of the question asked what advantages does "a set as a

>>>> function" has over a "set as a collection" ?

>>>>

>>>> I'm just wondering the same thing as I end up quite often using a List

>>>> rather than a Set (in places where a Set would be more appropriate and

>>>> more

>>>> meaningful) because of the variance difference.

>>>>

>>>> Does anyone has an answer to that ?

>>>>

>>> It's less about "set as a function" and more about "set as thing which

>>> has a contravariant method"

>>>

>>> The problem is that the Set[T] has the method

>>>

>>> def contains(t : T) : Boolean;

>>>

>>> So a Set[String] should have the method

>>>

>>> def contains(t : String) : Boolean;

>>>

>>> while a Set[Any] should have the method

>>>

>>> def contains(t : Any) : Boolean;

>>>

>>> Set[String] doesn't have the method which takes an Any (and it

>>> shouldn't, both for reasons of implementation and type safety), so it

>>> can't possibly be a Set[Any].

>>>

>>>

>>>> If this has to remain like that how would you work around this problem

>>>> ?

>>>>

>>> It's a feature, not a problem. :-) If you have a Set[S] and want to

>>> use it covariantly you're free to treat it as an Iterable[T] for any T

>>>

>>>> : S, just not a Set[T].

>>>>

>>>

>>

>>

> Set is a type constructor. The Set type constructor is invariant in its

> type argument (call it T). This is because T appears in a contravariant

> position (contains) as well as a covariant position (e.g. elements).

> This makes Set an exponential functor (ExpFunctor). An ExpFunctor cannot

> be covariant.

>

> To give some simpler examples:

>

> case class IntCovariantFunctor[+A](f: Int => A)

> case class IntContravariantFunctor[-A](f: A => Int)

> case class IntExpFunctor[A](f: A => (Int, A))

>

> Set is like IntExpFunctor. List is like IntCovariantFunctor. Set is not

> like List with respect to variance.

>

Thu, 2009-07-23, 14:57

#6
Re: Why Set aren't covariant

To make my point clearer, why scala doesn't provide an immutable covariant

Set like List. Something like :

abstract class CovSet[+A] {

val elements : List[A]

def contains[B >:A]( elem : B ) = elements.exists( _ == elem )

def +[B >:A]( elem : B ) = CovSet( elem :: elements.remove( _ == elem ) )

}

object CovSet {

def apply[A]( content : List[A] ) : CovSet[A] = new CovSet[A] {

val elements = content

}

}

mustaghattack wrote:

>

> Ok, sorry I must have missed the point but why do we want the contains

> method to be contravariant ?

>

>

>

> Tony Morris-4 wrote:

>>

>> mustaghattack wrote:

>>> I'm not sure to understand why the contains method is contravariant.

>>> Actually

>>> I don't think it has a type parameter.

>>>

>>> Then, the "set as a function" means that in scala implementation, a set

>>> is a

>>> function. Since a function has a contravariant type parameter, the set

>>> type

>>> parameter can't be covariant. At best it can be invariant.

>>>

>>> The question is, why do we need to define a set as a function and not as

>>> a

>>> kind of collection (no duplicate, no order) which could be covariant

>>> when

>>> immutable.

>>>

>>> Of course a contravariant set doesn't make sense.

>>>

>>>

>>>

>>> David MacIver wrote:

>>>

>>>> 2009/7/23 mustaghattack :

>>>>

>>>>> In this

>>>>> http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-no...

>>>>> post

>>>>> an answer says that Set are invariant in its type parameter because of

>>>>> the

>>>>> concept behind sets as functions.

>>>>>

>>>>> Then the author of the question asked what advantages does "a set as a

>>>>> function" has over a "set as a collection" ?

>>>>>

>>>>> I'm just wondering the same thing as I end up quite often using a List

>>>>> rather than a Set (in places where a Set would be more appropriate and

>>>>> more

>>>>> meaningful) because of the variance difference.

>>>>>

>>>>> Does anyone has an answer to that ?

>>>>>

>>>> It's less about "set as a function" and more about "set as thing which

>>>> has a contravariant method"

>>>>

>>>> The problem is that the Set[T] has the method

>>>>

>>>> def contains(t : T) : Boolean;

>>>>

>>>> So a Set[String] should have the method

>>>>

>>>> def contains(t : String) : Boolean;

>>>>

>>>> while a Set[Any] should have the method

>>>>

>>>> def contains(t : Any) : Boolean;

>>>>

>>>> Set[String] doesn't have the method which takes an Any (and it

>>>> shouldn't, both for reasons of implementation and type safety), so it

>>>> can't possibly be a Set[Any].

>>>>

>>>>

>>>>> If this has to remain like that how would you work around this problem

>>>>> ?

>>>>>

>>>> It's a feature, not a problem. :-) If you have a Set[S] and want to

>>>> use it covariantly you're free to treat it as an Iterable[T] for any T

>>>>

>>>>> : S, just not a Set[T].

>>>>>

>>>>

>>>

>>>

>> Set is a type constructor. The Set type constructor is invariant in its

>> type argument (call it T). This is because T appears in a contravariant

>> position (contains) as well as a covariant position (e.g. elements).

>> This makes Set an exponential functor (ExpFunctor). An ExpFunctor cannot

>> be covariant.

>>

>> To give some simpler examples:

>>

>> case class IntCovariantFunctor[+A](f: Int => A)

>> case class IntContravariantFunctor[-A](f: A => Int)

>> case class IntExpFunctor[A](f: A => (Int, A))

>>

>> Set is like IntExpFunctor. List is like IntCovariantFunctor. Set is not

>> like List with respect to variance.

>>

Thu, 2009-07-23, 15:27

#7
Re: Why Set aren't covariant

mustaghattack schrieb:

> Ok, sorry I must have missed the point but why do we want the contains method

> to be contravariant ?

We don't *want* the type parameter T to appear in a contravariant position in

contains, any more than we *want* 11 to be prime.

It is just so that it does, just like 11 happens to be prime.

- Florian.

Thu, 2009-07-23, 18:17

#8
Re: Why Set aren't covariant

List has a method contains as well, and it is covariant. List's contains receives Any, while Set's contains receives "A", the type parameter for Set. If you go through other methods on Set with elements in contravariant positions, you'll see they exist for List, being defined as [B <: A] returning List[B], or receiving Any instead of A.
So it seems to me that, as written, Set might not be covariant, but that it CAN be written to be covariant without losing any methods. As far as the reasons you give are concerned, at least.

On Thu, Jul 23, 2009 at 8:08 AM, David MacIver <david [dot] maciver [at] gmail [dot] com> wrote:

--

Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

On Thu, Jul 23, 2009 at 8:08 AM, David MacIver <david [dot] maciver [at] gmail [dot] com> wrote:

2009/7/23 mustaghattack <biethb [at] gmail [dot] com>:

>

> In this

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

> post

> an answer says that Set are invariant in its type parameter because of the

> concept behind sets as functions.

>

> Then the author of the question asked what advantages does "a set as a

> function" has over a "set as a collection" ?

>

> I'm just wondering the same thing as I end up quite often using a List

> rather than a Set (in places where a Set would be more appropriate and more

> meaningful) because of the variance difference.

>

> Does anyone has an answer to that ?

It's less about "set as a function" and more about "set as thing which

has a contravariant method"

The problem is that the Set[T] has the method

def contains(t : T) : Boolean;

So a Set[String] should have the method

def contains(t : String) : Boolean;

while a Set[Any] should have the method

def contains(t : Any) : Boolean;

Set[String] doesn't have the method which takes an Any (and it

shouldn't, both for reasons of implementation and type safety), so it

can't possibly be a Set[Any].

> If this has to remain like that how would you work around this problem ?

It's a feature, not a problem. :-) If you have a Set[S] and want to

use it covariantly you're free to treat it as an Iterable[T] for any T

>: S, just not a Set[T].

--

Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

Thu, 2009-07-23, 18:27

#9
Re: Why Set aren't covariant

On Thu, Jul 23, 2009 at 6:08 PM, Daniel Sobral wrote:

> So it seems to me that, as written, Set might not be covariant, but that it

> CAN be written to be covariant without losing any methods. As far as the

> reasons you give are concerned, at least.

As illustrated here,

http://www.scala-lang.org/node/129

Cheers,

Miles

Fri, 2009-07-24, 03:17

#10
Re: Why Set aren't covariant

Is T |-> Set[T] a covariant functor? Looks like it is. for S <: T, an instance of Set[S] is perceivably also an instance of Set[T].But actually it is not. The signature Set[S] x S -> Boolean requires Set[S] to be contravariant.

2009/7/23 mustaghattack <biethb [at] gmail [dot] com>

--

Thanks,

-Vlad

2009/7/23 mustaghattack <biethb [at] gmail [dot] com>

In this

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

post

an answer says that Set are invariant in its type parameter because of the

concept behind sets as functions.

Then the author of the question asked what advantages does "a set as a

function" has over a "set as a collection" ?

I'm just wondering the same thing as I end up quite often using a List

rather than a Set (in places where a Set would be more appropriate and more

meaningful) because of the variance difference.

Does anyone has an answer to that ?

If this has to remain like that how would you work around this problem ?

--

View this message in context: http://www.nabble.com/Why-Set-aren%27t-covariant-tp24623221p24623221.html

Sent from the Scala - User mailing list archive at Nabble.com.

--

Thanks,

-Vlad

Fri, 2009-07-24, 14:27

#11
Re: Why Set aren't covariant

On 23/07/2009, Daniel Sobral wrote:

> List has a method contains as well, and it is covariant. List's contains

> receives Any, while Set's contains receives "A", the type parameter for

> Set.

> If you go through other methods on Set with elements in contravariant

> positions, you'll see they exist for List, being defined as [B <: A]

> returning List[B], or receiving Any instead of A.

>

> So it seems to me that, as written, Set might not be covariant, but that it

> CAN be written to be covariant without losing any methods. As far as the

> reasons you give are concerned, at least.

>

It can, as long as you don't mind giving up on type safety and/or the

abiity to provide implementations.

Fri, 2009-07-24, 14:37

#12
Re: Why Set aren't covariant

On Fri, Jul 24, 2009 at 3:20 AM, Miles Sabin wrote:

> On Thu, Jul 23, 2009 at 6:08 PM, Daniel Sobral wrote:

>> So it seems to me that, as written, Set might not be covariant, but that it

>> CAN be written to be covariant without losing any methods. As far as the

>> reasons you give are concerned, at least.

>

> As illustrated here,

>

> http://www.scala-lang.org/node/129

>

Thats a cool technique. Taught me something new.

But a slightly different situation: Stack.push() is a mutator, so

pushing an Int onto a Stack[String] must change the Stack's type to

maintain logical consistency.

While Set.contains() is a query. And I can answer, "no, sorry this

Set[Int] doesnt contain a String" while remaining a Set[Int].

Thus, IMO, the argument that Set should not be covariant puts

mechanisms ("that's how Scala's variance rules work") before meaning

("that's how Sets work"). And it doesn't line up my direct experience:

IMO a Set of Circles /is/ a Set of Shapes.

I think I prefer Set.contains(Any) and covariance over the present arrangement.

-Ben

Fri, 2009-07-24, 15:27

#13
Re: Why Set aren't covariant

Thanks a lot for your answers.

I think what I missed is the fact that a function is contravariant in its

parameter type and covariant in its result type. I initially though that it

was possible to declare a class parameter type as covariant and have

"normal" method (without variance annotation) like :

trait Set[+A] {

def contains( elem : A ) : Boolean

}

David McIver has illustrated the problem in a previous answer.

So I guess we're left with the following solutions :

1) Any as the parameter's type:

def contains( elem : Any ) : Boolean

2) A lower bound :

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

3) A function like List :

def exists( f : A => Boolean ) : Boolean

If I understand, the compiler algorithm that checks variance validates it

due to the fact that the contravariant position of f parameter is "flipped"

twice ... not quite sure about that though.

My point was that even if we adopt one of these solution, a Set defined as a

Function1 cannot be covariant in its type parameter since it is in a

contravariant position with Function1.

Moreover, like Ben just wrote :

Ben Hutchison wrote:

>

> The argument that Set should not be covariant puts mechanisms ("that's how

> Scala's variance rules work") before meaning ("that's how Sets work"). And

> it doesn't line up my direct experience:

> IMO a Set of Circles /is/ a Set of Shapes.

>

That's exactly my feeling too. Glad to not be the only one :)

Now I suppose there must be reasons/advantages to have Set defined this way.

David said because of :

- type safety

- ability to define implementation

* Type safety

If we choose to replace contains by the 3rd option (exists) as defined

above, do we miss an important feature ?

* Ability to define implementation

A Seq has many implementations (List, Queue, Stack ...) that are covariant.

Why can't we define a Set as a covariant interface with multiple

implementations ?

Thanks,

Bruno

Fri, 2009-07-24, 15:47

#14
Re: Why Set aren't covariant

On Fri, Jul 24, 2009 at 8:14 AM, mustaghattack wrote:

>

> Thanks a lot for your answers.

>

> * Type safety

> If we choose to replace contains by the 3rd option (exists) as defined

> above, do we miss an important feature ?

Efficiency of access. If Set is implemented atop a hashtable,

contains(A) can be implemented to run in O(1) time; exists(A =>

Boolean) is O(n)

Kris

Fri, 2009-07-24, 20:27

#15
Re: Why Set aren't covariant

Actually, Set[T] is inherently contravariant. It is, toposophically, x |-> Ω^x. It is made contravariant artificially, by misinterpreting image morphism. I'll write about it in details later on. Will take some time.

2009/7/24 Kris Nuttycombe <kris [dot] nuttycombe [at] gmail [dot] com>

--

Thanks,

-Vlad

2009/7/24 Kris Nuttycombe <kris [dot] nuttycombe [at] gmail [dot] com>

On Fri, Jul 24, 2009 at 8:14 AM, mustaghattack<biethb [at] gmail [dot] com> wrote:

>

> Thanks a lot for your answers.

>

> * Type safety

> If we choose to replace contains by the 3rd option (exists) as defined

> above, do we miss an important feature ?

Efficiency of access. If Set is implemented atop a hashtable,

contains(A) can be implemented to run in O(1) time; exists(A =>

Boolean) is O(n)

Kris

--

Thanks,

-Vlad

Fri, 2009-07-24, 20:37

#16
Re: Why Set aren't covariant

2009/7/24 mustaghattack :

> * Ability to define implementation

> A Seq has many implementations (List, Queue, Stack ...) that are covariant.

> Why can't we define a Set as a covariant interface with multiple

> implementations ?

It gets in the way of at least one (and probably more) common approach

to defining sets: Ordered sets.

The problem is that ordered sets take an Ordering[T], not an

Ordering[Any], so you've got no way of determining whether it's

appropriate to compare a given Any (in principle you could test it is

of type T, but this runs into a bunch of issues mostly centered around

erasure) wih the elements of the set. You'd have the same problem if

you wanted a HashSet to be parameterisable with a custom equality

implementation

Sat, 2009-07-25, 08:47

#17
Re: Why Set aren't covariant

On Sat, Jul 25, 2009 at 5:21 AM, David MacIver wrote:

> 2009/7/24 mustaghattack :

>> * Ability to define implementation

>> A Seq has many implementations (List, Queue, Stack ...) that are covariant.

>> Why can't we define a Set as a covariant interface with multiple

>> implementations ?

>

> It gets in the way of at least one (and probably more) common approach

> to defining sets: Ordered sets.

>

> The problem is that ordered sets take an Ordering[T], not an

> Ordering[Any], so you've got no way of determining whether it's

> appropriate to compare a given Any (in principle you could test it is

> of type T, but this runs into a bunch of issues mostly centered around

> erasure)

Ouch. You make a good point re: Erasure

At runtime, due to erasure a Set[T] has no idea what T is. So if we

ask the set, do you contain some object:Any, it is unable to ascertain

whether the object is a T. Thus any function defined in terms of T,

such as an Ordering[T], cannot be safely employed to implement

contains().

I cant see any way forward without getting unerased generics (ie type

members) involved. Again, we find mechanism obstructing meaning.

So one answer to the original question "Why aren't Sets convariant"

might be "because Scala isnt expressive enough to represent them".

Erasure is a consistently leaky abstraction, and a reliance on it is

one of Scala's weak points.

-Ben

Sat, 2009-07-25, 14:07

#18
Re: Why Set aren't covariant

2009/7/25 Ben Hutchison :

> So one answer to the original question "Why aren't Sets convariant"

> might be "because Scala isnt expressive enough to represent them".

A better answer would be "Because they're inherently not covariant and

Scala isn't expressive enough to implement the hack that works around

this"

Sat, 2009-07-25, 16:17

#19
Re: Why Set aren't covariant

On Sat, Jul 25, 2009 at 11:03 PM, David MacIver wrote:

> 2009/7/25 Ben Hutchison :

>> So one answer to the original question "Why aren't Sets convariant"

>> might be "because Scala isnt expressive enough to represent them".

>

> A better answer would be "Because they're inherently not covariant

The word "inherent" is no substitute for a reasoned argument based on

"something", ideally some axioms on which we agree.

To me, it seems so natural that everyday sets we encounter are

covariant that it feels strange to claim otherwise.

Lets agree to accept that a Circle is a type of Shape.

We have one Circle. It is also one Shape. Agree so far?

Now, imagine we have a Set that contains the one Circle, and since we

agree a Circle is a Shape, one Shape. We agree we can view it as a Set

/of/ Circles. Why is there a difficulty viewing it as a Set /of/

Shapes?

-Ben

Sat, 2009-07-25, 16:27

#20
Re: Why Set aren't covariant

On 25 Jul 2009, at 17:00, Ben Hutchison wrote:

> On Sat, Jul 25, 2009 at 11:03 PM, David MacIver > wrote:

>> 2009/7/25 Ben Hutchison :

>>> So one answer to the original question "Why aren't Sets convariant"

>>> might be "because Scala isnt expressive enough to represent them".

>>

>> A better answer would be "Because they're inherently not covariant

>

> The word "inherent" is no substitute for a reasoned argument based on

> "something", ideally some axioms on which we agree.

>

> To me, it seems so natural that everyday sets we encounter are

> covariant that it feels strange to claim otherwise.

>

> Lets agree to accept that a Circle is a type of Shape.

>

> We have one Circle. It is also one Shape. Agree so far?

>

> Now, imagine we have a Set that contains the one Circle, and since we

> agree a Circle is a Shape, one Shape. We agree we can view it as a Set

> /of/ Circles. Why is there a difficulty viewing it as a Set /of/

> Shapes?

>

Imagine you have some working procedure for a set of circles, which

hinges on the fact that they have rotational symmetry. This procedure

is built into the set, e.g. to find out if a given circle is already

in the set. Now you view this set as a set of shapes and pass some

arbitrary shape into that algorithm. Big Badaboom.

In other words: your proposed set would not have this algorithm/

method. You could make a covariant set, but it would not have all the

features of a current Scala Set. And the problem is not specific to

the Scala language as far as I can see.

Ciao,

Roland

Sat, 2009-07-25, 16:37

#21
Re: Why Set aren't covariant

On Saturday July 25 2009, Ben Hutchison wrote:

> On Sat, Jul 25, 2009 at 11:03 PM, David

MacIver wrote:

> > 2009/7/25 Ben Hutchison :

> >> So one answer to the original question "Why aren't Sets

> >> convariant" might be "because Scala isnt expressive enough to

> >> represent them".

> >

> > A better answer would be "Because they're inherently not covariant

>

> ...

>

> To me, it seems so natural that everyday sets we encounter are

> covariant that it feels strange to claim otherwise.

>

> ...

It sounds to me like you're confusing the dynamic behavior (Set[T] can

accept items that merely conform to T, not only those that _are_ T)

with the static relationship between two sets Set[T] and Set[U] when T

and U have a sub-type / super-type relationship between them.

> -Ben

Randall Schulz

Sat, 2009-07-25, 16:47

#22
Re: Why Set aren't covariant

Roland Kuhn-2 wrote:

>

> Imagine you have some working procedure for a set of circles, which

> hinges on the fact that they have rotational symmetry. This procedure

> is built into the set, e.g. to find out if a given circle is already

> in the set. Now you view this set as a set of shapes and pass some

> arbitrary shape into that algorithm. Big Badaboom.

>

Roland,

Sorry I miss your point. How do you relate the contains method to the

procedure for a set of circles ?

Could you give a code example ?

Thanks, BRuno

Sat, 2009-07-25, 16:57

#23
Re: Why Set aren't covariant

This seems like a strawman argument, or I miss something that a code

example might clarify. Why the algorithm couldn't define the parameter

it accepts as Circle, if it only works for circles?

It seems to me that, for immutable sets, if:

- methods like +, ++, incl, union accept B >: A instead of A (not Any,

to return Set[B])

- methods like -, --, excl, intersect, contains accept Any instead of A

then Set could be covariant. I haven't really been convinced by the

arguments to the contrary. I think the main issue is really about

"contains" accepting Any, which would allow some invocations that now

would be compile-time errors, and these could only return false.

2009/7/25 Roland Kuhn :

> On 25 Jul 2009, at 17:00, Ben Hutchison wrote:

>>

>> On Sat, Jul 25, 2009 at 11:03 PM, David MacIver

>> wrote:

>>>

>>> 2009/7/25 Ben Hutchison :

>>>>

>>>> So one answer to the original question "Why aren't Sets convariant"

>>>> might be "because Scala isnt expressive enough to represent them".

>>>

>>> A better answer would be "Because they're inherently not covariant

>>

>> The word "inherent" is no substitute for a reasoned argument based on

>> "something", ideally some axioms on which we agree.

>>

>> To me, it seems so natural that everyday sets we encounter are

>> covariant that it feels strange to claim otherwise.

>>

>> Lets agree to accept that a Circle is a type of Shape.

>>

>> We have one Circle. It is also one Shape. Agree so far?

>>

>> Now, imagine we have a Set that contains the one Circle, and since we

>> agree a Circle is a Shape, one Shape. We agree we can view it as a Set

>> /of/ Circles. Why is there a difficulty viewing it as a Set /of/

>> Shapes?

>>

> Imagine you have some working procedure for a set of circles, which hinges

> on the fact that they have rotational symmetry. This procedure is built into

> the set, e.g. to find out if a given circle is already in the set. Now you

> view this set as a set of shapes and pass some arbitrary shape into that

> algorithm. Big Badaboom.

>

> In other words: your proposed set would not have this algorithm/method. You

> could make a covariant set, but it would not have all the features of a

> current Scala Set. And the problem is not specific to the Scala language as

> far as I can see.

>

> Ciao,

>

> Roland

>

Sat, 2009-07-25, 17:07

#24
Re: Why Set aren't covariant

On 25 Jul 2009, at 17:47, Jim Andreou wrote:

> This seems like a strawman argument, or I miss something that a code

> example might clarify. Why the algorithm couldn't define the parameter

> it accepts as Circle, if it only works for circles?

>

> It seems to me that, for immutable sets, if:

> - methods like +, ++, incl, union accept B >: A instead of A (not Any,

> to return Set[B])

> - methods like -, --, excl, intersect, contains accept Any instead

> of A

>

> then Set could be covariant. I haven't really been convinced by the

> arguments to the contrary. I think the main issue is really about

> "contains" accepting Any, which would allow some invocations that now

> would be compile-time errors, and these could only return false.

>

That's correct AFAICS. However, if you make an OrderedSet which

accepts only type parameters T <: Ordered[T] (just making that up in

case it doesn't match current library), and the set would be

covariant, then some operation which uses the ordering (like

partition) could be passed some Any, which does not have any ordering!

This is the reason for the covariance/contravariance checking by the

compiler.

If you move compile-time checks (with strictly typed .contains) to

runtime (with "def contains(e:Any)") is a matter of taste, and I

suspect that the idea behind Scala tends to push the scales in the

former direction.

Ciao,

Roland

> 2009/7/25 Roland Kuhn :

>> On 25 Jul 2009, at 17:00, Ben Hutchison wrote:

>>>

>>> On Sat, Jul 25, 2009 at 11:03 PM, David MacIver>> >

>>> wrote:

>>>>

>>>> 2009/7/25 Ben Hutchison :

>>>>>

>>>>> So one answer to the original question "Why aren't Sets

>>>>> convariant"

>>>>> might be "because Scala isnt expressive enough to represent them".

>>>>

>>>> A better answer would be "Because they're inherently not covariant

>>>

>>> The word "inherent" is no substitute for a reasoned argument based

>>> on

>>> "something", ideally some axioms on which we agree.

>>>

>>> To me, it seems so natural that everyday sets we encounter are

>>> covariant that it feels strange to claim otherwise.

>>>

>>> Lets agree to accept that a Circle is a type of Shape.

>>>

>>> We have one Circle. It is also one Shape. Agree so far?

>>>

>>> Now, imagine we have a Set that contains the one Circle, and since

>>> we

>>> agree a Circle is a Shape, one Shape. We agree we can view it as a

>>> Set

>>> /of/ Circles. Why is there a difficulty viewing it as a Set /of/

>>> Shapes?

>>>

>> Imagine you have some working procedure for a set of circles, which

>> hinges

>> on the fact that they have rotational symmetry. This procedure is

>> built into

>> the set, e.g. to find out if a given circle is already in the set.

>> Now you

>> view this set as a set of shapes and pass some arbitrary shape into

>> that

>> algorithm. Big Badaboom.

>>

>> In other words: your proposed set would not have this algorithm/

>> method. You

>> could make a covariant set, but it would not have all the features

>> of a

>> current Scala Set. And the problem is not specific to the Scala

>> language as

>> far as I can see.

>>

>> Ciao,

>>

>> Roland

>>

Sat, 2009-07-25, 18:57

#25
Re: Why Set aren't covariant

I promise to write a big text regarding why Set[T] is contravariant, and how come we manage to find and use covariant features there.

2009/7/25 Ben Hutchison <ben [at] playscapegames [dot] com>

--

Thanks,

-Vlad

2009/7/25 Ben Hutchison <ben [at] playscapegames [dot] com>

On Sat, Jul 25, 2009 at 11:03 PM, David MacIver<david [dot] maciver [at] gmail [dot] com> wrote:

> 2009/7/25 Ben Hutchison <ben [at] playscapegames [dot] com>:

>> So one answer to the original question "Why aren't Sets convariant"

>> might be "because Scala isnt expressive enough to represent them".

>

> A better answer would be "Because they're inherently not covariant

The word "inherent" is no substitute for a reasoned argument based on

"something", ideally some axioms on which we agree.

To me, it seems so natural that everyday sets we encounter are

covariant that it feels strange to claim otherwise.

Lets agree to accept that a Circle is a type of Shape.

We have one Circle. It is also one Shape. Agree so far?

Now, imagine we have a Set that contains the one Circle, and since we

agree a Circle is a Shape, one Shape. We agree we can view it as a Set

/of/ Circles. Why is there a difficulty viewing it as a Set /of/

Shapes?

-Ben

--

Thanks,

-Vlad

Sat, 2009-07-25, 19:47

#26
Re: Why Set aren't covariant

Okay, here's why Set's aren't covariant.

In contains the type A is in contravariant position so the type of contains would have to change. Somebody suggested that it could be

def contains[B >: A](x : B) : Boolean

But that's silly because we aren't using the type B in the output so that's exactly identical to

def contains(x : Any) : Boolean.

Now, you can either like that or not from a "type safety" standpoint. It does mean some programs compile that might not but other collections work that way. Sometimes its irritating and sometimes its useful. Let's just assume that's not a show stopper and move on.

The real problem is that there are a couple of common ways to implement a Set. The first way is to use hashing, the second is to use ordering. Both ways involve equality checking. There are tradeoffs between using the two and for some applications one works better than the other while other applications reverse the relative merits.

Now the Java platform says everything can be hashed and compared for equality. That's dubious - does it really make sense to compare a Function to a String for equality? Or even to hash a Funciton in the first place. But that's the way it is so Sets based on hashing can work covariantly. I can hash an Any and then compare it to all the other objects that hashed the same in the Set to find if any are equal. No problem thanks to this Java-land hack.

But Sets based on ordering simply cannot be covariant. The above signature for contains wouldn't work. The Java-land hack does not any two arbitrary objects to be ordered. So there is simply no way to compare an Any to a String or a Function to decide which comes first in an ordered tree. Thus for the Set interface to allow this perfectly reasonable and useful implementation the Set interface must be invariant. That way we're always comparing A's to A's.

Hope this helps.

In contains the type A is in contravariant position so the type of contains would have to change. Somebody suggested that it could be

def contains[B >: A](x : B) : Boolean

But that's silly because we aren't using the type B in the output so that's exactly identical to

def contains(x : Any) : Boolean.

Now, you can either like that or not from a "type safety" standpoint. It does mean some programs compile that might not but other collections work that way. Sometimes its irritating and sometimes its useful. Let's just assume that's not a show stopper and move on.

The real problem is that there are a couple of common ways to implement a Set. The first way is to use hashing, the second is to use ordering. Both ways involve equality checking. There are tradeoffs between using the two and for some applications one works better than the other while other applications reverse the relative merits.

Now the Java platform says everything can be hashed and compared for equality. That's dubious - does it really make sense to compare a Function to a String for equality? Or even to hash a Funciton in the first place. But that's the way it is so Sets based on hashing can work covariantly. I can hash an Any and then compare it to all the other objects that hashed the same in the Set to find if any are equal. No problem thanks to this Java-land hack.

But Sets based on ordering simply cannot be covariant. The above signature for contains wouldn't work. The Java-land hack does not any two arbitrary objects to be ordered. So there is simply no way to compare an Any to a String or a Function to decide which comes first in an ordered tree. Thus for the Set interface to allow this perfectly reasonable and useful implementation the Set interface must be invariant. That way we're always comparing A's to A's.

Hope this helps.

Sat, 2009-07-25, 19:57

#27
Re: Why Set aren't covariant

James, Given a manifest type, couldn't a TreeSet first check the type of the parameter is receives on the contains method, and then return false if the parameter is not of the expected type? So it would skip the actual search if the runtime types don't match, and cast to the appropriate type before doing the search if they do match.

-Erik

On Sat, Jul 25, 2009 at 2:38 PM, James Iry <jamesiry [at] gmail [dot] com> wrote:

--

http://erikengbrecht.blogspot.com/

-Erik

On Sat, Jul 25, 2009 at 2:38 PM, James Iry <jamesiry [at] gmail [dot] com> wrote:

Okay, here's why Set's aren't covariant.

In contains the type A is in contravariant position so the type of contains would have to change. Somebody suggested that it could be

def contains[B >: A](x : B) : Boolean

But that's silly because we aren't using the type B in the output so that's exactly identical to

def contains(x : Any) : Boolean.

Now, you can either like that or not from a "type safety" standpoint. It does mean some programs compile that might not but other collections work that way. Sometimes its irritating and sometimes its useful. Let's just assume that's not a show stopper and move on.

The real problem is that there are a couple of common ways to implement a Set. The first way is to use hashing, the second is to use ordering. Both ways involve equality checking. There are tradeoffs between using the two and for some applications one works better than the other while other applications reverse the relative merits.

Now the Java platform says everything can be hashed and compared for equality. That's dubious - does it really make sense to compare a Function to a String for equality? Or even to hash a Funciton in the first place. But that's the way it is so Sets based on hashing can work covariantly. I can hash an Any and then compare it to all the other objects that hashed the same in the Set to find if any are equal. No problem thanks to this Java-land hack.

But Sets based on ordering simply cannot be covariant. The above signature for contains wouldn't work. The Java-land hack does not any two arbitrary objects to be ordered. So there is simply no way to compare an Any to a String or a Function to decide which comes first in an ordered tree. Thus for the Set interface to allow this perfectly reasonable and useful implementation the Set interface must be invariant. That way we're always comparing A's to A's.

Hope this helps.

--

http://erikengbrecht.blogspot.com/

Sat, 2009-07-25, 20:07

#28
Re: Why Set aren't covariant

On Sat, Jul 25, 2009 at 7:38 PM, James Iry wrote:

> Okay, here's why Set's aren't covariant.

>

> In contains the type A is in contravariant position so the type of contains

> would have to change. Somebody suggested that it could be

Right. But contains doesn't _have_ to have A in contravariant

position. It being that way was a design decision which could have

been made differently. It's a perfectly reasonable decision for it to

have been made the way it was, and I certainly don't want to argue

that it should have been done otherwise. But that doesn't make the

question that started this thread misconceived.

Cheers,

Miles

Sat, 2009-07-25, 20:27

#29
Re: Why Set aren't covariant

Hi Erik,

On 25 Jul 2009, at 20:47, Erik Engbrecht wrote:

> James,

> Given a manifest type, couldn't a TreeSet first check the type of

> the parameter is receives on the contains method, and then return

> false if the parameter is not of the expected type? So it would

> skip the actual search if the runtime types don't match, and cast to

> the appropriate type before doing the search if they do match.

>

This discussion keeps coming back to this question: why is the type

check not done at runtime? I'm by no means an authority here, but

reading the book Programming in Scala, I came to the conclusion that

in this language, static typing is strongly preferred over dynamic

typing. As the saying goes "A good programmer can write Fortran code

in any language", and the same might apply to the dynamic typing

paradigm...

Ciao,

Roland

Sat, 2009-07-25, 20:37

#30
Re: Why Set aren't covariant

Okay, another method: add

How do you implement add on a functional covariant TreeSet. The type would have to be

forall A <% Ordered[A], B >: A . TreeSet[A] -> B -> TreeSet[B]

Do you throw a runtime exception if you try to add anything other than an A?

On Sat, Jul 25, 2009 at 11:47 AM, Erik Engbrecht <erik [dot] engbrecht [at] gmail [dot] com> wrote:

How do you implement add on a functional covariant TreeSet. The type would have to be

forall A <% Ordered[A], B >: A . TreeSet[A] -> B -> TreeSet[B]

Do you throw a runtime exception if you try to add anything other than an A?

On Sat, Jul 25, 2009 at 11:47 AM, Erik Engbrecht <erik [dot] engbrecht [at] gmail [dot] com> wrote:

James, Given a manifest type, couldn't a TreeSet first check the type of the parameter is receives on the contains method, and then return false if the parameter is not of the expected type? So it would skip the actual search if the runtime types don't match, and cast to the appropriate type before doing the search if they do match.

-Erik

Sat, 2009-07-25, 20:57

#31
Re: Why Set aren't covariant

James, Yes, add is a better example. Thanks.

-Erik

On Sat, Jul 25, 2009 at 3:20 PM, James Iry <jamesiry [at] gmail [dot] com> wrote:

--

http://erikengbrecht.blogspot.com/

-Erik

On Sat, Jul 25, 2009 at 3:20 PM, James Iry <jamesiry [at] gmail [dot] com> wrote:

Okay, another method: add

How do you implement add on a functional covariant TreeSet. The type would have to be

forall A <% Ordered[A], B >: A . TreeSet[A] -> B -> TreeSet[B]

Do you throw a runtime exception if you try to add anything other than an A?

On Sat, Jul 25, 2009 at 11:47 AM, Erik Engbrecht <erik [dot] engbrecht [at] gmail [dot] com> wrote:James, Given a manifest type, couldn't a TreeSet first check the type of the parameter is receives on the contains method, and then return false if the parameter is not of the expected type? So it would skip the actual search if the runtime types don't match, and cast to the appropriate type before doing the search if they do match.

-Erik

--

http://erikengbrecht.blogspot.com/

Sun, 2009-07-26, 01:17

#32
Re: Why Set aren't covariant

On Sat, Jul 25, 2009 at 9:18 PM, Roland Kuhn wrote:

> This discussion keeps coming back to this question: why is the type check

> not done at runtime?

I wouldn't call returning false based on the type "dynamic typing".

The program executes without error, and false is a perfectly sensible

value to return.

Isn't the source of this whole problem trying to merge the notion of a

collection with the notion of a predicate into the same thing?

Maybe what is called "Set" in Scala should simply be called something else.

Consider val N = Set[Nat] (the set of all naturals) and val R =

Set[Real] (the set of all reals)

What is N.size supposed to return? N subsetOf R? N.size < R.size?

Ideally they should return (some notion of infinity), true and true

respectively. I guess it will be hard to implement this given the

current definition of Set regardless of whether it is covariant or

contravariant.

BR,

John

Sun, 2009-07-26, 05:27

#33
Re: Why Set aren't covariant

On Sun, Jul 26, 2009 at 10:10 AM, John Nilsson wrote:

> Isn't the source of this whole problem trying to merge the notion of a

> collection with the notion of a predicate into the same thing?

This distinction resonates with me.

Scala's collection library, rooted in Traversable, is built on the

idea of a enumerable collection of values.

But another, seemingly more general but less powerful notion of

collection is based upon a membership test (ie a predicate), T ->

Boolean.

Its interesting that the covariant vs invariant clash occurs where we

support the two notions in one object, at Set.contains().

-Ben

Sun, 2009-07-26, 12:17

#34
Re: Why Set aren't covariant

On Sun, Jul 26, 2009 at 1:10 AM, John Nilsson wrote:

> Isn't the source of this whole problem trying to merge the notion of a

> collection with the notion of a predicate into the same thing?

I think that's the wrong way of looking at it.

This is simply a design decision. It could have been made differently.

But having been made it has consequences. It's only a problem if you

absolutely have to have covariant sets.

And conversely, there's no problem with covariant sets per se. You can

have them, but you have to write them yourself and they won't fit into

the main collection framework completely smoothly.

As ever, YMMV ...

Cheers,

Miles

Sun, 2009-07-26, 14:17

#35
Re: Why Set aren't covariant

On Saturday July 25 2009, Ben Hutchison wrote:

> On Sun, Jul 26, 2009 at 10:10 AM, John Nilsson wrote:

> > Isn't the source of this whole problem trying to merge the notion

> > of a collection with the notion of a predicate into the same thing?

>

> This distinction resonates with me.

>

> Scala's collection library, rooted in Traversable, is built on the

> idea of a enumerable collection of values.

This is the extensional definition of a set: A set defined by

enumerating its elements.

> But another, seemingly more general but less powerful notion of

> collection is based upon a membership test (ie a predicate), T ->

> Boolean.

This is the intensional definition of a set: A set defined by a

description of its elements.

Sets drawn from, say, the real numbers can (usually) only be represented

intensionally, since a fundamental aspect of their nature is their

nonenumerability. Certain subsets of the reals can be enumerated,

though not necessarily finitely, (the integers and the rationals,

e.g.). But those subsets clearly don't get at the essence of the real

numbers and most interesting truths about the reals thereof preclude an

extensional representation.

Intensionally defined and extensionally defined sets support the same

mathematics, though computationally they can be quite different, for

obvious reasons.

But I find it it odd to think that something more general could be less

powerful.

> Its interesting that the covariant vs invariant clash occurs where we

> support the two notions in one object, at Set.contains().

Perhaps, but every formal definition of set includes an "is element of"

test. You can scarcely do any set theory without it and it is

ubiquitous in the definition of algorithms involving sets. The essence

of "set-ness" is the dividing line it draws between things in the set

and things not in the set. Anything that purports to have set-like

characteristics must provide a membership test.

> -Ben

Randall Schulz

Sun, 2009-07-26, 22:07

#36
Re: Why Set aren't covariant

One of the problems with covariant set is that map won't work covariantly.

2009/7/26 Miles Sabin <miles [at] milessabin [dot] com>

--

Thanks,

-Vlad

2009/7/26 Miles Sabin <miles [at] milessabin [dot] com>

On Sun, Jul 26, 2009 at 1:10 AM, John Nilsson<john [at] milsson [dot] nu> wrote:

> Isn't the source of this whole problem trying to merge the notion of a

> collection with the notion of a predicate into the same thing?

I think that's the wrong way of looking at it.

This is simply a design decision. It could have been made differently.

But having been made it has consequences. It's only a problem if you

absolutely have to have covariant sets.

And conversely, there's no problem with covariant sets per se. You can

have them, but you have to write them yourself and they won't fit into

the main collection framework completely smoothly.

As ever, YMMV ...

Cheers,

Miles

--

Miles Sabin

tel: +44 (0)7813 944 528

skype: milessabin

http://www.chuusai.com/

http://twitter.com/milessabin

--

Thanks,

-Vlad

Sun, 2009-07-26, 22:27

#37
Re: Why Set aren't covariant

On Sun, Jul 26, 2009 at 10:02 PM, Vlad Patryshev wrote:

> One of the problems with covariant set is that map won't work covariantly.

Really?

scala> trait Set[+A] { def map[B](f : A => B) : Set[B] }

defined trait Set

A is in covariant position in map.

Cheers,

Miles

Mon, 2009-07-27, 01:27

#38
Re: Why Set aren't covariant

On Sun, Jul 26, 2009 at 11:16 PM, Randall R Schulz wrote:

> On Saturday July 25 2009, Ben Hutchison wrote:

>> Scala's collection library, rooted in Traversable, is built on the

>> idea of a enumerable collection of values.

>

> This is the extensional definition of a set: A set defined by

> enumerating its elements

>

>> But another, seemingly more general but less powerful notion of

>> collection is based upon a membership test (ie a predicate), T ->

>> Boolean.

>

> This is the intensional definition of a set: A set defined by a

> description of its elements.

...

> Intensionally defined and extensionally defined sets support the same

> mathematics, though computationally they can be quite different, for

> obvious reasons.

Thanks for the useful explanation. If there are 2 representations of

the Set concept, that differ computationally, doesn't that suggest

they are best modeled via 3 types:

- a covariant SetContainer, being a collection without duplicates.

contains(Any) defined by enumerating its elements.

- a contravariant SetPredicate (membership test)

- the current invariant Set (collection plus membership test defined over T)

Then, when people want/ask-for Set covariance, there's something

(SetContainer) that addresses their needs.

>

> But I find it it odd to think that something more general could be less

> powerful.

>

Yes, I think "powerful" was the wrong word. "Expressive"?

-Ben

Tue, 2009-07-28, 01:07

#39
Re: Why Set aren't covariant

On Sat, Jul 25, 2009 at 5:40 PM, Ben Hutchison wrote:

> Erasure is a consistently leaky abstraction, and a reliance on it is

> one of Scala's weak points.

For completeness, I will mention that a friend Bernie Pope educated me

out of this viewpoint last night.

His argument is based upon results in Phillip Wadlers paper "Theorems

for Free" [http://homepages.inf.ed.ac.uk/wadler/topics/parametricity.html].

I haven't read the paper, but apparently several important & useful

theoretical properties of parametrized types depend the type parameter

(ie the T in Set[T]) being completely invisible/inaccessible at

runtime. One example cited was the composability of functions mapped

over the type.

Thus, erasure has the benefit that of ensuring Scala can inherit these results.

This viewpoint makes for an interesting contrast with the widely

expressed desired for reified parametric types in Java; its is

currently the 9th most voted RFE

[http://bugs.sun.com/bugdatabase/top25_rfes.do].

Clearly, many people do want to reflect over parametric types (or

think they do). Is this purely to improve interop with Java's arrays

(which are problematic because they have their component type baked

into them) or for other reasons?

-Ben

Tue, 2009-07-28, 21:47

#40
Re: Why Set aren't covariant

Personally I think that Arrays are an optimization of List and they should be invisible to the developer (especially since the array-impl in Java is less than stellar)

On Tue, Jul 28, 2009 at 2:00 AM, Ben Hutchison <ben [at] playscapegames [dot] com> wrote:

--

Viktor Klang

Rogue Scala-head

Blog: klangism.blogspot.com

Twttr: viktorklang

On Tue, Jul 28, 2009 at 2:00 AM, Ben Hutchison <ben [at] playscapegames [dot] com> wrote:

On Sat, Jul 25, 2009 at 5:40 PM, Ben Hutchison<ben [at] playscapegames [dot] com> wrote:

> Erasure is a consistently leaky abstraction, and a reliance on it is

> one of Scala's weak points.

For completeness, I will mention that a friend Bernie Pope educated me

out of this viewpoint last night.

His argument is based upon results in Phillip Wadlers paper "Theorems

for Free" [http://homepages.inf.ed.ac.uk/wadler/topics/parametricity.html].

I haven't read the paper, but apparently several important & useful

theoretical properties of parametrized types depend the type parameter

(ie the T in Set[T]) being completely invisible/inaccessible at

runtime. One example cited was the composability of functions mapped

over the type.

Thus, erasure has the benefit that of ensuring Scala can inherit these results.

This viewpoint makes for an interesting contrast with the widely

expressed desired for reified parametric types in Java; its is

currently the 9th most voted RFE

[http://bugs.sun.com/bugdatabase/top25_rfes.do].

Clearly, many people do want to reflect over parametric types (or

think they do). Is this purely to improve interop with Java's arrays

(which are problematic because they have their component type baked

into them) or for other reasons?

-Ben

--

Viktor Klang

Rogue Scala-head

Blog: klangism.blogspot.com

Twttr: viktorklang

Tue, 2009-07-28, 23:07

#41
Re: Why Set aren't covariant

Hmm... Thinking that that that compiles is right is wrong... but actually, right, Im(f): S ↦ {f(x)| x ∈ S} may be a good candidate, yes. Is it monadic?

2009/7/26 Miles Sabin <miles [at] milessabin [dot] com>

--

Thanks,

-Vlad

2009/7/26 Miles Sabin <miles [at] milessabin [dot] com>

On Sun, Jul 26, 2009 at 10:02 PM, Vlad Patryshev<vpatryshev [at] gmail [dot] com> wrote:

> One of the problems with covariant set is that map won't work covariantly.

Really?

scala> trait Set[+A] { def map[B](f : A => B) : Set[B] }

defined trait Set

A is in covariant position in map.

Cheers,

Miles

--

Miles Sabin

tel: +44 (0)7813 944 528

skype: milessabin

http://www.chuusai.com/

http://twitter.com/milessabin

--

Thanks,

-Vlad

Tue, 2009-07-28, 23:47

#42
Re: Why Set aren't covariant

On Tue, Jul 28, 2009 at 10:56 PM, Vlad Patryshev wrote:

> Hmm... Thinking that that that compiles is right is wrong...

No, it really isn't wrong ...

Cheers,

Miles

Tue, 2009-07-28, 23:57

#43
Re: Why Set aren't covariant

Vlad Patryshev wrote:

> One of the problems with covariant set is that map won't work covariantly.

>

Also

$ rlwrap scala -classpath ScalaCheck-1.5.jar

Welcome to Scala version 2.7.4.final (Java HotSpot(TM) 64-Bit Server VM,

Java 1.6.0_13).

Type in expressions to have them evaluated.

Type :help for more information.

scala> import org.scalacheck.Arbitrary._

import org.scalacheck.Arbitrary._

scala> import org.scalacheck.Prop.forAll

import org.scalacheck.Prop.forAll

scala> val p = forAll { (s: collection.Set[Int], f: Int => String, g:

Int => Int) => (s map g map f) == s.map(f compose g) }

p: org.scalacheck.Prop = Prop

scala> p.check

! Falsified after 0 passed tests.

> ARG_0: "Set()"

> ARG_1: ""

> ARG_2: ""

Wed, 2009-07-29, 00:27

#44
Re: Why Set aren't covariant

On Tue, Jul 28, 2009 at 11:52 PM, Tony Morris wrote:

> Also

No.

That just shows that Set as defined in the Scala standard library is

not covariant ... this is something that we knew already.

It doesn't show that there isn't a perfectly good, but different, set

abstraction which is covariant.

The whole point of this thread (as I understood the OPs initial

question) is to get a better understanding of why the design decisions

embodied in the Scala standard library were made the way that they

were. It is utterly redundant to simply restate what that decision

was.

Cheers,

Miles

Wed, 2009-07-29, 00:37

#45
Re: Why Set aren't covariant

Tony Morris wrote:

> Vlad Patryshev wrote:

>

>> One of the problems with covariant set is that map won't work covariantly.

>>

>>

>

> Also

>

> $ rlwrap scala -classpath ScalaCheck-1.5.jar

> Welcome to Scala version 2.7.4.final (Java HotSpot(TM) 64-Bit Server VM,

> Java 1.6.0_13).

> Type in expressions to have them evaluated.

> Type :help for more information.

>

> scala> import org.scalacheck.Arbitrary._

> import org.scalacheck.Arbitrary._

>

> scala> import org.scalacheck.Prop.forAll

> import org.scalacheck.Prop.forAll

>

> scala> val p = forAll { (s: collection.Set[Int], f: Int => String, g:

> Int => Int) => (s map g map f) == s.map(f compose g) }

> p: org.scalacheck.Prop = Prop

>

> scala> p.check

> ! Falsified after 0 passed tests.

>

>> ARG_0: "Set()"

>> ARG_1: ""

>> ARG_2: ""

>>

>

>

>

This shows that Set as defined by the Scala libraries violates the

functor law of composition and so is not map after all, but something

else with the wrong name. Set cannot have a well-behaved map function.

Wed, 2009-07-29, 00:47

#46
Re: Why Set aren't covariant

On Wed, Jul 29, 2009 at 12:28 AM, Tony Morris wrote:

> Tony Morris wrote:

>>> ARG_0: "Set()"

>>> ARG_1: ""

>>> ARG_2: ""

>>

> This shows that Set as defined by the Scala libraries violates the

> functor law of composition and so is not map after all, but something

> else with the wrong name. Set cannot have a well-behaved map function.

The witness values of ARG_1 and ARG_2 for that are what?

Cheers,

Miles

Wed, 2009-07-29, 01:27

#47
Re: Why Set aren't covariant

x ↦ 2x, f ↦ ∃f = (s => {f(x) | x∈s} actually is a functor, not only in Sets, but in any elementary topos (replace 2 with Ω).

2009/7/28 Miles Sabin <miles [at] milessabin [dot] com>

--

Thanks,

-Vlad

2009/7/28 Miles Sabin <miles [at] milessabin [dot] com>

On Wed, Jul 29, 2009 at 12:28 AM, Tony Morris<tonymorris [at] gmail [dot] com> wrote:

> Tony Morris wrote:

>>> ARG_0: "Set()"

>>> ARG_1: "<function>"

>>> ARG_2: "<function>"

>>

> This shows that Set as defined by the Scala libraries violates the

> functor law of composition and so is not map after all, but something

> else with the wrong name. Set cannot have a well-behaved map function.

The witness values of ARG_1 and ARG_2 for that are what?

Cheers,

Miles

--

Miles Sabin

tel: +44 (0)7813 944 528

skype: milessabin

http://www.chuusai.com/

http://twitter.com/milessabin

--

Thanks,

-Vlad

Wed, 2009-07-29, 02:57

#48
Re: Why Set aren't covariant

On Tue, Jul 28, 2009 at 3:52 PM, Tony Morris <tonymorris [at] gmail [dot] com> wrote:

There is something deeply wrong happening in this test. I can't put my finger on it but it seems some compiler optimizations come into play and substitute Set[Int] values for ArrayBufferRO() and ArrayBuffer() and the equality check fails.

Invoking toList on the resulting sets makes the test pass and shows that sets obey composition rules (when not subjected to compiler bugs)

scala> boisvert@sixtine:/$ scala -cp /home/boisvert/.m2/repository/org/scala-tools/testing/scalacheck/1.5/scalacheck-1.5.jar

Welcome to Scala version 2.7.4.final (Java HotSpot(TM) Server VM, Java 1.6.0_10).

Type in expressions to have them evaluated.

Type :help for more information.

scala> import org.scalacheck.Arbitrary._

import org.scalacheck.Arbitrary._

scala> import org.scalacheck.Prop.forAll

import org.scalacheck.Prop.forAll

scala> val p = forAll { ( s: collection.Set[Int], f: Int => String, g: Int => Int) =>

| (s map g map f).toList == s.map(f compose g).toList

| }

p: org.scalacheck.Prop = Prop

scala> p.check

+ OK, passed 100 tests.

alex

scala> val p = forAll { (s: collection.Set[Int], f: Int => String, g:

Int => Int) => (s map g map f) == s.map(f compose g) }

p: org.scalacheck.Prop = Prop

scala> p.check

! Falsified after 0 passed tests.

> ARG_0: "Set()"

> ARG_1: "<function>"

> ARG_2: "<function>"

There is something deeply wrong happening in this test. I can't put my finger on it but it seems some compiler optimizations come into play and substitute Set[Int] values for ArrayBufferRO() and ArrayBuffer() and the equality check fails.

Invoking toList on the resulting sets makes the test pass and shows that sets obey composition rules (when not subjected to compiler bugs)

scala> boisvert@sixtine:/$ scala -cp /home/boisvert/.m2/repository/org/scala-tools/testing/scalacheck/1.5/scalacheck-1.5.jar

Welcome to Scala version 2.7.4.final (Java HotSpot(TM) Server VM, Java 1.6.0_10).

Type in expressions to have them evaluated.

Type :help for more information.

scala> import org.scalacheck.Arbitrary._

import org.scalacheck.Arbitrary._

scala> import org.scalacheck.Prop.forAll

import org.scalacheck.Prop.forAll

scala> val p = forAll { ( s: collection.Set[Int], f: Int => String, g: Int => Int) =>

| (s map g map f).toList == s.map(f compose g).toList

| }

p: org.scalacheck.Prop = Prop

scala> p.check

+ OK, passed 100 tests.

alex

Wed, 2009-07-29, 19:07

#49
Re: Why Set aren't covariant

On Wed, Jul 29, 2009 at 12:52 AM, Tony Morris wrote:

> scala> val p = forAll { (s: collection.Set[Int], f: Int => String, g:

> Int => Int) => (s map g map f) == s.map(f compose g) }

Hmm, would it solve the problem if you require the argument to map to

be injective for sets?

BR,

John

Wed, 2009-07-29, 19:17

#50
Re: Why Set aren't covariant

On Wed, Jul 29, 2009 at 7:56 PM, John Nilsson wrote:

> On Wed, Jul 29, 2009 at 12:52 AM, Tony Morris wrote:

>> scala> val p = forAll { (s: collection.Set[Int], f: Int => String, g:

>> Int => Int) => (s map g map f) == s.map(f compose g) }

>

> Hmm, would it solve the problem if you require the argument to map to

> be injective for sets?

Never mind by the way. I'm just being stupid...

BR,

John

2009/7/23 mustaghattack :

>

> In this

> http://stackoverflow.com/questions/676615/why-is-scalas-immutable-set-no...

> post

> an answer says that Set are invariant in its type parameter because of the

> concept behind sets as functions.

>

> Then the author of the question asked what advantages does "a set as a

> function" has over a "set as a collection" ?

>

> I'm just wondering the same thing as I end up quite often using a List

> rather than a Set (in places where a Set would be more appropriate and more

> meaningful) because of the variance difference.

>

> Does anyone has an answer to that ?

It's less about "set as a function" and more about "set as thing which

has a contravariant method"

The problem is that the Set[T] has the method

def contains(t : T) : Boolean;

So a Set[String] should have the method

def contains(t : String) : Boolean;

while a Set[Any] should have the method

def contains(t : Any) : Boolean;

Set[String] doesn't have the method which takes an Any (and it

shouldn't, both for reasons of implementation and type safety), so it

can't possibly be a Set[Any].

> If this has to remain like that how would you work around this problem ?

It's a feature, not a problem. :-) If you have a Set[S] and want to

use it covariantly you're free to treat it as an Iterable[T] for any T

>: S, just not a Set[T].