Code Examples for

Programming in Scala, Fourth Edition

Return to chapter index

16 Working with Lists

Sample run of chapter's interpreter examples

16.1 List literals


// In file working-with-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 working-with-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 working-with-lists/Misc.scala // List() is also of type List[String]! val xs: List[String] = List()

16.3 Constructing lists


// In file working-with-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 working-with-lists/Misc.scala val nums = 1 :: 2 :: 3 :: 4 :: Nil

16.4 Basic operations on lists


scala> Nil.head java.util.NoSuchElementException: head of empty list
// In file working-with-lists/InsertionSort1.scala def isort(xs: List[Int]): List[Int] = if (xs.isEmpty) Nil else insert(xs.head, isort(xs.tail)) 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 working-with-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 working-with-lists/Misc.scala xs ::: ys ::: zs
// In file working-with-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 working-with-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 xs.reverse.head equals xs.last xs.reverse.last equals xs.head
// In file working-with-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>:8: error: No implicit view available from Int => scala.collection.IterableOnce[B]. List(1, 2, 3).flatten ^
scala> abcde.indices zip abcde res17: scala.collection.immutable.IndexedSeq[(Int, Char)] = Vector((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] = <iterator>
scala> it.next res29: Char = a scala> it.next res30: Char = b
// In file working-with-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[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 working-with-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[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[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 = xs.foldLeft(0)(_ + _) sum: (xs: List[Int])Int
scala> def product(xs: List[Int]): Int = xs.foldLeft(1)(_ * _) product: (xs: List[Int])Int
scala> words.foldLeft("")(_ + " " + _) res49: String = " the quick brown fox"
scala> words.tail.foldLeft(words.head)(_ + " " + _) res50: String = the quick brown fox
def flattenLeft[T](xss: List[List[T]]) = xss.foldLeft(List[T]())(_ ::: _) def flattenRight[T](xss: List[List[T]]) = xss.foldRight(List[T]())(_ ::: _)
scala> def flattenRight[T](xss: List[List[T]]) = | xss.foldRight(List())(_ ::: _) <console>:8: error: type mismatch; found : List[T] required: List[Nothing] xss.foldRight(List())(_ ::: _) ^
def reverseLeft[T](xs: List[T]) = xs.foldLeft(\startValue)(\operation)
// In file working-with-lists/Reverse2.scala def reverseLeft[T](xs: List[T]) = xs.foldLeft(List[T]()) { (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[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[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) zip List(3, 4, 5)). map { case (x, y) => x * y } res63: List[Int] = List(30, 80)
scala> (List(10, 20) lazyZip List(3, 4, 5)).map(_ * _) res63: List[Int] = List(30, 80)
scala> (List("abc", "de") lazyZip List(3, 2)). | forall(_.length == _) res64: Boolean = true scala> (List("abc", "de") lazyZip List(3, 2)). | 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.foldRight(List[T]())(_ ::: _)
xs.foldRight(z)(op)
xss.foldRight(List())(_ ::: _) // this won't compile
(List[T], List[Nothing]) => List[Nothing]

16.11 Exercises

16.12 Conclusion

For more information about Programming in Scala, Fourth Edition (the "Stairway Book"), please visit:

http://www.artima.com/shop/programming_in_scala_4ed

and:

http://booksites.artima.com/programming_in_scala_4ed

Copyright © 2007-2019 Artima, Inc. All rights reserved.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.