Return to chapter index

18 Type Parameterization

Sample run of chapter's interpreter examples

• 18.1 Functional queues
• 18.2 Information hiding
• 18.3 Variance annotations
• 18.4 Checking variance annotations
• 18.5 Lower bounds
• 18.6 Contravariance
• 18.7 Upper bounds
• 18.8 Conclusion

18.1 Functional queues

  val q = Queue(1, 2, 3) // Queue(1, 2, 3)
  val q1 = q.enqueue(4)  // Queue(1, 2, 3, 4)
  q                      // Queue(1, 2, 3)


// In file type-parameterization/Queues1.scala

  class SlowAppendQueue[T](elems: List[T]): // Not efficient
    def head = elems.head
    def tail = new SlowAppendQueue(elems.tail)
    def enqueue(x: T) = SlowAppendQueue(elems ::: List(x))


// In file type-parameterization/Queues2.scala

  class SlowHeadQueue[T](smele: List[T]): // Not efficient
    // smele is elems reversed
    def head = smele.last
    def tail = new SlowHeadQueue(smele.init)
    def enqueue(x: T) = SlowHeadQueue(x :: smele)


// In file type-parameterization/Queues3.scala

  class Queue[T](
    private val leading: List[T], 
    private val trailing: List[T] 
  ):
    private def mirror = 
      if leading.isEmpty then
        new Queue(trailing.reverse, Nil)
      else
        this

    def head = mirror.leading.head

    def tail =
      val q = mirror 
      new Queue(q.leading.tail, q.trailing)

    def enqueue(x: T) = 
      new Queue(leading, x :: trailing)


  

18.2 Information hiding

// In file type-parameterization/Queues4.scala

  class Queue[T] private (
    private val leading: List[T],
    private val trailing: List[T]
  ) 


  scala> Queue(List(1, 2), List(3))
  1 |Queue(List(1, 2), List(3))
    |^^^^^
    |constructor Queue cannot be accessed as a member of
    |Queue from module class rs$line$4$.


  def this() = this(Nil, Nil) 


  def this(elems: T*) = this(elems.toList, Nil)


// In file type-parameterization/Queues3.scala

  object Queue:
    // constructs a queue with initial elements `xs'
    def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)


// In file type-parameterization/Queues5.scala

  trait Queue[T]:
    def head: T
    def tail: Queue[T]
    def enqueue(x: T): Queue[T]

  object Queue:

    def apply[T](xs: T*): Queue[T] = 
      QueueImpl[T](xs.toList, Nil)

    private class QueueImpl[T](
      private val leading: List[T],
      private val trailing: List[T]
    ) extends Queue[T]:

      def mirror = 
        if leading.isEmpty then
          QueueImpl(trailing.reverse, Nil)
        else 
          this

      def head: T = mirror.leading.head

      def tail: QueueImpl[T] =
        val q = mirror
        QueueImpl(q.leading.tail, q.trailing)

      def enqueue(x: T) = 
        QueueImpl(leading, x :: trailing)


  

18.3 Variance annotations

  scala> def doesNotCompile(q: Queue) = {}
  1 |def doesNotCompile(q: Queue) = {}
    |                      ^^^^^
    |                      Missing type parameter for Queue


  scala> def doesCompile(q: Queue[AnyRef]) = {}
  def doesCompile: (q: Queue[AnyRef]): Unit


  trait Queue[+T] { ... }


  trait Queue[-T] { ... } 


// In file type-parameterization/Misc.scala

  class Cell[T](init: T):
    private var current = init
    def get = current
    def set(x: T) =
      current = x


  val c1 = new Cell[String]("abc")
  val c2: Cell[Any] = c1
  c2.set(1)
  val s: String = c1.get 


  4 |    def set(x: T) =
    |            ^^^^
    |    covariant type T occurs in contravariant position
    |    in type T of value x


// In file type-parameterization/JavaArrays.java

  // this is Java
  String[] a1 = { "abc" };
  Object[] a2 = a1;
  a2[0] = new Integer(17);
  String s = a1[0];


  Exception in thread "main" java.lang.ArrayStoreException: 
  java.lang.Integer
          at JavaArrays.main(JavaArrays.java:8)


  void sort(Object[] a, Comparator cmp) { ... }


  scala> val a1 = Array("abc")
  val a1: Array[String] = Array(abc)

  scala> val a2: Array[Any] = a1
  1 |val a2: Array[Any] = a1
    |                     ^^
    |                     Found:    (a1 : Array[String])
    |                     Required: Array[Any]


  val a2: Array[Object] = a1.asInstanceOf[Array[Object]]


  

18.4 Checking variance annotations

  class StrangeIntQueue extends Queue[Int]:
    override def enqueue(x: Int) =
      println(math.sqrt(x))
      super.enqueue(x)


  val x: Queue[Any] = new StrangeIntQueue
  x.enqueue("abc")


  class Queue[+T]:
    def enqueue(x: T) = 
     ...


  17 |  def enqueue(x: T) =
     |              ^^^^
     |  covariant type T occurs in contravariant position
     |  in type T of value x


  abstract class Cat[-T, +U]:
    def meow[W-](volume: T-, listener: Cat[U+, T-]-)
      : Cat[Cat[U+, T-]-, U+]+


  

18.5 Lower bounds

  class Queue[+T] (private val leading: List[T],
      private val trailing: List[T]):
    def enqueue[U >: T](x: U) = 
      new Queue[U](leading, x :: trailing) // ...


  

18.6 Contravariance

// In file type-parameterization/Misc.scala

  trait OutputChannel[-T]:
    def write(x: T): Unit


// In file type-parameterization/Misc.scala

  trait Function1[-S, +T]:
    def apply(x: S): T


// In file type-parameterization/Customer.scala

class Publication(val title: String)
class Book(title: String) extends Publication(title)

object Library:
 val books: Set[Book] =
   Set(
     Book("Programming in Scala"),
     Book("Walden")
   )
 def printBookList(info: Book => AnyRef) =
   for book <- books do println(info(book))

object Customer:
 def getTitle(p: Publication): String = p.title
 def main(args: Array[String]): Unit =
   Library.printBookList(getTitle)


  Library.printBookList(getTitle)


  

18.7 Upper bounds

  val robert = new Person("Robert", "Jones")
  val sally = new Person("Sally", "Smith")
  robert < sally  // true


  class Person(val firstName: String, val lastName: String)
      extends Ordered[Person]:

    def compare(that: Person) =
      val lastNameComparison =
        lastName.compareToIgnoreCase(that.lastName)
      if lastNameComparison != 0 then
        lastNameComparison
      else
        firstName.compareToIgnoreCase(that.firstName)

    override def toString = s"firstName lastName"


  def orderedMergeSort[T <: Ordered[T]](xs: List[T]): List[T] =
    def merge(xs: List[T], ys: List[T]): List[T] =
      (xs, ys) match
        case (Nil, _) => ys
        case (_, Nil) => xs
        case (x :: xs1, y :: ys1) =>
          if x < y then x :: merge(xs1, ys)
          else y :: merge(xs, ys1)

    val n = xs.length / 2
    if n == 0 then xs
    else
      val (ys, zs) = xs.splitAt(n)
      merge(orderedMergeSort(ys), orderedMergeSort(zs))


  val people = List(
    Person("Larry", "Wall"),
    Person("Anders", "Hejlsberg"),
    Person("Guido", "van Rossum"),
    Person("Alan", "Kay"),
    Person("Yukihiro", "Matsumoto")
  )


  scala> val sortedPeople = orderedMergeSort(people)
  val sortedPeople: List[Person] = List(Anders Hejlsberg,
    Alan Kay, Yukihiro Matsumoto, Guido van Rossum, Larry Wall)


  scala> val wontCompile = orderedMergeSort(List(3, 2, 1))
  <console>:5: error: inferred type arguments [Int] do
     not conform to method orderedMergeSort's type
       parameter bounds [T <: Ordered[T]]
         val wontCompile = orderedMergeSort(List(3, 2, 1))
                           ^


  

18.8 Conclusion