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