Return to chapter index

22 Implementing Lists

Sample run of chapter's interpreter examples

• 22.1 The List class in principle
• 22.2 The ListBuffer class
• 22.3 The List class in practice
• 22.4 Functional on the outside
• 22.5 Conclusion

22.1 The List class in principle

// In file list-impl/Misc.scala

  package scala
  abstract class List[+T] {


  scala> val xs = List(1, 2, 3)
  xs: List[Int] = List(1, 2, 3)

  scala> var ys: List[Any] = xs
  ys: List[Any] = List(1, 2, 3)


// In file list-impl/Misc.scala

    def isEmpty: Boolean
    def head: T
    def tail: List[T]


// In file list-impl/Misc.scala

  case object Nil extends List[Nothing] {
    override def isEmpty = true
    def head: Nothing =
      throw new NoSuchElementException("head of empty list")
    def tail: List[Nothing] =
      throw new NoSuchElementException("tail of empty list")
  }


// In file list-impl/Misc.scala

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


// In file list-impl/Misc.scala

  final case class ::[T](head: T, tail: List[T])
      extends List[T] {

    override def isEmpty: Boolean = false
  }


// In file list-impl/Misc.scala

  def length: Int = 
    if (isEmpty) 0 else 1 + tail.length


// In file list-impl/Misc.scala

  def drop(n: Int): List[T] = 
    if (isEmpty) Nil
    else if (n <= 0) this
    else tail.drop(n - 1)


// In file list-impl/Misc.scala

  def map[U](f: T => U): List[U] =
    if (isEmpty) Nil
    else f(head) :: tail.map(f)


  abstract class Fruit 
  class Apple extends Fruit
  class Orange extends Fruit


  scala> val apples = new Apple :: Nil
  apples: List[Apple] = List(Apple@585fa9)

  scala> val fruits = new Orange :: apples
  fruits: List[Fruit] = List(Orange@cd6798, Apple@585fa9)


  def ::[U >: T](x: U): List[U] = new scala.::(x, this)


// In file list-impl/Misc.scala

  def ::[U >: T](x: U): List[U] = new ::(x, this)


  // A thought experiment (which wouldn't work)
  def ::(x: T): List[T] = new scala.::(x, this)


// In file list-impl/Misc.scala

    def :::[U >: T](prefix: List[U]): List[U] = 
      if (prefix.isEmpty) this
      else prefix.head :: prefix.tail ::: this


  prefix.head :: prefix.tail ::: this
    equals  (because  :: and  ::: are right-associative)

  prefix.head :: (prefix.tail ::: this)
    equals  (because  :: binds to the right)

  (prefix.tail ::: this).::(prefix.head)
    equals  (because  ::: binds to the right)

  this.:::(prefix.tail).::(prefix.head)


  

22.2 The ListBuffer class

// In file list-impl/Misc.scala

  def incAll(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case x :: xs1 => x + 1 :: incAll(xs1)
  }


  for (x <- xs) // ??


// In file list-impl/Misc.scala

  var result = List[Int]()    // a very inefficient approach
  for (x <- xs) result = result ::: List(x + 1)
  result


// In file list-impl/Misc.scala

  import scala.collection.mutable.ListBuffer


// In file list-impl/Misc.scala

  val buf = new ListBuffer[Int]
  for (x <- xs) buf += x + 1
  buf.toList


  

22.3 The List class in practice

  final override def map[U](f: T => U): List[U] = {
    val b = new ListBuffer[U]
    var these = this
    while (!these.isEmpty) {
      b += f(these.head)
      these = these.tail
    }
    b.toList
  }


// In file list-impl/Misc.scala

  final case class ::[U](hd: U, 
      private[scala] var tl: List[U]) extends List[U] {

    def head = hd
    def tail = tl
    override def isEmpty: Boolean = false
  }


// In file list-impl/Misc.scala

  package scala.collection.immutable
  final class ListBuffer[T] extends Buffer[T] {
    private var start: List[T] = Nil
    private var last0: ::[T] = _
    private var exported: Boolean = false
    ...


// In file list-impl/Misc.scala

  override def toList: List[T] = {
    exported = !start.isEmpty
    start
  }


  override def += (x: T) {
    if (exported) copy()
    if (start.isEmpty) {
      last0 = new scala.::(x, Nil)
      start = last0
    } else {
      val last1 = last0
      last0 = new scala.::(x, Nil)
      last1.tl = last0
    }
  }


  

22.4 Functional on the outside

// In file list-impl/Misc.scala

  val ys = 1 :: xs
  val zs = 2 :: xs


  ys.drop(2).tail = Nil  // can't do this in Scala!


  

22.5 Conclusion