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.