Code Examples for

Programming in Scala, Second Edition

Return to chapter index

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


scala> Nil.head java.util.NoSuchElementException: head of empty list
// In file 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 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 xs.reverse.head equals xs.last xs.reverse.last equals xs.head
// 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]

16.11 Exercises

16.12 Conclusion

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

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

and:

http://booksites.artima.com/programming_in_scala_2ed

Copyright © 2007-2010 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.