Scala Covariance and Lower Type Bounds Explanation

Question

I am trying to get my head around covariance in respect with methods creating new immutable types using lower bounds

class ImmutableArray[+T](item: T, existing: List[T] = Nil) {  
  private val items = item :: existing

  def append[S >: T](value: S) = new ImmutableArray[S](value, items)
}

I understand that the type parameter T can not be used in the append method as it violates the rules but if I have say a Customer class and sub class Student I can still make the type U Student.

I can see this works but why is this not a violation of the rules? I could understand if I had a list of Students and then added a Customer I could only return a list of Customers due to not allowing a Customer to be assigned to a Student as it is a parent type. But why can I use Student?

What am I missing?

Thanks Blair

Answer 1

Your class offers 2 operations involving T:

1. Construction

   nextImmutableArray = new ImmutableArray(nextT, priorImmutableArray)
   

   Because of this operation, the type parameter T must be co-variant: +T. That allows you to construct with the parameter set to an object of type (T OR a subtype of T).

   Think: it's valid to construct an array of Oranges by including a Valencia Orange.

2. Combination

   nextImmutableArray.append(newItemTorAncestor)
   

   This method doesn't append to your data structure. It takes two independent elements (your array instance this and an extra object) and it combines them within a newly constructed array. You could consider changing your method name to appendIntoCopy. Even better, you could use the name +. But to be most correct and consistent with Scala conventions, the best name would be :+ .

   Why am I waffling on about a 'random' method name, when you asked a specific question???

   Because precise nature of the method determines whether the returned data structure is (a) non-variant with T (b) co-variant with T (c) contra-variant with T.

   • Start with: ImmutableArray[T] - contains type T (or subtypes)
   • Combine with: Object of type S.
   • Result: ImmutableArray[S]
   • If S was allowed to be a proper subtype of T (beyond T itself), then the new array can't contain original elements of type T!
   • If S is of type T or a supertype of T, then all is good - can contain original elements, plus new element!

   When you combine arrays and elements, the newly created data structure must have a type parameter that is a supertype of the common ancestor type. Otherwise it couldn't contain the original elements. In general when you carry out "a :+ b", where A is an Array[A] and b is of type B, the resulting data structure is Array[Some_SuperType_Of_Both_A_and_B].

   Think: if I start with an array of Oranges, then add a Lemon, I end up with an array of Citrus Fruit (not Oranges, Navel Oranges, nor Lemons).

---

Method Rules (strict on input, accomodating on output):

• a) input parameter provides an element to insert (mutation): Co-Variant
• a) output parameter returns an element from data structure: Contra-Variant
• c) output parameter, returns data structure after combining: Contra-Variant
• c) Use type as a lower bound: "Flip" variance ("Contra-variant to T" = "Co-Variant to S, which has lower-bound T")

In case of append: Start with T, Output Data Structure = Contra-Variant to T, Type S uses T as a lower-bound, so Input Parameter = Co-Variant with S. This means that if T1 is a subtype of T2 then ImmutableArray[T1] is a subtype of ImmutableArray[T2] and that it can be substituted wherever the latter is expected, with all methods following Liskov's substitution principle.

Answer 2

First question:

I understand that the type parameter T can not be used in the append method as it violates the rules

Well it can be used. S >: T simply means that if you pass in a type S that is equal to T or its parant, then S will be used. If you pass a type that is sublevel to T then T will be used.

scala> class Animal
defined class Animal

scala> class Canine extends Animal
defined class Canine

scala> class Dog extends Canine
defined class Dog

scala> new ImmutableArray[Canine](new Canine)
res6: ImmutableArray[Canine] = ImmutableArray@a47775

scala> res6.append(new Animal)
res7: ImmutableArray[Animal] = ImmutableArray@1ba06f1

scala> res6.append(new Canine)
res8: ImmutableArray[Canine] = ImmutableArray@17e4626

scala> res6.append(new Dog)
res9: ImmutableArray[Canine] = ImmutableArray@a732f0

Above doing res6.append(new Dog) still gives you ImmutableArray of type Canine. And if you think in a way it makes complete sense as adding Dog to Canine Array will still keep the array Canine. But adding Animal to Canine Array makes it Animal as it can no longer be perfectly canine (can be molar or something).

This is a perfect example on why it is usually known that contra-variant type declaration make it perfect for writes (your case) and co-variance for reads.

In your example, I think the confusion might be because you are comparing S >: T to S super T (from java world). With S super T you are bound to have the argument type that is Super class of T and it does not allow you to pass an argument that is sub-type to T. In scala, the compiler takes care of this (thanks to type-inference).

Answer 3

Consider the followng hierarchy:

class Foo
class Bar extends Foo { def bar = () }
class Baz extends Bar { def baz = () }

And a class similar to yours:

class Cov[+T](val item: T, val existing: List[T] = Nil) {
  def append[S >: T](value: S) = new Cov[S](value, item :: existing)
}

Then we can construct three instances for each of the Foo sub-types:

val cFoo = new Cov(new Foo)
val cBar = new Cov(new Bar)
val cBaz = new Cov(new Baz)

And a test function that requires bar elements:

def test(c: Cov[Bar]) = c.item.bar

It holds:

test(cFoo) // not possible (otherwise `bar` would produce a problem)
test(cBaz) // ok, since T covariant, Baz <: Bar --> Cov[Baz] <: Cov[Bar]; Baz has bar

Now the append method, falling back to upper bound:

val cFoo2 = cBar.append(new Foo)

This is ok, because Foo >: Bar, List[Foo] >: List[Bar], Cov[Foo] >: Cov[Bar].

Now, correctly your bar access has gone:

cFoo2.item.bar // bar is not a member of Foo

---

To understand why you need the upper-bound, imagine the following was possible

class Cov[+T](val item: T, val existing: List[T] = Nil) {
  def append(value: T) = new Cov[T](value, item :: existing)
}

class BarCov extends Cov[Bar](new Bar) {
  override def append(value: Bar) = {
    value.bar // !
    super.append(value)
  }
}

Then you could write

def test2[T](cov: Cov[T], elem: T): Cov[T] = cov.append(elem)

And the following illegal behaviour would be allowed:

test2[Foo](new BarCov, new Foo) // BarCov <: Cov[Foo]

where value.bar would be called on a Foo. Using (correctly) the upper bound, you wouldn't be able to implement append as in the hypothetical last example:

class BarCov extends Cov[Bar](new Bar) {
  override def append[S >: Bar](value: S) = {
    value.bar // error: value bar is not a member of type parameter S
    super.append(value)
  }
}

So the type system remains sound.

Answer 4

It works because the append method returns a broader class than the original one. Let's conduct a little experiment.

    scala> case class myIntClass(a:Int)
    defined class myIntClass

    scala> case class myIntPlusClass(a:Int, b:Int)
    defined class myIntPlusClass

   scala> class ImmutableArray[+T](item: T, existing: List[T] = Nil){
         | 
         | private val items = item :: existing
         | 
         | def append[S >: T](value: S) = new ImmutableArray[S](value,items)
         | def getItems = items
         | }
    defined class ImmutableArray

    scala> val ia = new ImmutableArray[myIntClass](myIntClass(3))
    ia: ImmutableArray[myIntClass] = ImmutableArray@5aa91edb

    scala> ia.getItems
    res15: List[myIntClass] = List(myIntClass(3))

    scala> ia.append(myIntPlusClass(3,5))
    res16: ImmutableArray[Product with Serializable] = ImmutableArray@4a35a157

    scala> res16.getItems
    res17: List[Product with Serializable] = List(myIntPlusClass(3,5), myIntClass(3))

    scala> res16
    res18: ImmutableArray[Product with Serializable] = ImmutableArray@4a35a157

So you can add a derived class here, but it only works due to the fact that the base type of the resulting array is demoted to a lowest common denominator (in this case, Serializable).

If we try to force the derived type on the resulting array, it won't work:

scala> ia.append[myIntPlusClass](myIntPlusClass(3,5))
<console>:23: error: type arguments [myIntPlusClass] do not conform to method append's type parameter bounds [S >: myIntClass]
              ia.append[myIntPlusClass](myIntPlusClass(3,5))

Trying to do the same making append return an array of derived types won't work, because T is not a subclass of S:

scala> class ImmutableArray[+T](item: T, existing: List[T] = Nil){
     |           
     |          private val items = item :: existing
     |          
     |          def append[S <: T](value: S) = new ImmutableArray[S](value,items)
     |          def getItems = items
     |          }
<console>:21: error: type mismatch;
 found   : List[T]
 required: List[S]
                def append[S <: T](value: S) = new ImmutableArray[S](value,items)