Covariant type parameter

Question

I have been trying to push my understanding of Scala a little bit further lately and I cannot really figure out some things about covariant/contravariant type parameters.

Let's say I have a class called Basket as follows :

class Basket[+A <: Fruit](items: List[A]) {
  // ...
  def addAll[B >: A <: Fruit](newItems: List[B]): Basket[B] =
new Basket(items ++ newItems)
  // ...
}

and some classes like this:

trait Fruit
class Banana extends Fruit
class Orange extends Fruit

I know for sure that these assertions are correct :

Basket[Fruit] can be instantiated
Basket[String] cannot be instantiated (because String is not a subtype of Fruit)
Basket[Banana] is a subtype of Basket[Fruit]
Basket[Orange] is a subtype of Basket[Fruit]

This code:

val bananaBasket: Basket[Banana] = new Basket(List(new Banana, new Banana))
bananaBasket.addAll(List(new Orange))

will return a Basket[Fruit]

This code:

val bananaBasket: Basket[Banana] = new Basket(List(new Banana, new Banana))
bananaBasket.addAll(List(new Banana))

will return a Basket[Banana]

What I do not understand is how the B >: A affects the return type of the method .. Why when I add an Orange the return type become Basket[Fruit] and when I add a Banana, it stays a Basket[Banana] ? Does it look for the "lowest" common super-type ?

What did you find out when you tried compiling your "assertions" and seeing which of them are correct? — Dima
You also need to add Fruit as an upper bound to the parameter B in Basket.addAll method (addAll[B >: A <: Fruit]...). — Peter Neyens
All the assertions are true. My question was not very clear indeed. I'll edit it. — meucaa
"Does it look for the "lowest" common super-type ?" - exactly — Haspemulator
@PeterNeyens Just for information, do you have any idea on why we have to repeat the constraint ? — meucaa

Haspemulator Haspemulator · Accepted Answer · 2016-06-29T16:17:59

Yes, the Scala compiler tries to find the lowest common super-type. You can see it anywhere in Scala, including standard library classes. Consider this example for List, which is also covariant on its parameter type:

1.0 :: List(1, 2, 3)
// result type is AnyVal, least common ancestor of Double and Int
res1: List[AnyVal] = List(1.0, 1, 2, 3)

"0" :: List(1, 2, 3)
// result type is List[Any], lowest common ancestor of String and Int
res2: List[Any] = List(0, 1, 2, 3)

0 :: List(1, 2, 3)
// result type is List[Int] exactly
res3: List[Int] = List(0, 1, 2, 3)

res2.head
res4: Any = 0

res2.head.asInstanceOf[String]
res5: String = "0"

One can argue this is a dubious feature of Scala type system, because it's easy to end up with something like Any (how it's in my example) or Product with Serializable (if you're dealing with case classes), and then the error messages are quite misleading.

If you want to restrict Scala from generalizing your types, you should use the "sad in a hat" type constraint <:<. Then your code would look like this (I've changed the classes to case classes for readability):

case class Banana() extends Fruit
defined class Banana

case class Orange() extends Fruit
defined class Orange

case class Basket[+A <: Fruit](items: List[A]) {
    // ...
    def addAll[B >: A <: Fruit, C >: A](newItems: List[B])(implicit ev: B <:< C): Basket[B] =
  new Basket(items ++ newItems)
    // ...
  }
defined class Basket

val bananaBasket: Basket[Banana] = Basket(List(Banana(), Banana()))
bananaBasket: Basket[Banana] = Basket(List(Banana(), Banana()))

bananaBasket.addAll(List(Orange())) // not accepted
Main.scala:593: Cannot prove that Product with Serializable with cmd27.Fruit <:< cmd47.Banana.
bananaBasket.addAll(List(Orange()))
                   ^
Compilation Failed

bananaBasket.addAll(List(Banana())) // accepted
res52: Basket[Banana] = Basket(List(Banana(), Banana(), Banana()))

You can read more about this pattern in an very informative blog post here: http://blog.bruchez.name/2015/11/generalized-type-constraints-in-scala.html

Covariant type parameter

1 Answers