## 16 Working with Lists

Sample run of chapter's interpreter examples

### 16.1 List literals

```
// In file lists/Misc.scala

val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 =
List(
List(1, 0, 0),
List(0, 1, 0),
List(0, 0, 1)
)
val empty = List()

```

### 16.2 The List type

```
// In file lists/Misc.scala

val fruit: List[String] = List("apples", "oranges", "pears")
val nums: List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] =
List(
List(1, 0, 0),
List(0, 1, 0),
List(0, 0, 1)
)
val empty: List[Nothing] = List()

// In file lists/Misc.scala

// List() is also of type List[String]!
val xs: List[String] = List()

```

### 16.3 Constructing lists

```
// In file lists/Misc.scala

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums  = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
(0 :: (1 :: (0 :: Nil))) ::
(0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil

// In file lists/Misc.scala

val nums = 1 :: 2 :: 3 :: 4 :: Nil

```

### 16.4 Basic operations on lists

```
java.util.NoSuchElementException: head of empty list

// In file lists/InsertionSort1.scala

def isort(xs: List[Int]): List[Int] =
if (xs.isEmpty) Nil

def insert(x: Int, xs: List[Int]): List[Int] =
if (xs.isEmpty || x <= xs.head) x :: xs
else xs.head :: insert(x, xs.tail)

```

### 16.5 List patterns

```
scala> val List(a, b, c) = fruit
a: String = apples
b: String = oranges
c: String = pears

scala> val a :: b :: rest = fruit
a: String = apples
b: String = oranges
rest: List[String] = List(pears)

// In file lists/InsertionSort2.scala

def isort(xs: List[Int]): List[Int] = xs match {
case List()   => List()
case x :: xs1 => insert(x, isort(xs1))
}

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
case List()  => List(x)
case y :: ys => if (x <= y) x :: xs
else y :: insert(x, ys)
}

```

### 16.6 First-order methods on class List

```
scala> List(1, 2) ::: List(3, 4, 5)
res0: List[Int] = List(1, 2, 3, 4, 5)

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

scala> List(1, 2, 3) ::: List(4)
res2: List[Int] = List(1, 2, 3, 4)

// In file lists/Misc.scala

xs ::: ys ::: zs

// In file lists/Misc.scala

xs ::: (ys ::: zs)

def append[T](xs: List[T], ys: List[T]): List[T]

def append[T](xs: List[T], ys: List[T]): List[T] =
xs match {
case List() => // ??
case x :: xs1 => // ??
}

case List() => ys

// In file lists/Misc.scala

def append[T](xs: List[T], ys: List[T]): List[T] =
xs match {
case List() => ys
case x :: xs1 => x :: append(xs1, ys)
}

scala> List(1, 2, 3).length
res3: Int = 3

scala> val abcde = List('a', 'b', 'c', 'd', 'e')
abcde: List[Char] = List(a, b, c, d, e)

scala> abcde.last
res4: Char = e

scala> abcde.init
res5: List[Char] = List(a, b, c, d)

scala> List().init
java.lang.UnsupportedOperationException: Nil.init
at scala.List.init(List.scala:544)
at ...

scala> List().last
java.util.NoSuchElementException: Nil.last
at scala.List.last(List.scala:563)
at ...

scala> abcde.reverse
res6: List[Char] = List(e, d, c, b, a)

scala> abcde
res7: List[Char] = List(a, b, c, d, e)

xs.reverse.reverse  equals  xs

xs.reverse.init  equals  xs.tail.reverse
xs.reverse.tail  equals  xs.init.reverse

// In file lists/Reverse1.scala

def rev[T](xs: List[T]): List[T] = xs match {
case List() => xs
case x :: xs1 => rev(xs1) ::: List(x)
}

scala> abcde take 2
res8: List[Char] = List(a, b)

scala> abcde drop 2
res9: List[Char] = List(c, d, e)

scala> abcde splitAt 2
res10: (List[Char], List[Char]) = (List(a, b),List(c, d, e))

scala> abcde apply 2 // rare in Scala
res11: Char = c

scala> abcde(2)      // rare in Scala
res12: Char = c

scala> abcde.indices
res13: scala.collection.immutable.Range =
Range(0, 1, 2, 3, 4)

scala> List(List(1, 2), List(3), List(), List(4, 5)).flatten
res14: List[Int] = List(1, 2, 3, 4, 5)
scala> fruit.map(_.toCharArray).flatten
res15: List[Char] = List(a, p, p, l, e, s, o, r, a, n, g, e,
s, p, e, a, r, s)

scala> List(1, 2, 3).flatten
<console>:5: error: could not find implicit value for
parameter asTraversable: (Int) => Traversable[B]
List(1, 2, 3).flatten
^

scala> abcde.indices zip abcde
res17: scala.collection.immutable.IndexedSeq[(Int, Char)] =
IndexedSeq((0,a), (1,b), (2,c), (3,d), (4,e))

scala> val zipped = abcde zip List(1, 2, 3)
zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))

scala> abcde.zipWithIndex
res18: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3),
(e,4))

scala> zipped.unzip
res19: (List[Char], List[Int]) =
(List(a, b, c),List(1, 2, 3))

scala> abcde.toString
res20: String = List(a, b, c, d, e)

scala> abcde mkString ("[", ",", "]")
res21: String = [a,b,c,d,e]

scala> abcde mkString ""
res22: String = abcde

scala> abcde.mkString
res23: String = abcde

scala> abcde mkString ("List(", ", ", ")")
res24: String = List(a, b, c, d, e)

scala> val buf = new StringBuilder
buf: StringBuilder =

scala> abcde addString (buf, "(", ";", ")")
res25: StringBuilder = (a;b;c;d;e)

scala> val arr = abcde.toArray
arr: Array[Char] = Array(a, b, c, d, e)

scala> arr.toList
res26: List[Char] = List(a, b, c, d, e)

xs copyToArray (arr, start)

scala> val arr2 = new Array[Int](10)
arr2: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

scala> List(1, 2, 3) copyToArray (arr2, 3)

scala> arr2
res28: Array[Int] = Array(0, 0, 0, 1, 2, 3, 0, 0, 0, 0)

scala> val it = abcde.iterator
it: Iterator[Char] = non-empty iterator

scala> it.next
res29: Char = a

scala> it.next
res30: Char = b

// In file lists/Misc.scala

def msort[T](less: (T, T) => Boolean)
(xs: List[T]): List[T] = {

def merge(xs: List[T], ys: List[T]): List[T] =
(xs, ys) match {
case (Nil, _) => ys
case (_, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (less(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}

val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs))
}
}

scala> msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
res31: List[Int] = List(1, 3, 5, 7)

scala> val intSort = msort((x: Int, y: Int) => x < y) _
intSort: (List[Int]) => List[Int] = <function1>

scala> val reverseIntSort = msort((x: Int, y: Int) => x > y) _
reverseIntSort: (List[Int]) => List[Int] = <function>

scala> val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)
mixedInts: List[Int] = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)

scala> intSort(mixedInts)
res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> reverseIntSort(mixedInts)
res1: List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

```

### 16.7 Higher-order methods on class List

```
scala> List(1, 2, 3) map (_ + 1)
res32: List[Int] = List(2, 3, 4)

scala> val words = List("the", "quick", "brown", "fox")
words: List[java.lang.String] = List(the, quick, brown, fox)

scala> words map (_.length)
res33: List[Int] = List(3, 5, 5, 3)

scala> words map (_.toList.reverse.mkString)
res34: List[String] = List(eht, kciuq, nworb, xof)

scala> words map (_.toList)
res35: List[List[Char]] = List(List(t, h, e), List(q, u, i,
c, k), List(b, r, o, w, n), List(f, o, x))

scala> words flatMap (_.toList)
res36: List[Char] = List(t, h, e, q, u, i, c, k, b, r, o, w,
n, f, o, x)

scala> List.range(1, 5) flatMap (
|   i => List.range(1, i) map (j => (i, j))
| )
res37: List[(Int, Int)] = List((2,1), (3,1), (3,2), (4,1),
(4,2), (4,3))

// In file lists/Misc.scala

for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)

scala> var sum = 0
sum: Int = 0

scala> List(1, 2, 3, 4, 5) foreach (sum += _)

scala> sum
res39: Int = 15

scala> List(1, 2, 3, 4, 5) filter (_ % 2 == 0)
res40: List[Int] = List(2, 4)

scala> words filter (_.length == 3)
res41: List[java.lang.String] = List(the, fox)

scala> List(1, 2, 3, 4, 5) partition (_ % 2 == 0)
res42: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

scala>  List(1, 2, 3, 4, 5) find (_ % 2 == 0)
res43: Option[Int] = Some(2)

scala>  List(1, 2, 3, 4, 5) find (_ <= 0)
res44: Option[Int] = None

scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0)
res45: List[Int] = List(1, 2, 3)

scala> words dropWhile (_ startsWith "t")
res46: List[java.lang.String] = List(quick, brown, fox)

scala> List(1, 2, 3, -4, 5) span (_ > 0)
res47: (List[Int], List[Int]) = (List(1, 2, 3),List(-4, 5))

scala> def hasZeroRow(m: List[List[Int]]) =
|   m exists (row => row forall (_ == 0))
hasZeroRow: (m: List[List[Int]])Boolean

scala> hasZeroRow(diag3)
res48: Boolean = false

scala> def sum(xs: List[Int]): Int = (0 /: xs) (_ + _)
sum: (xs: List[Int])Int

scala> def product(xs: List[Int]): Int = (1 /: xs) (_ * _)
product: (xs: List[Int])Int

scala>  ("" /: words) (_ +" "+ _)
res49: java.lang.String =  the quick brown fox

scala> (words.head /: words.tail)  (_ +" "+ _)
res50: java.lang.String = the quick brown fox

def flattenLeft[T](xss: List[List[T]]) =
(List[T]() /: xss) (_ ::: _)

def flattenRight[T](xss: List[List[T]]) =
(xss :\ List[T]()) (_ ::: _)

scala> def flattenRight[T](xss: List[List[T]]) =
|     (xss :\ List()) (_ ::: _)
<console>:5: error: type mismatch;
found   : scala.List[T]
required: List[Nothing]
(xss :\ List()) (_ ::: _)
^

def reverseLeft[T](xs: List[T]) = (\startValue /: xs)(\operation)

// In file lists/Reverse2.scala

def reverseLeft[T](xs: List[T]) =
(List[T]() /: xs) {(ys, y) => y :: ys}

scala> List(1, -3, 4, 2, 6) sortWith (_ < _)
res51: List[Int] = List(-3, 1, 2, 4, 6)

scala> words sortWith (_.length > _.length)
res52: List[java.lang.String] = List(quick, brown, the, fox)

```

### 16.8 Methods of the List object

```
scala> List.apply(1, 2, 3)
res53: List[Int] = List(1, 2, 3)

scala> List.range(1, 5)
res54: List[Int] = List(1, 2, 3, 4)

scala> List.range(1, 9, 2)
res55: List[Int] = List(1, 3, 5, 7)

scala> List.range(9, 1, -3)
res56: List[Int] = List(9, 6, 3)

scala> List.fill(5)('a')
res57: List[Char] = List(a, a, a, a, a)

scala> List.fill(3)("hello")
res58: List[java.lang.String] = List(hello, hello, hello)

scala> List.fill(2, 3)('b')
res59: List[List[Char]] = List(List(b, b, b), List(b, b, b))

scala> val squares = List.tabulate(5)(n => n * n)
squares: List[Int] = List(0, 1, 4, 9, 16)
scala> val multiplication = List.tabulate(5,5)(_ * _)
multiplication: List[List[Int]] = List(List(0, 0, 0, 0, 0),
List(0, 1, 2, 3, 4), List(0, 2, 4, 6, 8),
List(0, 3, 6, 9, 12), List(0, 4, 8, 12, 16))

scala> List.concat(List('a', 'b'), List('c'))
res60: List[Char] = List(a, b, c)

scala> List.concat(List(), List('b'), List('c'))
res61: List[Char] = List(b, c)

scala> List.concat()
res62: List[Nothing] = List()

```

### 16.9 Processing multiple lists together

```
scala> (List(10, 20), List(3, 4, 5)).zipped.map(_ * _)
res63: List[Int] = List(30, 80)

scala> (List("abc", "de"), List(3, 2)).zipped.
\|   forall(_.length == _)
res64: Boolean = true

scala> (List("abc", "de"), List(3, 2)).zipped.
\|   exists(_.length != _)
res65: Boolean = false

```

### 16.10 Understanding Scala's type inference algorithm

```
scala> msort((x: Char, y: Char) => x > y)(abcde)
res66: List[Char] = List(e, d, c, b, a)

scala> abcde sortWith (_ > _)
res67: List[Char] = List(e, d, c, b, a)

scala> msort(_ > _)(abcde)
<console>:12: error: missing parameter type for expanded
function ((x\$1, x\$2) => x\$1.\$greater(x\$2))
msort(_ > _)(abcde)
^

scala> msort[Char](_ > _)(abcde)
res68: List[Char] = List(e, d, c, b, a)

def msortSwapped[T](xs: List[T])(less:
(T, T) => Boolean): List[T] = {

// same implementation as msort,
// but with arguments swapped
}

scala> msortSwapped(abcde)(_ > _)
res69: List[Char] = List(e, d, c, b, a)

(xss :\ List[T]()) (_ ::: _)

(xs :\ z) (op)

(xss :\ List()) (_ ::: _)  // this won't compile

(List[T], List[Nothing]) => List[Nothing]

```