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 implementing-lists/Misc.scala

  package scala.collection.immutable
  sealed abstract class List[+A] {


  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 implementing-lists/Misc.scala

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


// In file implementing-lists/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 implementing-lists/Misc.scala

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


// In file implementing-lists/Misc.scala

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

    override def isEmpty: Boolean = false
  }


// In file implementing-lists/Misc.scala

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


// In file implementing-lists/Misc.scala

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


// In file implementing-lists/Misc.scala

  def map[B](f: A => B): List[B] =
    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@e885c6a)

  scala> val fruits = new Orange :: apples
  fruits: List[Fruit] = List(Orange@3f51b349, Apple@e885c6a)


  def ::[B >: A](x: B): List[B] = new scala.::(x, this)


// In file implementing-lists/Misc.scala

  def ::[B >: A](x: B): List[B] = new ::(x, this)


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


// In file implementing-lists/Misc.scala

    def :::[B >: A](prefix: List[B]): List[B] = 
      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 implementing-lists/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 implementing-lists/Misc.scala

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


// In file implementing-lists/Misc.scala

  import scala.collection.mutable.ListBuffer


// In file implementing-lists/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[B](f: A => B): List[B] = {
  if (this eq Nil) Nil else {
    val h = new ::[B](f(head), Nil)
    var t: ::[B] = h
    var rest = tail
    while (rest ne Nil) {
      val nx = new ::(f(rest.head), Nil)
      t.next = nx
      t = nx
      rest = rest.tail
    }
    h
  }
}


t.next = nx


// In file implementing-lists/Misc.scala

final case class :: [A](override val head: A,
    private[scala] var next: List[A]) extends List[A] {

  def isEmpty: Boolean = false
  def tail: List[A] = next
}


// In file implementing-lists/Misc.scala

  package scala.collection.mutable
  class ListBuffer[A] extends Buffer[A] {
    private var first: List[A] = Nil
    private var last0: ::[A] = null
    private var aliased: Boolean = false

    ...


// In file implementing-lists/Misc.scala

override def toList: List[A] = {
  aliased = nonEmpty
  first
}


def addOne(elem: A): this.type = {
  if (aliased) copyElems()
  val last1 = new ::[A](elem, Nil)
  if (first.isEmpty) first = last1 else last0.next = last1
  last0 = last1
  this
}


  

22.4 Functional on the outside

// In file implementing-lists/Misc.scala

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


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


  

22.5 Conclusion