Teaching beginners simple GADTs without introducing variance

Dotty
1

Hello
I am working on Scala 3 training materials and finding it a bit tricky to teach a simple LinkedList enum without having to introduce variance first.

enum LinkedList[A]:
  case Empty
  case NonEmpty(a: A, tail: LinkedList[A])

That won’t compile unless I declare A as covariant or explicitly extending LinkedList[Nothing] on the Empty case.

I wonder what Scala instructors do? Shall I go with the extends hack or just introduce covariance at this early stage of the course?

1 Like
2

Another workaround I found is to declare Empty as a class

enum LinkedList[A]:
  case Empty()
  case NonEmpty(head: A, tail: LinkedList[A])

val l1 = LinkedList.Empty[Int]()

That’s probably more evil than the extends trick :slightly_smiling_face:

3

I think the one with a case object without covariance is simply incorrect. Even if you manually extend LinkedList[Nothing].

2 Likes
4

Yes, I just realised the compiler will start complaining when instantiating

[error] 39 |val l1 = LinkedList.NonEmpty(1, LinkedList.NonEmpty(2, LinkedList.NonEmpty(3, LinkedList.Empty)))
[error] | ^^^^^^^^^^^^^^^^
[error] |Found: (lesson3.LinkedList.Empty : lesson3.LinkedList[Nothing])
[error] |Required: lesson3.LinkedList[A]

I am inclined to bite the bullet and teach invariance, covariance, but not contravariance.

1 Like
5

Or just say “you need a plus here or it breaks, we’ll understand it later”

Contravariance is also easy if you use the right examples, for example functions. Why should it be delayed?

  • RubenVerg :heart:
2 Likes
6

Another option - what I’d do with my 11-year-olds - is to stay focused on the data structure lesson at hand and put off the puzzles of variance for another day. Something like:

enum LinkedList:
  case Empty()
  case NonEmpty(a: Any, tail: LinkedList)

However, it might be as much to explain “Don’t use Any after September,” as “You need a + here. I’ll explain why in October.”

3 Likes
7

Hi Tamer,

I actually realized about a week ago that I had this same in PinS 5ed. We added an enums chapter well before we explain covariance, but several unexplained plus signs were lurking quietly in the enum examples. I decided I will leave the plus signs in and add a footnote or callout that says the plus signs means covariance, which will be explained in section X.Y and in short means… Otherwise we’d need to twist our examples into pretzels to avoid covariance, or introduce enums way later than they deserve.

Bill

8

why? I find the example easy to understand and straight forward.

LinkedList.NonEmpty(1, LinkedList.NonEmpty(2, LinkedList.Empty()))
3 Likes