This page is no longer maintained — Please continue to the home page at www.scala-lang.org

the "contains" problem

13 replies
extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.

Since I was so recently discussing with the cc: recipient the annoyance imposed by the absence of errors or warnings here:

List("a", "b") contains 5

This is a consequence of the inability to selectively "turn off" variance (without having to rig up something silly like an implicit from List[T] to MyInvariantList[T]) thus requiring contains to be unbounded on the upside, i.e. Any. It looks like they've done something sensible about this in kotlin:

http://confluence.jetbrains.net/display/Kotlin/Generics#Generics-Typepro...

It says:

"What happened here is called type projection: we said that from is not simply an array, but a restricted (projected) one: we can only call those methods that return the type parameter T, in this case it means that we can only call get()."

I propose we steal this, but only after adding some needless complexity so it fits in better with our language.

Joshua.Suereth
Joined: 2008-09-02,
User offline. Last seen 32 weeks 5 days ago.
Re: the "contains" problem
It's a neat idea.   Mixing usage site variance into scala.    If we bump up the complexity, I vote using smileys (☺ and ☻)  for notation.
Seriously though, anything to help make variance easier to deal with would be great.

- Josh
On Tue, Jul 19, 2011 at 8:14 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
Since I was so recently discussing with the cc: recipient the annoyance imposed by the absence of errors or warnings here:

 List("a", "b") contains 5

This is a consequence of the inability to selectively "turn off" variance (without having to rig up something silly like an implicit from List[T] to MyInvariantList[T]) thus requiring contains to be unbounded on the upside, i.e. Any.  It looks like they've done something sensible about this in kotlin:

 http://confluence.jetbrains.net/display/Kotlin/Generics#Generics-Typeprojections

It says:

"What happened here is called type projection: we said that from is not simply an array, but a restricted (projected) one: we can only call those methods that return the type parameter T, in this case it means that we can only call get()."

I propose we steal this, but only after adding some needless complexity so it fits in better with our language.

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: the "contains" problem
On 20/07/11 13:58, Josh Suereth wrote:
CAFLqJkxgv3kHMP39amoGQn5v4noTeBOZ1X9pWCNTu1gJKqR0cA [at] mail [dot] gmail [dot] com" type="cite">anything to help make variance easier to deal with would be great

I vote for (but you already knew that):

* trait Covariant[F[_]] { def fmap[A, B](f: A => B): F[A] => F[B] }
* trait Contravariant[F[_]] { def contramap[A, B](f: A => B): F[B] => F[A] }

List[A] would then be invariant and have an implementation of Covariant[List] and the contains method would also accept an implicit argument of type Equal[A], which itself, has an implementation of Contravariant[Equal].

Unfortunately, Kotlin adds needless complexity by omitting higher-kinds (attributing to its todo list) thus making the above solution impossible.

-- 
Tony Morris
http://tmorris.net/

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: the "contains" problem


On Wed, Jul 20, 2011 at 5:58 AM, Josh Suereth <joshua [dot] suereth [at] gmail [dot] com> wrote:
It's a neat idea.   Mixing usage site variance into scala.    If we bump up the complexity, I vote using smileys (☺ and ☻)  for notation.
Seriously though, anything to help make variance easier to deal with would be great.

How is this different from wildcards/existential types?

 -- Martin
 

milessabin
Joined: 2008-08-11,
User offline. Last seen 33 weeks 3 days ago.
Re: the "contains" problem

On Wed, Jul 20, 2011 at 9:24 AM, martin odersky wrote:
> On Wed, Jul 20, 2011 at 5:58 AM, Josh Suereth
> wrote:
>>
>> It's a neat idea.   Mixing usage site variance into scala.    If we bump
>> up the complexity, I vote using smileys (☺ and ☻)  for notation.
>> Seriously though, anything to help make variance easier to deal with would
>> be great.
>>
> How is this different from wildcards/existential types?

It's not ... all we need is a simple type alias,

type Out[C[_], B] = C[_ <: B]

and then we get pretty much the same appearances,

scala> val ints = Array(1, 2, 3)
ints: Array[Int] = Array(1, 2, 3)

scala> val any = new Array[Any](3)
any: Array[Any] = Array(null, null, null)

scala> def copy(from: Out[Array, Any], to : Array[Any]) { for(i <- 0
until from.length) to(i) = from(i) }
copy: (from: Out[Array,Any], to: Array[Any])Unit

scala> copy(ints, any)

scala> any
res1: Array[Any] = Array(1, 2, 3)

For completeness, In looks like,

type In[C[_], B] = C[_ >: B]

Cheers,

Miles

adriaanm
Joined: 2010-02-08,
User offline. Last seen 31 weeks 4 days ago.
Re: the "contains" problem
nice!

On Wed, Jul 20, 2011 at 11:21 AM, Miles Sabin <miles [at] milessabin [dot] com> wrote:
On Wed, Jul 20, 2011 at 9:24 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:
> On Wed, Jul 20, 2011 at 5:58 AM, Josh Suereth <joshua [dot] suereth [at] gmail [dot] com>
> wrote:
>>
>> It's a neat idea.   Mixing usage site variance into scala.    If we bump
>> up the complexity, I vote using smileys (☺ and ☻)  for notation.
>> Seriously though, anything to help make variance easier to deal with would
>> be great.
>>
> How is this different from wildcards/existential types?

It's not ... all we need is a simple type alias,

 type Out[C[_], B] = C[_ <: B]

and then we get pretty much the same appearances,

 scala> val ints = Array(1, 2, 3)
 ints: Array[Int] = Array(1, 2, 3)

 scala> val any = new Array[Any](3)
 any: Array[Any] = Array(null, null, null)

 scala> def copy(from: Out[Array, Any], to : Array[Any]) { for(i <- 0
until from.length) to(i) = from(i) }
 copy: (from: Out[Array,Any], to: Array[Any])Unit

 scala> copy(ints, any)

 scala> any
 res1: Array[Any] = Array(1, 2, 3)

For completeness, In looks like,

 type In[C[_], B] = C[_ >: B]

Cheers,


Miles

--
Miles Sabin
tel: +44 7813 944 528
gtalk: miles [at] milessabin [dot] com
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

milessabin
Joined: 2008-08-11,
User offline. Last seen 33 weeks 3 days ago.
Re: the "contains" problem

On Wed, Jul 20, 2011 at 10:41 AM, Adriaan Moors wrote:
> nice!

Err ... well, if "completely trivial" qualifies as nice ;-)

Cheers,

Miles

adriaanm
Joined: 2010-02-08,
User offline. Last seen 31 weeks 4 days ago.
Re: the "contains" problem


On Wed, Jul 20, 2011 at 11:43 AM, Miles Sabin <miles [at] milessabin [dot] com> wrote:
On Wed, Jul 20, 2011 at 10:41 AM, Adriaan Moors <adriaan [dot] moors [at] epfl [dot] ch> wrote:
> nice!

Err ... well, if "completely trivial" qualifies as nice ;-)
that's exactly why it nice -- see also the scala complexity discussion
Ittay Dror 2
Joined: 2010-05-05,
User offline. Last seen 42 years 45 weeks ago.
Re: the "contains" problem
Can you please elaborate how "contains" will look like with this approach?
milessabin
Joined: 2008-08-11,
User offline. Last seen 33 weeks 3 days ago.
Re: the "contains" problem

On Wed, Jul 20, 2011 at 11:37 AM, Ittay Dror wrote:
> Can you please elaborate how "contains" will look like with this approach?

I don't think there's anything new here which helps.

Cheers,

Miles

adriaanm
Joined: 2010-02-08,
User offline. Last seen 31 weeks 4 days ago.
Re: the "contains" problem


On Wed, Jul 20, 2011 at 12:37 PM, Ittay Dror <ittay [dot] dror [at] gmail [dot] com> wrote:
Can you please elaborate how "contains" will look like with this approach?
I think this is a different problem: we'd like to use a covariant type parameter in a contravariant position
As far as I understand (is there a more detailed spec?), Kotlin's type projections can only be used to turn invariant type params into co/contravariant ones, by blocking access to members that mention the type param in a contra/covariant position.
Since the type of the target of a method selection can be subsumed, a List[String] can be re-interpreted as a List[Any], and must thus support the same operations. In theory, if you're certain (statically) that you know the exact (dynamic) type of a target of a method call, you need not worry about this and could allow a covariant type parameter in a contravariant position. However, Scala does not have this notion of exact types.
On the other hand, implicit conversions do not perform this subsumption, so you can do something like:
scala> case class Source[+T](val contents: T)scala> trait Contains[T] {      |   def contents: T     |   def contains(x: T) = contents == x     | }
scala> implicit def containsSrc[T](s: Source[T]) = new Contains[T]{def contents = s.contents}
scala> Source(1) contains "1"<console>:12: error: type mismatch; found   : java.lang.String("1") required: Int       Source(1) contains "1"                           ^
scala> Source(1) contains 1res1: Boolean = true
scala> val x: Source[Any] = Source(1) // we have to make subsumption explicit x: Source[Any] = Source(1)
scala> x contains "1"res2: Boolean = false
odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: the "contains" problem


On Wed, Jul 20, 2011 at 1:26 PM, Adriaan Moors <adriaan [dot] moors [at] epfl [dot] ch> wrote:


On Wed, Jul 20, 2011 at 12:37 PM, Ittay Dror <ittay [dot] dror [at] gmail [dot] com> wrote:
Can you please elaborate how "contains" will look like with this approach?
I think this is a different problem: we'd like to use a covariant type parameter in a contravariant position
As far as I understand (is there a more detailed spec?), Kotlin's type projections can only be used to turn invariant type params into co/contravariant ones, by blocking access to members that mention the type param in a contra/covariant position.

That was precisely the idea of Viroli and Igarashi. Their underlying formalism were existential types. Their work led to Java wildcards, which replaced existentials by something which is a bit easier to use but far more hairy to spec & understand. I still claim that the number of people who really understand wildcards number fewer than the fingers of one hand. I wonder where in that spectrum Kotlin is.

Cheers

 -- Martin
Ben Hutchison 3
Joined: 2009-11-02,
User offline. Last seen 42 years 45 weeks ago.
Re: the "contains" problem

On Wed, Jul 20, 2011 at 10:14 AM, Paul Phillips wrote:
> This is a consequence of the inability to selectively "turn off" variance (without having to rig up something silly like an implicit from List[T] to MyInvariantList[T]) thus requiring contains to be unbounded on the upside, i.e. Any.  It looks like they've done something sensible about this in kotlin:
>
>  http://confluence.jetbrains.net/display/Kotlin/Generics#Generics-Typeprojections
>
> It says:
>
> "What happened here is called type projection: we said that from is not simply an array, but a restricted (projected) one: we can only call those methods that return the type parameter T, in this case it means that we can only call get()."
>
> I propose we steal this, but only after adding some needless complexity so it fits in better with our language.

+1.

Many moons ago, there was a long and informative discussion on why
scala.collection.Set is not covariant but rather invariant:
http://www.scala-lang.org/node/2685

What emerged was that Set combines two roles
(a) a contravariant predicate that tests for membership of the Set
(b) a covariant container that can enumerate the members of the set

In that discussion, after some silly stuff, I eventually said
something sensible: "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)"

I still hold that view. The problem is, such as change to a key type
like Set may be/appear too disruptive to pursue or win support for.

It is exactly these kinds of "legacy API" use cases where it might be
nice to give "wiggle-room" in variance to the _client_ of an API, so
that they can narrow existing APIs, like Set, down to the operations
they use.

For example, if one uses a Set object only as a container, treat is an
being covariant. If one uses it purely as a predicate, then allow it
to be contra-variant.

In summary: definition-site variance would be Scala's default.
Constrained use-site variance an optional override, where a client has
different, probably narrower, usage patterns for an API than the API's
designer anticipated.

-Ben

Sebastien Bocq
Joined: 2008-12-18,
User offline. Last seen 42 years 45 weeks ago.
Re: the "contains" problem


2011/7/21 Ben Hutchison <brhutchison [at] gmail [dot] com>
On Wed, Jul 20, 2011 at 10:14 AM, Paul Phillips <paulp [at] improving [dot] org> wrote:
> This is a consequence of the inability to selectively "turn off" variance (without having to rig up something silly like an implicit from List[T] to MyInvariantList[T]) thus requiring contains to be unbounded on the upside, i.e. Any.  It looks like they've done something sensible about this in kotlin:
>
>  http://confluence.jetbrains.net/display/Kotlin/Generics#Generics-Typeprojections
>
> It says:
>
> "What happened here is called type projection: we said that from is not simply an array, but a restricted (projected) one: we can only call those methods that return the type parameter T, in this case it means that we can only call get()."
>
> I propose we steal this, but only after adding some needless complexity so it fits in better with our language.

+1.

Many moons ago, there was a long and informative discussion on why
scala.collection.Set is not covariant but rather invariant:
http://www.scala-lang.org/node/2685

What emerged was that Set combines two roles
(a)  a contravariant predicate that tests for membership of the Set
(b) a covariant container that can enumerate the members of the set

In that discussion, after some silly stuff, I eventually said
something sensible: "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)"

I still hold that view. The problem is, such as change to a key type
like Set may be/appear too disruptive to pursue or win support for.

It is exactly these kinds of "legacy API" use cases where it might be
nice to give "wiggle-room" in variance to the _client_ of an API, so
that they can narrow existing APIs, like Set, down to the operations
they use.

For example, if one uses a Set object only as a container, treat is an
being covariant. If one uses it purely as a predicate, then allow it
to be contra-variant.

In summary: definition-site variance would be Scala's default.
Constrained use-site variance an optional override, where a client has
different, probably narrower, usage patterns for an API than the API's
designer anticipated.

-Ben

I've been experimenting with the following pattern for a while to get around variance issues. I know, it is hackish around the corner and its been only a few weeks, but so far I find it very easy to work with and I find the explicit coercion adds some clues to the code. Maybe it is time for feedback :)

  trait Covariant[CC[A], A] {
    def coerce[B >: A]:CC[B] = this.asInstanceOf[CC[B]]
  }

  trait Covariant2[M[A, B], A, B] {
    def coerce[C >: A, D >: B]:M[C, D] = this.asInstanceOf[M[C, D]]
  }
 
  trait ArrowVariant[M[_, _], A, B] {
    def coerce[C <: A, D >: B]:M[C, D] = this.asInstanceOf[M[C, D]]
  }
 
  // ...
 
  class List[A] extends Covariant[List, A] with Function[A, Boolean] {
  
    def ::(a:A):List[A] = new ::(a, this)

    def append(l:List[A]):List[A] = this match {
      case Nil()     => l
      case (a :: as) => new ::(a, as append l)
    }

    def contains(x:A):Boolean = this match {
      case Nil()     => false
      case (a :: as) => if (a == x) true else as contains x
    }

    def apply(a:A):Boolean = contains(a)
  }
 
  object Nil extends List[Nothing] {
    def apply[A]:List[A] = this.coerce
    def unapply[A](l:List[A]):Boolean = l eq this
  }
 
  case class ::[A](hd:A, tail:List[A]) extends List[A]
  
  abstract class Pet
  case class Cat() extends Pet
  case class Dog() extends Pet

   val l1 = Dog() :: Cat() :: Nil[Pet]
 
  l1 contains Dog()
 
  val l2 = Cat() :: Nil[Cat]
 
  // does not compile: l2 contain Dog()
 
  val l4 = l2.coerce append l1
  val l5 = l1 append l2.coerce

 
  val l2 = Cat() :: Nil[Cat]
  val l4 = l2.coerce append l1
  val l5 = l1 append l2.coerce


--
Sébastien

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland