Covariant Sets?

560 views
Skip to first unread message

Haoyi Li

unread,
Oct 5, 2012, 11:58:20 AM10/5/12
to scala-user
I noticed that the immutable Set class is invariant, and ignoring whether or not that is a good idea, I often find myself wanting a covariant Set to put things in. Currently I am either:
  • Using Seqs where a Set would actually fit better (e.g. I don't care about order, and I want the each-item-only-once characteristics of a set, and I want) because I want the covariance
  • Casting things to the correct type every time before putting them into the invariant Sets
Neither of these seems like a good solution. I couldn't find any convenient covariant Set class floating around the standard library to use; is it feasible to make a wrapper around invariant Sets to do all the casting for me, or is there a better solution? 

-Haoyi

Vlad Patryshev

unread,
Oct 5, 2012, 12:17:33 PM10/5/12
to Haoyi Li, scala-user
A tricky issue. A while ago I tried to get arguments that a Set is contravariant. Seems like we have a pretty vague definition of sets: they are supposed to be enumerable; and enumeration requires covariance. There's an article that might address the issue, I believe:


www-lmpa.univ-littoral.fr/~stubbe/PDF/CatDistFunTAC.pdf

But it's big; I'm reading it.

Generally speaking, Set is not a Seq at all.

Thanks,
-Vlad

Haoyi Li

unread,
Oct 5, 2012, 1:04:29 PM10/5/12
to Vlad Patryshev, scala-user
Yeah, a Set is not a Seq. That's why I find it awkward to keep using Seqs when i really want Sets, because they really aren't the same thing. 

As I understand, it boils down to Sets as:
  1. Function1[A, Boolean], in which case it should be contravariant
  2. "bunch of stuff with no dupes, with no particular order", in which case it should be covariant
I don't think I'm the only one who very often finds myself needing the 2nd use case. My experience is that "bunches of stuff" are as-often unordered as they are ordered, and in the unordered case both Set and Seq feel very awkward to use. Nonetheless I find myself passing around Lists and Seqs of objects when I really want to be passing around Sets, simply because they're covariant and covariance is nice to have, O(n) set operations be damned. It just doesn't seem like a good solution.

-Haoyi

Vlad Patryshev

unread,
Oct 5, 2012, 1:15:40 PM10/5/12
to Haoyi Li, scala-user
Right; and there must be some deep cause for this; knowing the cause may bring the right solution to the puzzle.

Thanks,
-Vlad

HamsterofDeath

unread,
Oct 5, 2012, 1:25:48 PM10/5/12
to scala...@googlegroups.com
this is one of the big mysteries, just like "why does java.util.Map.get" accept objects as keys even though there is a type parameter for keys?

Juha Heljoranta

unread,
Oct 5, 2012, 1:30:29 PM10/5/12
to scala...@googlegroups.com
On Friday, October 05, 2012 10:15:40 Vlad Patryshev wrote:
> Right; and there must be some deep cause for this; knowing the cause may
> bring the right solution to the puzzle.

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


nicola...@gmail.com

unread,
Oct 5, 2012, 1:42:39 PM10/5/12
to Haoyi Li, Vlad Patryshev, scala-user
> Function1[A, Boolean], in which case it should be contravariant
> "bunch of stuff with no dupes, with no particular order", in which case it
> should be covariant
>
You can see them as Function1[Any,Boolean], which solves that part of
the problem.
Anything not of type A is not a member.

Rüdiger Klaehn

unread,
Oct 5, 2012, 3:29:18 PM10/5/12
to Haoyi Li, Vlad Patryshev, scala-user
I was convinced in a recent discussion that sets should not be
covariant by default:
https://groups.google.com/forum/#!topic/scala-language/WqJR38REXnk

I managed to remove the need for covariant sets in my code, so the
need is no longer as pressing for me. But it would be nice if you
could have a covariant set for the cases where it is useful.

Sometimes when you can't make something covariant because of one or
two methods, it is a good idea to split the interface into a covariant
and a contravariant/invariant part. Maybe something like this could be
done with Set. The only methods that prevent Set from being covariant
are apply and contains (which is just an alias for apply).

trait CovariantSet[T] {
.. the usual collection stuff

def containsAny(x:Any) : Boolean // covariant contains method
}

trait Set extends Set[T] with Function1[T,Boolean] {
def contains(x:T) = apply(x:T)

Raoul Duke

unread,
Oct 5, 2012, 7:10:39 PM10/5/12
to scala...@googlegroups.com
On Fri, Oct 5, 2012 at 12:29 PM, Rüdiger Klaehn <rkl...@gmail.com> wrote:
> Sometimes when you can't make something covariant because of one or
> two methods, it is a good idea to split the interface into a covariant
> and a contravariant/invariant part. Maybe something like this could be
> done with Set. The only methods that prevent Set from being covariant
> are apply and contains (which is just an alias for apply).

hm, interesting point.

Haoyi Li

unread,
Oct 5, 2012, 7:40:33 PM10/5/12
to Raoul Duke, scala...@googlegroups.com
I guess this kind of ties back into my original question: Assuming the current invariant set is not going anywhere, would anyone else find having a covariant set (CovSet? CoSet? CSet?) in the standard library useful? Would it be nice to have in some places where you currently use Seqs or invariant Sets? I thought it made a lot of sense for such a thing to exist, but if nobody else would find it useful I guess I'm the anomaly.

Daniel Sobral

unread,
Oct 5, 2012, 11:30:28 PM10/5/12
to Vlad Patryshev, Haoyi Li, scala-user
On Fri, Oct 5, 2012 at 2:15 PM, Vlad Patryshev <vpatr...@gmail.com> wrote:
> Right; and there must be some deep cause for this; knowing the cause may
> bring the right solution to the puzzle.

Very shallow cause: sets are invariant to make it's contains method type-safe.
--
Daniel C. Sobral

I travel to the future all the time.

Vlad Patryshev

unread,
Oct 6, 2012, 1:17:34 AM10/6/12
to Daniel Sobral, Haoyi Li, scala-user
I was always wondering, is List safe? It has some kind of contains() method... :)

Would be great if someone could put it all clearly and explicitly, like, see, Cardelli had demonstrated that Liskov principle is self-contradictory... something like that.

Daniel Sobral

unread,
Oct 6, 2012, 1:39:02 AM10/6/12
to Vlad Patryshev, Haoyi Li, scala-user
On Sat, Oct 6, 2012 at 2:17 AM, Vlad Patryshev <vpatr...@gmail.com> wrote:
> I was always wondering, is List safe? It has some kind of contains()
> method... :)

Try List(1,2,3).contains(true) and see.

Jeff Olson

unread,
Oct 6, 2012, 7:09:47 PM10/6/12
to scala...@googlegroups.com, Vlad Patryshev, Haoyi Li


On Friday, October 5, 2012 10:30:53 PM UTC-5, Daniel Sobral wrote:
On Fri, Oct 5, 2012 at 2:15 PM, Vlad Patryshev <vpatr...@gmail.com> wrote:
> Right; and there must be some deep cause for this; knowing the cause may
> bring the right solution to the puzzle.

Very shallow cause: sets are invariant to make it's contains method type-safe.


I think that's a little backwards. I would say the contains method is written the way it is because someone choose (badly, IMHO) to make sets invariant. There is nothing in the interface of an (immutable) Set that prevents it from being covariant. However, some modifications need to be made. Mainly Set[+A] should extend (Any => Boolean) rather than (A => Boolean) and the signature of contains needs be modified accordingly.

I haven't tried writing a complete implementation but I have no doubt that it could be done. Here is a very minimal (very naive) implementation:

https://gist.github.com/3846435

Immutable sets should be covariant. End of story. Maybe I'll write an implementation and try to get it into 2.11.

(On the other hand: immutable _sorted_ sets cannot be made covariant. Exercise for the reader).

Daniel Sobral

unread,
Oct 7, 2012, 12:05:59 AM10/7/12
to Jeff Olson, scala...@googlegroups.com, Vlad Patryshev, Haoyi Li
On Sat, Oct 6, 2012 at 8:09 PM, Jeff Olson <jeff.d...@gmail.com> wrote:
>
>
> On Friday, October 5, 2012 10:30:53 PM UTC-5, Daniel Sobral wrote:
>>
>> On Fri, Oct 5, 2012 at 2:15 PM, Vlad Patryshev <vpatr...@gmail.com> wrote:
>> > Right; and there must be some deep cause for this; knowing the cause may
>> > bring the right solution to the puzzle.
>>
>> Very shallow cause: sets are invariant to make it's contains method
>> type-safe.
>>
>
> I think that's a little backwards. I would say the contains method is
> written the way it is because someone choose (badly, IMHO) to make sets
> invariant. There is nothing in the interface of an (immutable) Set that

Think what you will, but that is the cause, and I'd go further and say
it's the right decision.

> prevents it from being covariant. However, some modifications need to be
> made. Mainly Set[+A] should extend (Any => Boolean) rather than (A =>
> Boolean) and the signature of contains needs be modified accordingly.

Which would lose all type safety.

There are two kinds of people in the world: those that thing
Set(1,2,3).contains(true) should be a compile time error, and those
that should stay away from statically typed languages.

> I haven't tried writing a complete implementation but I have no doubt that
> it could be done. Here is a very minimal (very naive) implementation:
>
> https://gist.github.com/3846435
>
> Immutable sets should be covariant. End of story. Maybe I'll write an
> implementation and try to get it into 2.11.

Yeah, right, whatever. You can count on my vote against any such change.

>
> (On the other hand: immutable _sorted_ sets cannot be made covariant.
> Exercise for the reader).
>



Vlad Patryshev

unread,
Oct 7, 2012, 12:06:43 AM10/7/12
to Jeff Olson, scala...@googlegroups.com, Haoyi Li

I don't even know what is "_sorted_ set". Do you mean a linear order? Any additional properties? (If one believes in AC, every set can be linearly ordered).


Jeff Olson

unread,
Oct 7, 2012, 1:29:59 AM10/7/12
to scala...@googlegroups.com, Jeff Olson, Vlad Patryshev, Haoyi Li


On Saturday, October 6, 2012 11:06:23 PM UTC-5, Daniel Sobral wrote:
On Sat, Oct 6, 2012 at 8:09 PM, Jeff Olson <jeff.d...@gmail.com> wrote:
>
>
> On Friday, October 5, 2012 10:30:53 PM UTC-5, Daniel Sobral wrote:
>>
>> On Fri, Oct 5, 2012 at 2:15 PM, Vlad Patryshev <vpatr...@gmail.com> wrote:
>> > Right; and there must be some deep cause for this; knowing the cause may
>> > bring the right solution to the puzzle.
>>
>> Very shallow cause: sets are invariant to make it's contains method
>> type-safe.
>>
>
> I think that's a little backwards. I would say the contains method is
> written the way it is because someone choose (badly, IMHO) to make sets
> invariant. There is nothing in the interface of an (immutable) Set that

Think what you will, but that is the cause, and I'd go further and say
it's the right decision.

> prevents it from being covariant. However, some modifications need to be
> made. Mainly Set[+A] should extend (Any => Boolean) rather than (A =>
> Boolean) and the signature of contains needs be modified accordingly.

Which would lose all type safety.

There are two kinds of people in the world: those that thing
Set(1,2,3).contains(true) should be a compile time error, and those
that should stay away from statically typed languages.


That's a rather odd position. So your opinion is that Lists should not be covariant? Or that they shouldn't have a contains method? Or that covariance and type safety are fundamentally at odds with one another and that anyone who wants type safety should abandoned covariance? In which case I think Scala is not the language for you.

Clearly anyone who wants a covariant Set class thinks that Set(1,2,3).contains(true) is a sensible expression (after all, a Set[Int] is a Set[Any]). So your argument is fundamentally begging the question.

Jeff Olson

unread,
Oct 7, 2012, 1:32:32 AM10/7/12
to scala...@googlegroups.com, Jeff Olson, Haoyi Li


On Saturday, October 6, 2012 11:06:47 PM UTC-5, Vlad Patryshev wrote:

I don't even know what is "_sorted_ set". Do you mean a linear order? Any additional properties? (If one believes in AC, every set can be linearly ordered).



I mean a scala.collection.immutable.SortedSet[A]

Which can't be covariant because of the Ordering[A] (which is naturally contravariant--although its actually invariant in scala for a technical reason involving implicit search).

HamsterofDeath

unread,
Oct 7, 2012, 2:44:18 AM10/7/12
to scala...@googlegroups.com
opinion:
Set(1,2,3) .contains(true) should not compile, booleans do not extend numbers
Set(1,2,3).contains(somethingOfTypeAnyWhichHappensToBeABooleanAtRuntime) should return false

problems solved:
* those who use unspecific types get bitten as they deserve
* those who want sets to be covariant get what they want
* sets are still type safe enough

it shouldn't be difficult to write a simple wrapper class around sets which are covariant, so everyone is free to do it.

Jan Vanek

unread,
Oct 7, 2012, 9:35:56 AM10/7/12
to scala...@googlegroups.com
It would be nice to have the Set covariant and at the same time the contains() "type-safe". The Set(1,2,3).contains(true) should be compile-time failure. But it should be possible to do val s: Set[Any] = Set(1,2,3); s.contains(true)

If Set[+T] is covariant the compiler complains that the covariant type is used in contra-variant position (in contains), but it is too strict. The contains() doesn't mutate the set (regardless of whether the set is mutable or immutable), and it follows from the semantics of contains(), that this particular usage is fine. Compiler can't know, sometimes, if such a method is abstract, he doesn't even have a code to attempt to, and even if it has the code, it might be impossible to verify that the parameter is used correctly. So we could tell him, that we know it, e.g. like:

trait Set[+T] {
  def contains(x: ~T): Boolean
}

With ~T we say this usage/position is "flexible" with regard to sub-typing. We override the "too strict" thinking of the compiler that the position is contra-variant. Similarly with Ordering, we could have:

trait Ordering[-T] extends Serializable {
  def compare(x: T, y: T): Int
   
  def lteq(x: T, y: T): Boolean = compare(x, y) <= 0
   
  def gteq(x: T, y: T): Boolean = compare(x, y) >= 0

  def max(x: T, y: T): ~T = if (gteq(x, y)) x else y
 
  def min(x: T, y: T): ~T = if (lteq(x, y)) x else y
}

If we have Ordering[Any] and pass/use it as Ordering[Int], the min/max return value is still fine.

I don't have clarity of mind about it at the moment, so the right words are not found. Anyway, I'd not be surprised if something like this has already been discussed, and possibly even refuted. What do you think?

Regards,
Jan

Jeff Olson

unread,
Oct 7, 2012, 10:06:15 AM10/7/12
to scala...@googlegroups.com

Let's be absolutely clear about this:

If Sets are covariant then, by the Liskov substitution principle, Set(1,2,3).contains(false) _must_ compile (without warning).

This is not a bad thing. It's working as intended. A Set[Int] is a Set[Any] (since an Int is an Any) and by the LSP we should be able to substitute a Set[Int] for a Set[Any] in any expression without modification.

If you think I'm off my rocker try

    Seq(1,2,3).contains(false)

or

    List(1,2,3).contains(false)

Do you see any warnings?

There are two consistent positions one can take here. Either Seqs and Sets should both be covariant, or neither of them should be (and we should just do anyway with variance altogether). There is absolutely no fundamental difference between Seqs and Sets that allows one to be covariant but not the other. The library is internally inconsistent at present and should be fixed.

If you think I'm wrong, please explain why List(1,2,3).contains(false) is perfectly valid but Set(1,2,3).contains(false) is an atrocity.

-Jeff

Jan Vanek

unread,
Oct 7, 2012, 10:24:52 AM10/7/12
to scala...@googlegroups.com
On 07.10.2012 16:06, Jeff Olson wrote:
>
> Let's be absolutely clear about this:
>
> If Sets are covariant then, by the Liskov substitution principle,
> Set(1,2,3).contains(false) _must_ compile (without warning).
>

I don't think it is clear. I'd expect that from LSP comes
Set(1,2,3).asInstanceOf[Set[Any]].contains(false) _must_ compile.

> This is not a bad thing. It's working as intended. A Set[Int] is a
> Set[Any] (since an Int is an Any) and by the LSP we should be able to
> substitute a Set[Int] for a Set[Any] in any expression without
> modification.
>

Yes, I agree. But in Set(1,2,3).contains(false) there is no
substitution. In cf(Set(1,2,3)), where
def cf(s: Set[Any]) = s.contains(false)
there is a substitution and should work without warning.

> If you think I'm off my rocker try
>
> Seq(1,2,3).contains(false)
>
> or
>
> List(1,2,3).contains(false)
>
> Do you see any warnings?
>
> There are two consistent positions one can take here. Either Seqs and
> Sets should both be covariant, or neither of them should be (and we
> should just do anyway with variance altogether). There is absolutely
> no fundamental difference between Seqs and Sets that allows one to be
> covariant but not the other. The library is internally inconsistent at
> present and should be fixed.
>

Yes, there is an inconsistency, I agree.

> If you think I'm wrong, please explain why List(1,2,3).contains(false)
> is perfectly valid but Set(1,2,3).contains(false) is an atrocity.
>

I think List(1,2,3).contains(false) should not compile. It does, because
the List contains's parameter type is Any.

I'm proposing to have:
def contains(x: ~T): Boolean
in List too.


> -Jeff

Regards,
Jan

Jeff Olson

unread,
Oct 7, 2012, 11:07:00 AM10/7/12
to scala...@googlegroups.com


On Sunday, October 7, 2012 9:25:03 AM UTC-5, JV wrote:
On 07.10.2012 16:06, Jeff Olson wrote:
>
> Let's be absolutely clear about this:
>
> If Sets are covariant then, by the Liskov substitution principle,
> Set(1,2,3).contains(false) _must_ compile (without warning).
>

I don't think it is clear. I'd expect that from LSP comes
Set(1,2,3).asInstanceOf[Set[Any]].contains(false) _must_ compile.

But that's the point: the asInstanceOf is unnecessary--a Set[Int] is already a Set[Any]

I retract the "without warning" part. After all, the compiler helpfully warns users when they write dubious (albeit perfectly valid) expressions like

3 == Some(3)

If 'set.contains(x)' can be determined to be false *at compile time* then a warning might be appropriate, e.g

scala> def dubious(set: Set[Int]) = set.contains("apple")
warning: a Set[Int] cannot contain a String, this expression will always yield false

or something like that.

Jan Vanek

unread,
Oct 7, 2012, 11:56:37 AM10/7/12
to scala...@googlegroups.com
On 07.10.2012 17:07, Jeff Olson wrote:


On Sunday, October 7, 2012 9:25:03 AM UTC-5, JV wrote:
On 07.10.2012 16:06, Jeff Olson wrote:
>
> Let's be absolutely clear about this:
>
> If Sets are covariant then, by the Liskov substitution principle,
> Set(1,2,3).contains(false) _must_ compile (without warning).
>

I don't think it is clear. I'd expect that from LSP comes
Set(1,2,3).asInstanceOf[Set[Any]].contains(false) _must_ compile.

But that's the point: the asInstanceOf is unnecessary--a Set[Int] is already a Set[Any]


In this case the asInstanceOf[] call brings the substitution ("the this is substituted for the return value"). The point is, the substitution is necessary here, you need to convince the compiler that you intend to lose the precise type, in order to be able to perform that particular call (contains(false)). So up-cast in this case, contrary to the usual, is necessary.

My example with asInstanceOf[] is not very lucky though. The other one is more clear I think, there is no asInstanceOf, as e.g. here:

val s: Set[Any] = Set(1,2,3)
s.contains(false) // must compile


I retract the "without warning" part. After all, the compiler helpfully warns users when they write dubious (albeit perfectly valid) expressions like

3 == Some(3)

If 'set.contains(x)' can be determined to be false *at compile time* then a warning might be appropriate, e.g

scala> def dubious(set: Set[Int]) = set.contains("apple")
warning: a Set[Int] cannot contain a String, this expression will always yield false

or something like that.

This is where we differ. I think it should be compile-time error, you think it should be a (compile-time) warning. Btw. I quote something:

On Wed, Aug 8, 2012 at 12:10 PM, Paul Phillips <pa...@improving.org> wrote:
To be told there is a programmer error at compile time in preference to silently being given the right answer to the wrong question at runtime is the reason there are types.

I know, in your case it is not silent, there is a warning. I think this is an error, code like that should be fixed, especially in real code where there are no constants, I prefer to be forced by the compiler to either fix it (99,99%), or, if I really have a reason, to perform this explicit up-cast (well I doubt it will ever happen).

With regards,
Jan

Roland Kuhn

unread,
Oct 7, 2012, 12:10:17 PM10/7/12
to Jan Vanek, scala...@googlegroups.com
Hi Jan,

7 okt 2012 kl. 06:35 skrev Jan Vanek:

It would be nice to have the Set covariant and at the same time the contains() "type-safe". The Set(1,2,3).contains(true) should be compile-time failure. But it should be possible to do val s: Set[Any] = Set(1,2,3); s.contains(true)

If Set[+T] is covariant the compiler complains that the covariant type is used in contra-variant position (in contains), but it is too strict. The contains() doesn't mutate the set (regardless of whether the set is mutable or immutable), and it follows from the semantics of contains(), that this particular usage is fine. Compiler can't know, sometimes, if such a method is abstract, he doesn't even have a code to attempt to, and even if it has the code, it might be impossible to verify that the parameter is used correctly. So we could tell him, that we know it, e.g. like:

trait Set[+T] {
  def contains(x: ~T): Boolean
}

This means that the type of “x” must be Any (when type-checking the body of “contains”). Without introducing new syntax it is already possible to express what you want:

scala> class A[T] { def f[U](x: U)(implicit ev: U <:< T) = true }
defined class A

scala> new A[Int].f("")
<console>:9: error: Cannot prove that String <:< Int.
              new A[Int].f("")
                          ^

scala> new A[Int].f(12)
res1: Boolean = true

scala> new A[Int].asInstanceOf[A[Any]].f("")
res2: Boolean = true

And with this scheme you could e.g. require U <: AnyRef, which may be helpful in some cases.

Regards,

Roland

Roland Kuhn
Typesafe – The software stack for applications that scale.
twitter: @rolandkuhn


Roland Kuhn

unread,
Oct 7, 2012, 12:16:01 PM10/7/12
to Jan Vanek, scala...@googlegroups.com
7 okt 2012 kl. 09:10 skrev Roland Kuhn:

Hi Jan,

7 okt 2012 kl. 06:35 skrev Jan Vanek:

It would be nice to have the Set covariant and at the same time the contains() "type-safe". The Set(1,2,3).contains(true) should be compile-time failure. But it should be possible to do val s: Set[Any] = Set(1,2,3); s.contains(true)

If Set[+T] is covariant the compiler complains that the covariant type is used in contra-variant position (in contains), but it is too strict. The contains() doesn't mutate the set (regardless of whether the set is mutable or immutable), and it follows from the semantics of contains(), that this particular usage is fine. Compiler can't know, sometimes, if such a method is abstract, he doesn't even have a code to attempt to, and even if it has the code, it might be impossible to verify that the parameter is used correctly. So we could tell him, that we know it, e.g. like:

trait Set[+T] {
  def contains(x: ~T): Boolean
}

This means that the type of “x” must be Any (when type-checking the body of “contains”). Without introducing new syntax it is already possible to express what you want:

scala> class A[T] { def f[U](x: U)(implicit ev: U <:< T) = true }
defined class A

oops, spoke too soon: I had forgotten the covariance annotation (should have coffee first).

scala> class A[+T] { def f[U](x: U)(implicit ev: U <:< T) = true }
<console>:7: error: covariant type T occurs in contravariant position in type <:<[U,T] of value ev
       class A[+T] { def f[U](x: U)(implicit ev: U <:< T) = true }

Now I need to understand why that is so and whether it can be worked around …

Rüdiger Klaehn

unread,
Oct 7, 2012, 1:02:30 PM10/7/12
to scala...@googlegroups.com
As I said before, I was convinced that invariant sets are the right way to go.

But since this apparently is a big deal for a lot of people, why not
just introduce a trait between Iterable and Set that does not extend
from Function1[A,Boolean] and thus can be covariant? That way you
would have a type to describe that you want an unordered collection of
some elements without duplicates.

Something like

trait CovariantSet[+T] extends Iterable[T] {
def unsafeContains(x:Any) : Boolean
}

trait Set[A] extends (A => Boolean)
with CoSet[A] // instead of Iterable[A]
with GenSet[A]
with GenericSetTemplate[A, Set]
with SetLike[A, Set[A]] {
override def companion: GenericCompanion[Set] = Set

override def seq: Set[A] = this
}

Daniel Sobral

unread,
Oct 7, 2012, 1:38:26 PM10/7/12
to Jeff Olson, scala...@googlegroups.com, Vlad Patryshev, Haoyi Li
On Sun, Oct 7, 2012 at 2:29 AM, Jeff Olson <jeff.d...@gmail.com> wrote:
>
>> There are two kinds of people in the world: those that thing
>> Set(1,2,3).contains(true) should be a compile time error, and those
>> that should stay away from statically typed languages.
>
> That's a rather odd position. So your opinion is that Lists should not be

I don't see why.

> covariant? Or that they shouldn't have a contains method? Or that covariance

No and no.

> and type safety are fundamentally at odds with one another and that anyone
> who wants type safety should abandoned covariance? In which case I think

Well, it certainly pays to abandon covariance in many cases. For
instance, Option would be perfectly usable with invariant classes if
the type of None and Some[t](x) were declared to be Option instead of
None.type and Some[t]. Scalaz has it working perfectly.

Covariance only matters if you have subtyping, and subtyping is
inherently evil. Or maybe not inherently, just accidentally.

THAT SAID,

I never said contains cannot be implemented in a type safe manner on a
covariant class. I'll leave such an implementation as an exercise to
the reader, but, as encouragement that it is possible, I provide a
small repl snippet:

scala> List(1, 2, 3) has true
<console>:13: error: type mismatch;
found : Boolean(true)
required: Int
List(1, 2, 3) has true
^

> Scala is not the language for you.

Non-sense. There are places where avoiding covariance pays, and there
are places where it doesn't. I never said not to use covariance.

Honestly, you are implying I said a bunch of things I have never said.
Cool down and read more carefully.

> Clearly anyone who wants a covariant Set class thinks that
> Set(1,2,3).contains(true) is a sensible expression (after all, a Set[Int] is
> a Set[Any]). So your argument is fundamentally begging the question.

You might as well replace that expression with "false", for any
Set[Int] and any Boolean. It's a constant. You are either obscuring
your code, or making a mistake. In the latter case, the sooner you
catch the error, the better. In the former case, there are automatic
tools for that.

I see no question begging here, except why would anyone NOT want that
to be a compile time error.

Daniel Sobral

unread,
Oct 7, 2012, 1:47:00 PM10/7/12
to Jeff Olson, scala...@googlegroups.com
On Sun, Oct 7, 2012 at 11:06 AM, Jeff Olson <jeff.d...@gmail.com> wrote:
>
> Let's be absolutely clear about this:
>
> If Sets are covariant then, by the Liskov substitution principle,
> Set(1,2,3).contains(false) _must_ compile (without warning).

That would bet case if a Set[Any] were a Set[Int], which is clearly
not the case. You are inverting the Liskov Substitution Principle,
since you do *not* have a Set[Any], but a Set[Int].

Daniel Sobral

unread,
Oct 7, 2012, 1:57:31 PM10/7/12
to Jeff Olson, scala...@googlegroups.com
On Sun, Oct 7, 2012 at 2:47 PM, Daniel Sobral <dcso...@gmail.com> wrote:
> On Sun, Oct 7, 2012 at 11:06 AM, Jeff Olson <jeff.d...@gmail.com> wrote:
>>
>> Let's be absolutely clear about this:
>>
>> If Sets are covariant then, by the Liskov substitution principle,
>> Set(1,2,3).contains(false) _must_ compile (without warning).
>
> That would bet case if a Set[Any] were a Set[Int], which is clearly

"be the case"

> not the case. You are inverting the Liskov Substitution Principle,
> since you do *not* have a Set[Any], but a Set[Int].

That sounds weird, so let me put it other terms. The LSP says I can
replace B with A if B <: A. So, this should compile (assuming
covariance):

def test(s: Set[Any]): Boolean = s.contains(false)
test(Set(1, 2, 3))

In this case, I'm using an instance of Set[Int] where a Set[Any] is
expected, and it works as it should. It would work with the "has" code
I used to demonstrate type-safety on covariance as well.

However, it does not follow that a Set[Int], *not used* where a
Set[Any] is expected, will work as a Set[Any].

Vlad Patryshev

unread,
Oct 7, 2012, 2:11:44 PM10/7/12
to Jeff Olson, scala...@googlegroups.com, Haoyi Li

Oh; of course! :)

Jan Vanek

unread,
Oct 7, 2012, 2:12:44 PM10/7/12
to scala...@googlegroups.com
On 07.10.2012 18:16, Roland Kuhn wrote:
7 okt 2012 kl. 09:10 skrev Roland Kuhn:

Hi Jan,

7 okt 2012 kl. 06:35 skrev Jan Vanek:

It would be nice to have the Set covariant and at the same time the contains() "type-safe". The Set(1,2,3).contains(true) should be compile-time failure. But it should be possible to do val s: Set[Any] = Set(1,2,3); s.contains(true)

If Set[+T] is covariant the compiler complains that the covariant type is used in contra-variant position (in contains), but it is too strict. The contains() doesn't mutate the set (regardless of whether the set is mutable or immutable), and it follows from the semantics of contains(), that this particular usage is fine. Compiler can't know, sometimes, if such a method is abstract, he doesn't even have a code to attempt to, and even if it has the code, it might be impossible to verify that the parameter is used correctly. So we could tell him, that we know it, e.g. like:

trait Set[+T] {
� def contains(x: ~T): Boolean
}

This means that the type of �x� must be Any (when type-checking the body of �contains�). Without introducing new syntax it is already possible to express what you want:

That's the case in invariant set too (that the type of �x� must be Any (when type-checking the body of �contains�)).
trait Set[T] { def contains(x: T): Boolean }
All you know is Any. The bounds apply the same to both versions.


scala> class A[T] { def f[U](x: U)(implicit ev: U <:< T) = true }
defined class A

oops, spoke too soon: I had forgotten the covariance annotation (should have coffee first).

scala> class A[+T] { def f[U](x: U)(implicit ev: U <:< T) = true }
<console>:7: error: covariant type T occurs in contravariant position in type <:<[U,T] of value ev
� � � �class A[+T] { def f[U](x: U)(implicit ev: U <:< T) = true }

Now I need to understand why that is so and whether it can be worked around �


Let's assume it is possible. How do you fix the Ordering version?

scala> new A[Int].f("")
<console>:9: error: Cannot prove that String <:< Int.
� � � � � � � new A[Int].f("")
� � � � � � � � � � � � � ^

scala> new A[Int].f(12)
res1: Boolean = true

scala> new A[Int].asInstanceOf[A[Any]].f("")
res2: Boolean = true

And with this scheme you could e.g. require U <: AnyRef, which may be helpful in some cases.

Regards,

Roland


Regards,
Jan


Roland Kuhn
Typesafe���The software stack for applications that scale.
twitter:�@rolandkuhn



Roland Kuhn
Typesafe���The software stack for applications that scale.
twitter:�@rolandkuhn



Jan Vanek

unread,
Oct 7, 2012, 2:25:53 PM10/7/12
to scala...@googlegroups.com
On 07.10.2012 19:02, R�diger Klaehn wrote:
> As I said before, I was convinced that invariant sets are the right way to go.

I had an impression (from that thread) that you were convinced that the
set's contains method should be "type-safe", primarily.

https://groups.google.com/forum/#!topic/scala-language/WqJR38REXnk

From which in current situation follows, secondarily, that the set must be invariant.

I want both, type-safety and covariance. Certainly I don't want to lose type-safety.


> But since this apparently is a big deal for a lot of people, why not
> just introduce a trait between Iterable and Set that does not extend
> from Function1[A,Boolean] and thus can be covariant? That way you
> would have a type to describe that you want an unordered collection of
> some elements without duplicates.
>
> Something like
>
> trait CovariantSet[+T] extends Iterable[T] {
> def unsafeContains(x:Any) : Boolean
> }
>
> trait Set[A] extends (A => Boolean)
> with CoSet[A] // instead of Iterable[A]
> with GenSet[A]
> with GenericSetTemplate[A, Set]
> with SetLike[A, Set[A]] {
> override def companion: GenericCompanion[Set] = Set
>
> override def seq: Set[A] = this
> }
>

Can't we avoid this chain-saw?

Plus, all you get here is unsafe contains.

With regards,
Jan

Roland Kuhn

unread,
Oct 7, 2012, 3:08:17 PM10/7/12
to Jan Vanek, scala...@googlegroups.com

7 okt 2012 kl. 11:25 skrev Jan Vanek:

> On 07.10.2012 19:02, Rüdiger Klaehn wrote:
>> As I said before, I was convinced that invariant sets are the right way to go.
>
> I had an impression (from that thread) that you were convinced that the set's contains method should be "type-safe", primarily.
>
> https://groups.google.com/forum/#!topic/scala-language/WqJR38REXnk
>
> From which in current situation follows, secondarily, that the set must be invariant.
>
> I want both, type-safety and covariance. Certainly I don't want to lose type-safety.
>
Thinking about why my previously presented code fails, I came to the conclusion that it is unsound (which is why the compiler rejects it). You cannot have the combination you say you want (actually you can, as Daniel noted, but let’s disregard that “type hack” for the moment), because the compile-time error you’ll get is a fragile one: due to type inference and some unrelated change elsewhere in your code, your static type may change, removing the error.

Basically, what you’re saying is

- I have implemented this method so it can deal with T arguments
- but due to variance, anybody could call it with any supertype of T, which you have no idea how to handle

This is not about changing the object (which is the classical argument why Array[] cannot be covariant).

Now let’s look at the hack:

scala> class A[+T]
defined class A

scala> implicit class AOps[T](val a: A[T]) extends AnyVal { def f(x: T) = true }
defined class AOps

scala> new A[Int].f(12)
res9: Boolean = true

scala> new A[Int].f("")
<console>:10: error: type mismatch;
found : String("")
required: Int


Those methods which have different variance needs can be split out in a fashion which “fixes” the type parameter. This solves the second part of my argument, but not the first, as the below may well be a rather hidden effect (and not as blatant as my demo):

scala> (new A[Int]: A[Any]).f("")
res11: Boolean = true


It seems a question of expectations: type-safety for me means «it will always protect me» while you would be fine with a best-effort service level.

Regards,

Roland


>
>> But since this apparently is a big deal for a lot of people, why not
>> just introduce a trait between Iterable and Set that does not extend
>> from Function1[A,Boolean] and thus can be covariant? That way you
>> would have a type to describe that you want an unordered collection of
>> some elements without duplicates.
>>
>> Something like
>>
>> trait CovariantSet[+T] extends Iterable[T] {
>> def unsafeContains(x:Any) : Boolean
>> }
>>
>> trait Set[A] extends (A => Boolean)
>> with CoSet[A] // instead of Iterable[A]
>> with GenSet[A]
>> with GenericSetTemplate[A, Set]
>> with SetLike[A, Set[A]] {
>> override def companion: GenericCompanion[Set] = Set
>>
>> override def seq: Set[A] = this
>> }
>>
>
> Can't we avoid this chain-saw?
>
> Plus, all you get here is unsafe contains.
>
> With regards,
> Jan
>

Jan Vanek

unread,
Oct 7, 2012, 3:46:44 PM10/7/12
to Roland Kuhn, scala...@googlegroups.com
On 07.10.2012 21:08, Roland Kuhn wrote:
> 7 okt 2012 kl. 11:25 skrev Jan Vanek:
>
>> On 07.10.2012 19:02, R�diger Klaehn wrote:
>>> As I said before, I was convinced that invariant sets are the right way to go.
>> I had an impression (from that thread) that you were convinced that the set's contains method should be "type-safe", primarily.
>>
>> https://groups.google.com/forum/#!topic/scala-language/WqJR38REXnk
>>
>> From which in current situation follows, secondarily, that the set must be invariant.
>>
>> I want both, type-safety and covariance. Certainly I don't want to lose type-safety.
>>
> Thinking about why my previously presented code fails, I came to the conclusion that it is unsound (which is why the compiler rejects it). You

Hmm, I'd say it might be sound, but the compiler is not able to prove it.

> cannot have the combination you say you want (actually you can, as Daniel noted, but let�s disregard that �type hack� for the moment), because the compile-time error you�ll get is a fragile one: due to type inference and some unrelated change elsewhere in your code, your static type may change, removing the error.
>
> Basically, what you�re saying is
>
> - I have implemented this method so it can deal with T arguments
> - but due to variance, anybody could call it with any supertype of T, which you have no idea how to handle

There are 2 points.

First, I have implemented the method so that it can deal with T
arguments, and the compiler type-checked it as if the T was Any (or the
upper bound), so any super-type up to the upper bound is "technically" fine.

Second, more important, the semantics (and implementation) of this
concrete method is such, that this one code works equally correct
(completely, not only "technically") for T and for any super-type (up to
the upper bound), without breaking anything. So, I wouldn't say "no idea
how to handle", but rather that the *one* code (which works for the
invariant case) is correct also for the super-types.

The compiler can't currently infer it, I think it should be possible to
infer it in some cases. The ~T annotation would have to be
propagated/repeated, I mean from declarations in traits into the
concrete method definitions, where the compiler can try. I don't know
how much can be inferred, my guess would be that the infer-able portion
is big enough so that the non-provable portion can be compile time
error. (I admit, I see it optimistically).

> This is not about changing the object (which is the classical argument why Array[] cannot be covariant).
>
> Now let�s look at the hack:
>
> scala> class A[+T]
> defined class A
>
> scala> implicit class AOps[T](val a: A[T]) extends AnyVal { def f(x: T) = true }
> defined class AOps
>
> scala> new A[Int].f(12)
> res9: Boolean = true
>
> scala> new A[Int].f("")
> <console>:10: error: type mismatch;
> found : String("")
> required: Int
>
>
> Those methods which have different variance needs can be split out in a fashion which �fixes� the type parameter. This solves the second part of my argument, but not the first, as the below may well be a rather hidden effect (and not as blatant as my demo):
>
> scala> (new A[Int]: A[Any]).f("")
> res11: Boolean = true
>
>
> It seems a question of expectations: type-safety for me means �it will always protect me� while you would be fine with a best-effort service level.

It depends how much can actually be inferred, as mentioned above. But
let's assume compiler can't infer anything, then right, I'd be fine with
"best-effort", as you say. I think it is better than to "cut the trait
into two and add implicit class for the covariant one". I think it's too
complex, not only for the implementor, also for the user.

> Regards,
>
> Roland

With regards,
Jan


>
>>> But since this apparently is a big deal for a lot of people, why not
>>> just introduce a trait between Iterable and Set that does not extend
>>> from Function1[A,Boolean] and thus can be covariant? That way you
>>> would have a type to describe that you want an unordered collection of
>>> some elements without duplicates.
>>>
>>> Something like
>>>
>>> trait CovariantSet[+T] extends Iterable[T] {
>>> def unsafeContains(x:Any) : Boolean
>>> }
>>>
>>> trait Set[A] extends (A => Boolean)
>>> with CoSet[A] // instead of Iterable[A]
>>> with GenSet[A]
>>> with GenericSetTemplate[A, Set]
>>> with SetLike[A, Set[A]] {
>>> override def companion: GenericCompanion[Set] = Set
>>>
>>> override def seq: Set[A] = this
>>> }
>>>
>> Can't we avoid this chain-saw?
>>
>> Plus, all you get here is unsafe contains.
>>
>> With regards,
>> Jan
>>
> Roland Kuhn
> Typesafe � The software stack for applications that scale.
> twitter: @rolandkuhn
>
>
>

Jan Vanek

unread,
Oct 8, 2012, 5:17:19 AM10/8/12
to scala-user, r...@rkuhn.info
If we have (case 1):

trait List[+T] {
  def contains(x: Any): Boolean
}

the compiler is happy. The declaration and definition of contains (not shown) is just fine. It is only that the compiler allows to use contains() with more than we wish for, namely T. So, when we have (case 2):

trait List[+T] {
  def contains(x: ~T): Boolean
}

we can use the same type-checking as in case 1, namely the x is seen as Any (during the compilation of the contains(), the inside), and at the same time only allow to call the contains() with T (the outside usage).

With regards,
Jan

Matthew Pocock

unread,
Oct 8, 2012, 8:21:22 AM10/8/12
to Haoyi Li, scala-user
IMHO, Set (the data structure) should be variant on the type. The problem is that Set[A] is conflated with A => Boolean. If the association between Set[A] and A => Boolean was via an implicit conversion, you could have your cake and eat it. However, since Set[A] extends A => Boolean, you're locked in to a fundamental disagreement between `get` and `put` ops on the data structure. Too much inheritance too soon is a classic OO snafu.

Matthew


On 5 October 2012 16:58, Haoyi Li <haoy...@gmail.com> wrote:
I noticed that the immutable Set class is invariant, and ignoring whether or not that is a good idea, I often find myself wanting a covariant Set to put things in. Currently I am either:
  • Using Seqs where a Set would actually fit better (e.g. I don't care about order, and I want the each-item-only-once characteristics of a set, and I want) because I want the covariance
  • Casting things to the correct type every time before putting them into the invariant Sets
Neither of these seems like a good solution. I couldn't find any convenient covariant Set class floating around the standard library to use; is it feasible to make a wrapper around invariant Sets to do all the casting for me, or is there a better solution? 

-Haoyi



--
Dr Matthew Pocock
Integrative Bioinformatics Group, School of Computing Science, Newcastle University
skype: matthew.pocock
tel: (0191) 2566550

Daniel Sobral

unread,
Oct 8, 2012, 11:03:19 AM10/8/12
to Matthew Pocock, Haoyi Li, scala-user
On Mon, Oct 8, 2012 at 9:21 AM, Matthew Pocock
<turingate...@gmail.com> wrote:
> IMHO, Set (the data structure) should be variant on the type. The problem is
> that Set[A] is conflated with A => Boolean. If the association between
> Set[A] and A => Boolean was via an implicit conversion, you could have your
> cake and eat it. However, since Set[A] extends A => Boolean, you're locked
> in to a fundamental disagreement between `get` and `put` ops on the data
> structure. Too much inheritance too soon is a classic OO snafu.

Actually, Seq/Set/Map is the first point at which Function comes into
the inheritance chain, and Function is the fundamental distinction
between them, as compared to Iterable.

I don't think the problem is there. I think the problem is that the
*data structures* inherit from there, instead of just being seen as
Seq/Map/Set through a type class.

Jeff Olson

unread,
Oct 8, 2012, 1:43:55 PM10/8/12
to scala...@googlegroups.com, Jeff Olson
Daniel, I think we disagree on the interpretation of the LSP. To me, it means that if I have a valid expression like 'set.contains("apple")' where set has type Set[Any] then I can literally substitute in a different set of type Set[Int] and still have a perfectly valid expression. You clearly subscribe to a slightly weaker notion.

Also I must apologize, for I did misinterpret your initial claim that "sets are invariant to make its contains method type-safe" as "sets are invariant because of the signature of the contains method", which is clearly not what you said. The latter is the oft given reason for why sets are not covariant and I think it is misleading at best. Restricting the signature of contains in the name of type-safety (but at the expense of invariance) is a perfectly valid design decision even if I happen to disagree with it.

As to your "List(1,2,3) has (true)" trick: It is very amusing. It hadn't occurred to me before. But as Roland points out elsewhere in this thread it is a fragile hack at best. Also the hack violates the LSP in the strong sense mentioned above.

As I see it there are thee desirable properties for containers such as Lists and Sets which cannot not all simultaneously be satisfied:

1. Covariance
2. Type-safety (namely Set(1,2,3).contains(true) should be a compile time *error*)
3. The Liskov substitution principal (in the strong sense mentioned above)

Something has to give. In the case of the standard library List class #2 was abandoned. In the case of the Set class #1. Personally I would rather have consistency and make the same choice for both. I see no fundamental reason for the distinction.

In another thread pointed to Rudiger, Paul Phillips offers at least some justification for the difference: namely 'contains' (aka membership) is a fundamental method on Sets and "just some method" on Lists. Whether or not this is just cause for the distinction is obviously open to debate. In my humble opinion, no.

In any case, I would like to see the design decision regarding the covariance of sets opened to the community as there are clearly trade-offs either way.

Cheers, Jeff 

Raoul Duke

unread,
Oct 8, 2012, 1:53:09 PM10/8/12
to scala...@googlegroups.com
On Mon, Oct 8, 2012 at 10:43 AM, Jeff Olson <jeff.d...@gmail.com> wrote:
> Daniel, I think we disagree on the interpretation of the LSP.

it appears to be confusing for lots of people.
http://lambda-the-ultimate.org/node/1430#comment-17016

Jeff Olson

unread,
Oct 8, 2012, 2:29:16 PM10/8/12
to scala...@googlegroups.com
To the original poster of this question. I apologize for my part in hijacking your thread. Let me offer than following solution to your dilemma:

scala> type CovSet[+A] = Set[A @annotation.unchecked.uncheckedVariance]
defined type alias CovSet

scala> def foo(set: CovSet[Any]) = set.contains("apple")
foo: (set: CovSet[Any])Boolean

scala> val s: CovSet[Int] = Set(1,2,3)
s: CovSet[Int] = Set(1, 2, 3)

scala> foo(s)
res0: Boolean = false

Cheers, Jeff

Daniel Sobral

unread,
Oct 8, 2012, 4:52:46 PM10/8/12
to Jeff Olson, scala...@googlegroups.com
On Mon, Oct 8, 2012 at 2:43 PM, Jeff Olson <jeff.d...@gmail.com> wrote:
> Daniel, I think we disagree on the interpretation of the LSP. To me, it
> means that if I have a valid expression like 'set.contains("apple")' where
> set has type Set[Any] then I can literally substitute in a different set of
> type Set[Int] and still have a perfectly valid expression. You clearly
> subscribe to a slightly weaker notion.

I entirely agree with that. If you do val set: Set[Any] = Set(1, 2,
3), it will work perfectly. Any code using Set[Any] will work
perfectly.

And that has absolutely no bearing on code that uses Set[Int].

Daniel Sobral

unread,
Oct 8, 2012, 4:58:11 PM10/8/12
to Jeff Olson, scala...@googlegroups.com
I'll even reply to myself to reinforce this point: the LSP is about
the behavior of existing code when fed a subtype of one of the types
it uses. It is *not* about changes in compilation when you replace a
type with another, nor about how a subtype acts own its own terms.

And that's the crux of it, since "Set(1,2,3).contains(true)" is *not*
the same program as "(Set(1, 2, 3): Set[Any]).contains(true)". The
latter uses Set[Any], while the former doesn't use Set[Any] *at all*.

Jan Vanek

unread,
Oct 8, 2012, 5:45:10 PM10/8/12
to scala...@googlegroups.com, r...@rkuhn.info
I was thinking about the Option.orElse where the T is used on both
sides. I know the current Option uses another type parameter in orElse,
so this is more of an example of using T on both sides. Also the
following orElse can't be called with anything less than => T, if one
has Opt[T] in hand.

trait Opt[+T] {
def orElse(alt: => ~T): T
}

Typechecking the orElse() definition must take into account that
possible invocations of orElse are done on an instance of Opt[B], which
is seen at the call site as Opt[A], where A <: B. This means we take the
body of orElse and replace every occurrence of T with an artificial type
S, where S <: T, like it were:

def orElse(alt: => S): S // including body

before the type-checking. The rest of the class remains unchanged, with
the exception of other methods which take ~T parameters. All such
methods are "prepared" for type-checking at once, and can thus call each
other.

In the example with contains(x: T) it is enough to see x as Any (or as
the upper bound of T if any), because the T is not used on both sides.
Having the artificial type S is more general, works for the simpler case
too, and allows to have the T on both sides.

I hope this is not completely stupid and I eventually get some critique :-).

Regards,
Jan

Jan Vanek

unread,
Oct 9, 2012, 2:59:23 AM10/9/12
to scala...@googlegroups.com
On 08.10.2012 23:45, Jan Vanek wrote:
> I was thinking about the Option.orElse where the T is used on both
> sides. I know the current Option uses another type parameter in
> orElse, so this is more of an example of using T on both sides. Also
> the following orElse can't be called with anything less than => T, if
> one has Opt[T] in hand.
>
> trait Opt[+T] {
> def orElse(alt: => ~T): T
> }
>
> Typechecking the orElse() definition must take into account that
> possible invocations of orElse are done on an instance of Opt[B],
> which is seen at the call site as Opt[A], where A <: B. This means we
> take the body of orElse and replace every occurrence of T with an
> artificial type S, where S <: T, like it were:
>

Sorry, I was completely stupid, of course. I meant:
Typechecking the orElse() definition must take into account that
possible invocations of orElse are done on an instance of Opt[B], which
is seen at the call site as Opt[A], where B <: A. This means we take the
body of orElse and replace every occurrence of T (corresponds to B) with
an artificial type S (corresponds to A), where T <: S, like it were:

Emre Sevinc

unread,
Oct 9, 2012, 4:05:10 AM10/9/12
to scala...@googlegroups.com, Daniel Sobral, Haoyi Li
On Saturday, October 6, 2012 7:17:39 AM UTC+2, Vlad Patryshev wrote:
I was always wondering, is List safe? It has some kind of contains() method... :)

Would be great if someone could put it all clearly and explicitly, like, see, Cardelli had demonstrated that Liskov principle is self-contradictory...

Hello,

Could you please the paper / article in which he did that? (A short googling turned out many papers by Cardelli but I could not find the exactly relevant one.)

Kind regards,
Emre

Matthew Pocock

unread,
Oct 9, 2012, 7:40:03 AM10/9/12
to Daniel Sobral, Haoyi Li, scala-user
On 8 October 2012 16:03, Daniel Sobral <dcso...@gmail.com> wrote:
On Mon, Oct 8, 2012 at 9:21 AM, Matthew Pocock
<turingate...@gmail.com> wrote:
> IMHO, Set (the data structure) should be variant on the type. The problem is
> that Set[A] is conflated with A => Boolean. If the association between
> Set[A] and A => Boolean was via an implicit conversion, you could have your
> cake and eat it. However, since Set[A] extends A => Boolean, you're locked
> in to a fundamental disagreement between `get` and `put` ops on the data
> structure. Too much inheritance too soon is a classic OO snafu.

Actually, Seq/Set/Map is the first point at which Function comes into
the inheritance chain, and Function is the fundamental distinction
between them, as compared to Iterable.

Set[A] is an enumeration (tabulation?) of a set of instances that describe an indicator function A => Boolean. Map[A, B] is an enumeration of a set of key->value pairs that describes a) a function (A, B) => Boolean (the entry set indicator function) and, equivalently, b) a function A => B (map lookup). These enumerations are not *the same thing* as the functions, but they are related *:1 with these functions.

I agree with you that the data structures should ideally be viewed as sets/maps through type classes - this is something I end up doing a lot in my code, particularly high-performance stuff where maps get packed into primitives or even NIO buffers. However, that doesn't detract from my conviction that the functions should be implicitly derived from these, rather than conflated in by inheritance. Let's not confuse a set with its indicator function - they are two distinct, but intimately related things.

Matthew


I don't think the problem is there. I think the problem is that the
*data structures* inherit from there, instead of just being seen as
Seq/Map/Set through a type class.

--
Daniel C. Sobral

I travel to the future all the time.

Meredith Gregory

unread,
Oct 9, 2012, 12:36:35 PM10/9/12
to Matthew Pocock, Daniel Sobral, Haoyi Li, scala-user
Dear Matthew,

Thanks for being an advocate of common sense! i gave a C9 video presentation to the same effect -- inspired by my coming up against the lack of covariant sets in Scala -- in the summer of 2011. We really have to distinguish API from implementation if we want to avoid needless conflicts and introduce layer upon layer of unnecessary complexity.

Best wishes,

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

nicola...@gmail.com

unread,
Oct 9, 2012, 12:48:05 PM10/9/12
to Matthew Pocock, Daniel Sobral, Haoyi Li, scala-user
a function (A, B) => Boolean (the entry
> set indicator function) and, equivalently, b) a function A => B (map
> lookup). These enumerations are not *the same thing* as the functions, but
> they are related *:1 with these functions.

I like the view as A => B better. It gives the right variance to B,
and the constraint of functionality of the map.
(only one b per a).
Could you explain why those are equivalent?

Matthew Pocock

unread,
Oct 10, 2012, 12:46:30 PM10/10/12
to nicola...@gmail.com, Daniel Sobral, Haoyi Li, scala-user
The indicator function f: (A, B) => Boolean is equivalent to g: A => B iff each key `a` in f is unique. We can compute a function equivalent to g with:

g'(k) := v where exists v . f(k, v)

We can compute a function equivalent to f with:

f'(k, v) := g(k) = v

Is that what you where asking? The Map and Set data-structures are fancy tabulations of values, incorporating tricks so that the table can be filtered and merged (the two basic operations upon which all others are built) in sub-linear time.

Matthew
Reply all
Reply to author
Forward
0 new messages