(Co)Variance on Lists different then on Stacks in Scala?

Question

Hi,

When I'm writing this code, I've got a Compile error in Scala

var s: Stack[_ <: Number] = new Stack[Integer]; 
s.push(new Integer(1)); //compile-error: type mismatch; found :Integer required: _$bqjyh where type _$bqjyh <: Number
s.push(null); //compile-error: type mismatch; found   : Null(null) required: _$2 where type _$2 <: Objects.Vehicle

This is equivalent to covariant collection in Java due the wildcard; it exact type in unknown, so we cannot added something to the stack.

But with lists I won't get the same error:

   var list: List[_ <: Number] = Nil;
   var intList : List[Integer] = new Integer(1) :: Nil;
   list = intList ; //no error
   list = new Float(2) :: vehicles;  //even float allowed

Now I can added even a float, but in fact I would believe the list is a List of Integers, so not Floats allowed.

1) Why is this allowed with lists, and not with Stacks? Is this due to the cons (::) operator?

2) What is the type of list? Is it dynamic?

3) Why is this allowed in Scala and not in Java?

4) Can I add something to the stack? (null is not working, in Java does because generic types only allows reference types)

Answer 1

:: isn't a mutating operation. This means that x :: xs will return a List of type List[ commonSupertypeOf[ typeOf[x], elementTypeOf[xs] ] ] (this isn't actual scala code, but I hope my point comes across), but it will not change the type of xs. If xs has type List[Float] and x has type Integer, then the expression x :: xs will have type List[Numeric], but the type of xs is still List[Float], so nothing breaks.

add however is a mutating operation. xs.add(x) will add an Integer to a Stack whose type is Stack<Float>, which is clearly an error.

This explains why doing x :: xs is not dangerous. Now to explain why it typeckecks:

The singnature of :: on a List[A] is: def :: [B >: A] (x: B) : List[B].

What this means is that for any types A and B where B is a supertype of A, :: given a value of type B and a list of type A will produce a list of type B. So when you do some someInteger :: someFloats, the compiler infers that B is Numeric and A is Float and everything works.

In java terms that would be <B supertypeOf A> List<B> prepend(B item) except that supertypeOf isn't legal java.

Answer 2

The Scala language uses definition-site variance annotations, not use-site variance annotations. Covariance for Lists is defined in the List trait, while Stacks are not defined as covariant. In general, mutable collections can't be covariant, because that leads to type errors involving inserting new elements into the collection (which is a major problem with Java's covariant arrays.)