All the collections shown here are immutable.
Lists are linear, access to the first element is faster than accessing the middle of the list. A more evenly balanced access pattern is provided by Vectors:
Vectors and Lists are quite analogous and easily interchangeable.
val nums = Vector(1, 2, 3, -88)
val people = Vector("Bob", "James", "Peter")Instead of: x :: xs we have:
Vectors and Lists are both sub-classes of Seq which implements Iterable.
Array and String are very similar to Seq and support functions like foldLeft, filter or map but they don't share the same hierarchy because they come from Java.
Other collection class is Range:
val r: Range = 1 until 5 // 1, 2, 3, 4
val s: Range = 1 to 5 // 1, 2, 3, 4, 5
val t: Range = 1 to 10 by 3 // 1, 4, 7, 10
val u: Range = 6 to 1 by -2 // 6, 4, 2More Seq operations:
xs exists p // true if an element exists that fulfills p
xs forall p // true if all elements fulfill p
xs zip ys // creates a list of pairs drawing from xs and ys
xs.unzip // splits a list of pairs into two lists
xs.flatMap f // applies the collection-valued function to each
// element and concatenates the result
xs.sum
xs.product
xs.max
xs.minExample:
def isPrime(n: Int): Boolean = (2 until n) forall (x => n % x != 0)Example: find all the pairs of (1 <= i < n, 1 <= j < i) such that i + j is prime.
val n = 7 // upper limit
(1 until n).flatMap(i => (1 until i).map(j => (i, j))
.filter(pair => isPrime(pair._1 + pair._2))Introducing for-expressions:
case class Person(name: String, age: Int)
for (p <- persons if p.age > 20) yield p.name // list of names of all persons
// older than 20This is equivalent to:
persons filter (p => p.age > 20) map (p => p.name)Rewriting the original example using for-expressions:
val n= 7
for {
i <- 1 until n
j <- 1 until i
if (isPrime(i + j))
} yield (i, j)Another example:
def scalarProduct(xs: List[Int], ys: List[Int]): Int =
(for ((x, y) <- xs zip ys) yield x * y).sumSets are close to Seqs
val fruit = Set("apple", "orange", "banana")
val s = (1 to 6).toSet
s.map(_ + 2)
fruit filter (_.startsWith = "app")
s.nonEmptyDifferences between Sets and Seqs:
The eight queens problem:
Recursive algorithm:
def queens(n: Int): Set[List[Int]] = {
def placeQueens(k: Int): Set[List[Int]] =
if (k == 0) Set(List())
else
for {
queens <- placeQueens(k-1)
col <- 0 until n
if (isSafe(col, queens))
} yield col :: queens
def isSafe(col: Int, queens: List[Int]): Boolean = {
val row = queens.length
val queensWithRow = (row - 1 to 0 by -1) zip queens // List of pairs (r, c)
queensWithRow forall {
case (r, c) => (col != c) && (math.abs(col - c) != (row - r))
}
}
placeQueens(n)
}Maps associate keys to values.
val romanNumerals = Map("I" -> 1, "V" -> 5, "X" -> 10)
val capitalOfCountry = Map("US" -> "Washington", "Switzerland" -> "Bern")Maps are Iterables. Class Map[Key, Value] extends Iterable[(Key, Value)], so they support all operations that other collections do.
val countryOfCapital = capitalOfCountry map {
case (x, y) => (y, x) // reverse map
}The syntax key -> value is just another way of writing the pair (key, value).
Class Map[Key, Value] also extends the function type Key => Value, so maps can be used everywhere functions.
capitalOfCountry("US") // function call
capitalOfCountry("Andorra") // java.util.NoSuchElementException
capitalOfCountry get "US" // Some("Washington")
capitalOfCountry get "Andorra" // NoneThe result of get is an Option.
Option is a standard type in Scala:
trait Option[+A]
case class Some[+A](value: A) extends Option[A]
object None extends Option[Nothing]Options can be decomposed using pattern matching:
def showCapital(country: String) = capitalOfCountry.get(country) match {
case Some(capital) => capital
case None => "missing data"
}
showCapital("US") // Washington
showCapital("Andorra") // missing dataCollections can be sorted and grouped (like in SQL):
val fruit = List("apple", "pear", "orange", "pineapple")
fruit sortWith (_.length < _.length) // List(pear, apple, orange, pineapple)
fruit.sorted // List(apple, orange, pear, pineapple)
fruit groupBy (_.head) // Map( p -> List(pear, pineapple),
// o -> List(orange),
// a -> List(apple))
// (_.head) is a "discriminator" functionExample: modeling polynomials. Polynomials can be represented as maps from exponents to coefficients. For instance:
$$ x^3 - 2x + 5 $$
can be represented as:
Map(0 -> 5, 1 -> -2, 3 -> 1)We can encapsulate this in a class:
class Poly(val terms: Map[Int, Double]) {
def +(other: Poly): Poly = new Poly(terms ++ (other.terms map adjust))
def adjust(term: (Int, Double)): (Int, Double) = {
val (exp, coeff) = term
terms get exp match {
case Some(exp1, coeff1) => exp -> (coeff + coeff1)
case None => exp -> coeff
}
}
override def toString =
(for ((exp, coeff) <- terms.toList.sorted.reverse)
(yield coeff + "x^" + exp).mkString " + "
}
val p1 = new Poly(Map(1 -> 2.0, 3 -> 4.0, 5 -> 6.2))
val p2 = new Poly(Map(0 -> 3.0, 3 -> 7.0))
p1 + p2Maps can have default values:
val cap1 = capitalOfCountry withDefaultValue "<unknown>"
cap1("Andorra") // <unknown>Rewriting the Polynomials example with default values:
class Poly(val terms0: Map[Int, Double]) {
def this(bindings: (Int, Double)*) = this(bindings.toMap)
val terms = terms0 withDefaultValue 0.0
def +(other: Poly): Poly = new Poly(terms ++ (other.terms map adjust))
def adjust(term: (Int, Double)): (Int, Double) = {
val (exp, coeff) = term
exp -> (coeff + terms(exp))
}
override def toString =
(for ((exp, coeff) <- terms.toList.sorted.reverse)
(yield coeff + "x^" + exp).mkString " + "
}
val p1 = Poly(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)
val p2 = Poly(0 -> 3.0, 3 -> 7.0)
p1 + p2Notice the second constructor, using a varargs syntax **(Int, Double)* that simplifies the construction of Poly** objects.
The + operation can also be implemented using foldLeft
Example: generate all phone number mnemonics based on a dictionary.
We will implement a function translate(phoneNumber) that produces all phrases of words that can serve as mnemonics for the phone number.
val words = ... // dictionary, one word per line
val mnem = Map('2' -> "ABC", '3' -> "DEF", '4' -> "GHI",
'5' -> "JKL", '6' -> "MNO", '7' -> "PQRS",
'8' -> "TUV", '9' -> "WXYZ")
// invert the map to get a map of characters to digits
val charCode: Map[Char, Char] =
for ((digit, str) <- mnem; ltr <- str) yield ltr -> digit
// map a word to its code, e.g. "Java" -> "5282"
def wordCode(word: String): String = word.toUpperCase map charCode
// reverse map from digit strings to the words that represent them
// missing numbers will map to an empty sequence "1111" -> List()
val wordsForNum: Map[String, Seq[String]] = words groupBy wordCode
//finally, encoding the number
def encode(number: String): Set[List[String]] =
if (number.isEmpty) Set(List())
else {
for {
split <- 1 to number.length
word <- wordsForNum(number take split)
rest <- encode(number drop split)
} yield word :: rest
}.toSet
encode("4169535740")