RE: I don’t really get the example on the “Lower Type Bounds” page of the language tour

Question
1

Hi @SliverHotDog, not sure why you deleted your original post but I hope this explanation that I was just posting when you deleted the topic would be helpful; not only for you but for future readers.

Variance is probably one of the most complex yet most useful topics in Scala. I hope that after this explanation the concept becomes clearer.

First let’s try to understand what the current signature means:

Intutive explanation

sealed trait List[+A] {
  def add[B >: A](elem: B): List[B]
}

In this example, if you add something to a List then elem should be:

  • Of type A - In this case, it returns a List[A]
  • Of any subtype of A - In this case, the element gets upcasted to A, and the return is still a List[A]
    (Actually, the previous case and this one are the same)
  • Or any other type C - In this case, the compiler will find a new type B which is the LUB (least upper bound) between A & C, then you can think that the whole original list gets upcasted to a List[B] and the new element is also upcasted to B and finally the return will be another List[B].
    (Because Any is just a supertype of everything, in the worst case the result will be a List[Any]).

Formal explanation

If we tried to define add like this:

sealed trait List[+A] {
  def add(elem: A): List[A]
}

The code will not compile because:

The parameter elem in prepend is of type A , which we declared covariant. This doesn’t work because functions are contravariant in their parameter types.
– Reference

In other words, since A is covariant with respect to List then it can’t be used as an argument of a method because those are contravariant.
Thus, in order to fix it, we must add a new type parameter B But, to be able to successfully implement the method we end up adding the constraint that B >: A

But why?

The reason why this is the case is actually quite simple.
Since we declared List[+A] so A is covariant with respect to List it means that I can always pass a List[Dog] where a List[Pet] is expected; because Dog <: Pet then List[Dog] <: List[Pet]

Now, if we think about it, it means that I can always add a Pet to a List[Dog] right?
Because I can always do the upcast route:

val dogs: List[Dog] =???
val pet: Pet = ???

// Why would this not compile?
dogs.add(pet)

// When this should compile?
val pets: List[Pet] = dogs
pets.add(pet)

Similarly, I can always add a Cat to a List[Dog] because Cat <: Pet and the Liskov principle should be held!

val dogs: List[Dog] =???
val cat: Cat = ???

// Why would this not compile?
dogs.add(cat)

// When this should compile?
val pets: List[Pet] = dogs
val pet: Pet = cat
pets.add(pet)

And, if you see the expected return type of the longer routes is List[Pet] that is why if you add a Cat to a List[Dog] you get back a List[Pet]; because the compiler automatically does for us what I just did manually, finding the LUB and doing the proper upcasting.

In conclusion, add must work for any supertype of A because I can always upcast the List and it should keep working to guarantee the Liskov principle and its own covariance.

Note, if List would have been invariant then add would only accept elements of type A, just like Array.update

1 Like
2

Hey,

thanks for your explanation, and sorry that I deleted my post just as you apparently wrote a very wholesome answer. The reason I deleted my post is that I in fact understood the underlying issue by myself. However, I still really appreciate your answer.

The thing that I was missing was the return type of the “add”/“prepend” function. Coming from other languages and currently being a Dart developer (where all generic types are always covariant and the parameter of the add function would be invariant), I just did not expect a method “List[T].add()” to have any other return type then “List[T]”. In most of the languages I know, “List[T].add” would have a return type of void, and just alter the list.

And to be fair, the code on the Language Tour Page looking like this…

val africanSwallowList = ListNode[AfricanSwallow](AfricanSwallow(), Nil())
val birdList: Node[Bird] = africanSwallowList
birdList.prepend(EuropeanSwallow())

… where the return value of prepend is ignored does not really emphasise the importance of the return value here.

Thank’s very much for your clarification, I hope it will help others struggling with

1 Like
3

Variance is a tricky thing so nice that you help people out with this. A question: Shouldn’t this code in your “Intuitive explanation”…

sealed trait List[+A] {
  def add[B >: A](elem: A): List[A]
}

rather be like this so that the returning list can vary:

sealed trait List[+A] {
  def add[B >: A](elem: B): List[B]
}

or am I missing something?

4

As Scala encourages a functional programming style, the default collections are immutable, so a void return type would not work.

If you look at the collections in the standard library, you’ll also note, that the methods for adding elements to mutable collections are also named slightly different: While some mutable collections like e.g. Buffer have a prepend method, the immutable List only has prepended (which also exists on the mutable collections, but also returns a new copy with the prepended element instead of mutating). As a rule of thumb, if the method is using a past-tense form, it usually returns a copy instead of mutating the collection.

1 Like
5

Nop, you are right!
That is what happens when you copy & paste code :sweat_smile:

I just fixed it.

6

Cool. Copy paste is deceptive :slight_smile:
But: Also, elem should be of type B?
And I think you need to adapt the text in the bullet list…

7

I am going to pretend I didn’t make that mistake… twice.

Uhm, I rather not. My idea with the cases of the bullet list is to explain how the code works in each case and the first two are, IHMO, the natural ones. The cases on which most people think initially so they don’t see the point of B so that is why I use A here to show that they understanding is correct, they are just missing more context.

8

I am going to pretend I didn’t make that mistake… twice.

We should “compile all the things”[trademark]. :exploding_head:

The cases on which most people think initially so they don’t see the point of B so that is why I use A here

Ok yeah, I see. It reads well if you assume that you pass an elem with some type and you discuss that type in relation to the A in a concrete List[A]…

1 Like
9

Found another risk for misinterpretation: you write A & C but people might go down the trail of Scala 3’s intersection types… so perhaps, instead of "between A & C" write something like “has both A and C as subtypes”. (Now I’m done nit-picking; sorry :slight_smile: )

1 Like
10

I am planning on creating a blog soon and I will add this as a post so I will review all feedback you (or anyone else) may have by that time! :smiley: