Return to chapter index

19 Type Parameterization

Sample run of chapter's interpreter examples

• 19.1 Functional queues
• 19.2 Information hiding
• 19.3 Variance annotations
• 19.4 Checking variance annotations
• 19.5 Lower bounds
• 19.6 Contravariance
• 19.7 Object private data
• 19.8 Upper bounds
• 19.9 Conclusion

19.1 Functional queues

  scala> val q = Queue(1, 2, 3)
  q: Queue[Int] = Queue(1, 2, 3)

  scala> val q1 = q append 4
  q1: Queue[Int] = Queue(1, 2, 3, 4)

  scala> q
  res0: Queue[Int] = 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 append(x: T) = new 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 append(x: T) = new 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)
        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 append(x: T) = 
      new Queue(leading, x :: trailing)
  }


  

19.2 Information hiding

// In file type-parameterization/Queues4.scala

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


  scala> new Queue(List(1, 2), List(3))
  <console>:6: error: constructor Queue cannot be accessed in 
    object $iw
         new Queue(List(1, 2), List(3))
         ^


  def this() = this(Nil, Nil) 


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


// In file type-parameterization/Queues4.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 append(x: T): Queue[T]
  }

  object Queue {

    def apply[T](xs: T*): Queue[T] = 
      new 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)
          new QueueImpl(trailing.reverse, Nil)
        else 
          this

      def head: T = mirror.leading.head

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

      def append(x: T) = 
        new QueueImpl(leading, x :: trailing)
    }
  }


  

19.3 Variance annotations

  scala> def doesNotCompile(q: Queue) {}
  <console>:5: error: trait Queue takes type parameters
         def doesNotCompile(q: Queue) {}
                            ^


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


  trait Queue[+T] { ... }


  trait Queue[-T] { ... } 


// In file type-parameterization/Misc.scala

  class Cell[T](init: T) {
    private[this] 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 


  Cell.scala:7: error: covariant type T occurs in
  contravariant position in type T of value x
     def set(x: T) = current = 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")
  a1: Array[java.lang.String] = Array(abc)

  scala> val a2: Array[Any] = a1
  <console>:5: error: type mismatch;
   found   : Array[java.lang.String]
   required: Array[Any]
         val a2: Array[Any] = a1
                              ^


  scala> val a2: Array[Object] =
       |   a1.asInstanceOf[Array[Object]]
  a2: Array[java.lang.Object] = Array(abc)


  

19.4 Checking variance annotations

  class StrangeIntQueue extends Queue[Int] {
    override def append(x: Int) = {
      println(Math.sqrt(x))
      super.append(x)
    }
  }


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


  class Queue[+T] {
    def append(x: T) = 
     ...
  }


  Queues.scala:11: error: covariant type T occurs in
  contravariant position in type T of value x
    def append(x: T) = 
               ^


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


  

19.5 Lower bounds

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


  

19.6 Contravariance

// In file type-parameterization/Misc.scala

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


// 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(
     new Book("Programming in Scala"),
     new Book("Walden")
   )
 def printBookList(info: Book => AnyRef) {
   for (book <- books) println(info(book))
 }
}

object Customer extends Application {
 def getTitle(p: Publication): String = p.title
 Library.printBookList(getTitle)
}


  Library.printBookList(getTitle)


 class Queue[+T] private (
   private[this] var leading: List[T], 
   private[this] var trailing: List[T]
 ) {

   private def mirror() = 
     if (leading.isEmpty) {
       while (!trailing.isEmpty) {
         leading = trailing.head :: leading
         trailing = trailing.tail
       }
     }

   def head: T = { 
     mirror()
     leading.head 
   }

   def tail: Queue[T] = { 
     mirror()
     new Queue(leading.tail, trailing) 
   }

   def append[U >: T](x: U) = 
     new Queue[U](leading, x :: trailing)
 }


  

19.7 Object private data

  Queues.scala:1: error: covariant type T occurs in 
  contravariant position in type List[T] of parameter of
  setter leading_=
  class Queue[+T] private (private var leading: List[T],
                                       ^
  Queues.scala:1: error: covariant type T occurs in 
  contravariant position in type List[T] of parameter of
  setter trailing_=
                           private var trailing: List[T]) {
                                       ^


  

19.8 Upper bounds

  scala> val robert = new Person("Robert", "Jones")
  robert: Person = Robert Jones

  scala> val sally = new Person("Sally", "Smith")
  sally: Person = Sally Smith

  scala> robert < sally
  res0: Boolean = 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)
        lastNameComparison
      else
        firstName.compareToIgnoreCase(that.firstName)
    }

    override def toString = 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) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }
    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(orderedMergeSort(ys), orderedMergeSort(zs))
    }
  }


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


  scala> val sortedPeople = orderedMergeSort(people)
  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))
                           ^


  

19.9 Conclusion