Why Set aren't covariant

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

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

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@gmail.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@gmail.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.

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.

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

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

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.

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

2009/7/23 mustaghattack <biethb@gmail.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.

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

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@gmail.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

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.

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

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

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

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.nuttycombe@gmail.com>

On Fri, Jul 24, 2009 at 8:14 AM, mustaghattack<biethb@gmail.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

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

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

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"

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

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

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

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

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
>

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

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@playscapegames.com>

On Sat, Jul 25, 2009 at 11:03 PM, David MacIver<david.maciver@gmail.com> wrote:
> 2009/7/25 Ben Hutchison <ben@playscapegames.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

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.

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@gmail.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/

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

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

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.engbrecht@gmail.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

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

On Sat, Jul 25, 2009 at 3:20 PM, James Iry <jamesiry@gmail.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.engbrecht@gmail.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/

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

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

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

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

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

2009/7/26 Miles Sabin <miles@milessabin.com>

On Sun, Jul 26, 2009 at 1:10 AM, John Nilsson<john@milsson.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

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

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

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

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

On Sat, Jul 25, 2009 at 5:40 PM, Ben Hutchison<ben@playscapegames.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

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@milessabin.com>

On Sun, Jul 26, 2009 at 10:02 PM, Vlad Patryshev<vpatryshev@gmail.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

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

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: ""

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

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.

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

 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@milessabin.com>

On Wed, Jul 29, 2009 at 12:28 AM, Tony Morris<tonymorris@gmail.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

On Tue, Jul 28, 2009 at 3:52 PM, Tony Morris <tonymorris@gmail.com> 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) }
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

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

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