Study note of the chapter 22 of the book: Programming In Scala, 4th Edition.

Chapter 22 Implementing Lists

The List definition is similar to the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
sealed abstract class List[+A] {
  // three basic members
  def isEmpty: Boolean
  def head: A
  def tail: List[A]

  // other methods

  // Because List is covariant and the elemetn is used as an argument
  // the lower bound `[B >: A]` helps to make it a covariant type.
  def ::[B >: A](x: B): List[B] = new ::(x, this)
  def :::[B >: A](prefix: List[B]): List[B] =
    if (prefix.isEmpty) this
    else prefix.head :: (prefix.tail ::: this)

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

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

  override def toString() = "Nil"
}

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

  override def toString() = s"${head.toString} :: ${tail.toString}"
}

One probelm of this implementation is that most methods use recursive functions and most of them are not tail-recurisve. Each recursive call required a new stack frame thus it is slow and consumes a lot of resources.

A better functional on the outside approach is to use var tail or to use a ListBuffer that both the append and toList operations take constant time. These methods uses loop instead of non-tail recursive implementations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

  final override def map[B](f: A => B): List[B] = {
    if (this eq Nil) Nil
    else {
      val h: ::[B] = 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
    }
  }
}