Review

Subtype relationship S <: T
Java generics: type erasure, wildcards
Type erasure: type parameters erased to bound (usually Object)
Wildcards: Solve “variance” issues when converting between G<S> and G<T>, where S <:T

ActiveLecture.org Warm-up exercise: Explain the wildcard in the Collections.fill method.

Scala Generics

[] instead of <>, e.g. Array[T]
Type erasure (for compatibility with Java)
Type bounds
No wildcards
Variance annotations

Type Bounds

trait TreeSet[T <: Ordered[T]]
T must be a subtype of Ordered[T]
Like <T extends Comparable<T>> in Java
Technical problem, particularly when using Java types: Java String does not implement Scala Ordered[String]
There is an implicit conversion from String to RichString which does
Use <% instead of <: if you want to allow conversions
T <% Ordered[T] means that T must be convertible to a subtype of Ordered[T]

Variance Annotations

By default, generic types are invariant, just like in Java. That is, no relationship between G[S] and G[T]
Ex. No relationship between Array[Employee] and Array[Person]
Not convenient, but not fatal. May have to make new array and shovel elements across
Can declare covariance:
```
class List[+T]
```
Now List[Employee] <: List[Manager]
In general, G[+T] means that S <: T ⇒ G[S] <: G[T]
Similar, contravariance
```
trait Comparable[-T]
```

Immutable List Example

abstract class List[+T] {
  def isEmpty : Boolean
  def head : T 
  def tail : List[T]
}

case class EmptyList[T]() extends List[T] {
  override def isEmpty : Boolean = true
  override def head = error("No head")
  override def tail = error("No tail")
}

case class NonEmptyList[T](hd : T, tl : List[T]) extends List[T] {
  override def isEmpty : Boolean = false
  override def head = hd
  override def tail = tl
}

Immutable List Example

Note that the list has no mutator—no issue with storing a bad value

If you add a bad value, you just get a list of a weaker type

scala> val foo = NonEmptyList("foo", EmptyList[String]())
foo: NonEmptyList[String] = NonEmptyList(foo,EmptyList())

scala> val bar = NonEmptyList(1, foo)
bar: NonEmptyList[Any] = NonEmptyList(1,NonEmptyList(foo,EmptyList()))

Positional Safety Checks

Problem with covariance: stores
Java arrays: Array store exception
Java wildcards: ? extends T allows loads and blocks stores

But stores are not the only problem

class BadStack extends Stack[Double] { 
   override def push(e : Double) = { super.push(Math.sqrt(e)) } 
}

Of course BadStack <: Stack[Double]

Is BadStack[Double] <: Stack[AnyRef]? It better not be:

Stack[AnyRef] bad = new BadStack(); 
bad.push("Yikes!"); // calls Math.sqrt("Yikes!")

Scala: Cannot use covariant T in “contravariant positions”

Ex. Can't have parameters of covariant T

class Stack[+T] {
   def pop() : T = ... // OK
   def push(newValue : T) { ... } // ERROR--T is parameter type
   def isEmpty = ...
}

Lower Bounds

Can fix push variance problem by making push into a generic method

class Stack[+T] {
  def push[N :> T](newValue : N) : Stack[N] = new NonEmptyStack[N](newValue, this)
  ...
}

T no longer appears as a parameter type of push (parameter is N)
Lower bound is a covariant position
Reasonable behavior: Push a supertype object, and you get a more general stack
Now you can't override push in BadStack

Conclusion

Lab shows how to use bounds, variance annotations for most common cases
Scala is simpler for immutable collections
For mutable collections, a bit more complex than Java wildcards
C# will have support for variance in version 4.0
Still active area of research