# Why Set aren't covariant

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 ?

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

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

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

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

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

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.