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.
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 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).
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.
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.
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.
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
}
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
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:
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 }defined class A
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 �
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
Typesafe���The software stack for applications that scale.
twitter:�@rolandkuhn
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
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...
On Mon, Oct 8, 2012 at 9:21 AM, Matthew PocockActually, Seq/Set/Map is the first point at which Function comes into
<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.
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.
--
Daniel C. Sobral
I travel to the future all the time.