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 } } }``````