the "contains" problem
Paul Phillips
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.
Josh Suereth
Tony Morris
anything to help make variance easier to deal with would be great
* 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/
martin odersky
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.
-- Martin
Miles Sabin
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: mi...@milessabin.com
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin
Adriaan Moors
Miles Sabin
> nice!
Err ... well, if "completely trivial" qualifies as nice ;-)
Adriaan Moors
On Wed, Jul 20, 2011 at 10:41 AM, Adriaan Moors <adriaa...@epfl.ch> wrote:
> nice!
Err ... well, if "completely trivial" qualifies as nice ;-)
Ittay Dror
Miles Sabin
> Can you please elaborate how "contains" will look like with this approach?
I don't think there's anything new here which helps.
Adriaan Moors
Can you please elaborate how "contains" will look like with this approach?
martin odersky
I think this is a different problem: we'd like to use a covariant type parameter in a contravariant positionOn Wed, Jul 20, 2011 at 12:37 PM, Ittay Dror <ittay...@gmail.com> wrote:Can you please elaborate how "contains" will look like with this approach?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
> 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
Sébastien Bocq
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