Lists in Scala

As with most functional languages, lists play a big roll in Scala. Lists contains, among others, the following operations.

// List in Scala or homogenous, they are declared as List[T]
val names: List[String] = List("Arnold", "George", "Obama")

// Lists are constructed from two building blocks :: and Nil
assert(names == "Arnold" :: "George" :: "Obama" :: Nil)

// Gets the first element of a list
assert(names.head == "Arnold")

// Gets the rest of the list
assert(names.tail == "George" :: "Obama" :: Nil)

// Checks if the list is empty
assert(List().isEmpty)

Instead of using head and tail, pattern matching is commonly used.

def length(xs: List[T]): Int = xs match {
 case Nil => 0
 case x :: xs1 => 1 + length(xs1)
}

From these simple functions a flora of functions is built.

// List length
assert(names.length == 3)

// ::: appends two lists
val namesTwice = names ::: names
assert(namesTwice == List("Arnold", "George", "Obama", "Arnold", "George", "Obama"))

// last gets the last element
assert(names.last == "Obama")

// init gets all but the last
assert(names.init == "Arnold" :: "George" :: Nil)

// reverse reverses the list
assert(names.reverse == "Obama" :: "George" :: "Arnold" :: Nil)

// drop drops the first n items
assert(names.drop(2) == "Obama" :: Nil)

// take keeps the first n items
assert(names.take(1) == "Arnold" :: Nil)

// splitAt, does both take and drop at the same time, returning a tuple
assert(names.splitAt(1) == (List("Arnold"), List("George", "Obama")))

// indeces, gives my the indeces of the list
assert(names.indices == List(0, 1, 2))

// zip, zips two lists together
assert(names.zip(names.indices) == List(("Arnold", 0), ("George", 1), ("Obama", 2)))

// toString returns a list as String
assert(names.toString == "List(Arnold, George, Obama)")

// mkString, lets you join the string with a separator
assert(names.mkString("-") == "Arnold-George-Obama")

There are also a few functions for converting to and from lists.

val array = Array("Arnold", "George", "Obama")

// Convert the list to an Array
assert(names.toArray == array) // Equality does not work for arrays
java.lang.AssertionError: assertion failed
 at scala.Predef$.assert(Predef.scala:87)
...

// If we convert it back it works
assert(names.toArray.toList == names)

// We can also mutate the array with copyToArray
List("Hilary").copyToArray(array, 1)
assert(array.toList == List("Arnold", "Hilary", "Obama")) 

// elements will give me an iterator
val it = names.elements
assert (it.next == "Arnold")

Pretty slick, but now it is time for the good stuff, Higher Order Functions!

// map, converts from one list to another, notice the placeholder syntax (_)
assert(names.map(_.length) == List(6 ,6, 5))

// Get the first char of the words
assert(names.map(_.charAt(0)) == List('A', 'G', 'O'))

// Get the names as lists
assert(names.map(_.toList) == List(List('A', 'r', 'n', 'o', 'l', 'd'),
 List('G', 'e', 'o', 'r', 'g', 'e'), List('O', 'b', 'a', 'm', 'a')))

// When you have a list of lists, you can use flatMap
assert(names.flatMap(_.toList) == List('A', 'r', 'n', 'o', 'l', 'd',
 'G', 'e', 'o', 'r', 'g', 'e', 'O', 'b', 'a', 'm', 'a'))

// Filter is used to filter out specific elements that satisfy the predicate.

// Filter out all names of length 6
assert(names.filter(_.length == 6) == List("Arnold", "George"))

val chars = names.flatMap(_.toList)

// Filter out all chars larger than 'a' (capitals are smaller in ascii)
assert(chars.filter(_ > 'a') == List('r', 'n', 'o', 'l', 'd', 'e', 'o', 
'r', 'g', 'e', 'b', 'm'))

// And combine them
// Give me the first letter of all words with length 6
assert(names.filter(_.length == 6).map(_.charAt(0)) == List('A', 'G'))

There is a bunch of other useful functions based on filter.

// partition returns a pair of list (satisfied, not satisfied)
assert(names.partition(_.length == 6) == (List("Arnold", "George"), List("Obama")))

// find returns the first element that satisfy the predicate
// Since this function may not be satisfied, an optional value is used
assert(names.find(_.length == 6) == Some("Arnold"))

// An optional value returns Some(value) or None
assert(names.find(_.length == 7) == None)

// takeWhile and dropWhile take resp. drop while the predicate is fulfilled
assert(chars.takeWhile(_ != 'o') == List('A', 'r', 'n'))
assert(chars.dropWhile(_ != 'm') == List('m', 'a'))

// Span does both at the same time
assert(chars.span(_ != 'o') == (List('A', 'r', 'n'), 
List('o', 'l', 'd', 'G', 'e', 'o', 'r', 'g', 'e', 'O', 'b', 'a', 'm', 'a')))

// forall checks that a predicate is true for all elements of the list
assert(!chars.forall(_ == 'a'))
assert(chars.forall(_ >= 'A'))

// exists checks that a predicate is true for some element of the list
assert(names.exists(_.length == 5))
assert(!names.exists(_.length == 7))

// sort, sorts a list according to an ordinal function
assert(List(3, 7, 5).sort(_ > _) == List(7, 5, 3))

The fold functions, fold left (/:) and fold right (:\) inserts operators between all the elements of a list. The difference between them is whether they start or end with the base element.

fold left: (0 /: List(1, 2, 3)) (op) = op(op(op(0, 1), 2), 3)

fold right: (List(1, 2, 3) :\ 0) (op) = op(1, op(2, op(3, 0)))

// Define the sum function for lists with fold left
def sum(xs:List[Int]): Int = (0 /: xs)(_ + _)
assert(sum(List(2, 3, 4)) == 9) 

// Define the product function for lists with fold right
def prod(xs:List[Int]): Int = (xs :\ 1)(_ * _)
assert(prod(List(2, 3, 4)) == 24) 

// Define reverse in terms of fold
def reverse[T](xs: List[T]) = (List[T]() /: xs) ((ys, y) => y :: ys)
assert(reverse(List(1, 2, 3)) == List(3, 2, 1))

Thats it for the methods of the List class. In the Companion List object we also find some useful functions. We have been using one of them, all the time.

List.apply or List() creates a list from its arguments.

Apart from this one, there are some other worth mentioning.

// List.range creates a list of numbers
assert(List.range(1, 4) == List(1, 2, 3))
assert(List.range(1, 9, 3) == List(1, 4, 7))
assert(List.range(9, 1, -3) == List(9, 6, 3))

// List.make, creates lists containing the same element
assert(List.make(3, 1) == List(1, 1, 1))
assert(List.make(3, 'a') == List('a', 'a', 'a'))

// List.unzip zips up a list of tuples
assert(List.unzip(List(('a', 1), ('b', 2))) == (List('a', 'b'), List(1, 2)))

// List.flatten flattens a list of lists
assert(List.flatten(List(List(1, 2), List(3, 4), List(5, 6))) == List(1, 2, 3, 4, 5, 6))

// List.concat concatenates a bunch of lists
assert(List.concat(List(1, 2), List(3, 4), List(5, 6)) == List(1, 2, 3, 4, 5, 6))

// List.map2 maps two lists 
assert(List.map2(List.range(1, 999999), List('a', 'b'))((_, _)) == List((1, 'a'), (2, 'b')))

// List.forall2
assert(List.forall2(List("abc", "de"), List(3, 2)) (_.length == _))

// List.exists2
assert(List.exists2(List("abc", "de"), List(3, 4)) (_.length != _))

And as if all this was not enough, Scala also support For Expressions. In other languages they are commonly known as List Comprehensions.

A basic for expression looks like this

for ( seq ) yield expr where seq is a semicolon separated sequence of generators, definitions and filters.

// Do nothing
assert(names == (for (name <- names) yield name))

// Map
assert(List('A', 'G', 'O') == (for (name <- names) yield name.charAt(0)))

// Filter
assert(List("Obama") == (for (name <- names if name.length == 5) yield name))

val cartesian = for (x <- List(1, 2); y <- List("one", "two")) yield (x, y)
assert(cartesian == List((1, "one"), (1, "two"), (2, "one"),  (2, "two")))

// And now the grand finale, the cartesian product of a list of list
def cart[T](listOfLists: List[List[T]]): List[List[T]] = listOfLists match {
 case Nil => List(List())
 case xs :: xss => for (y <- xs; ys <- cart(xss)) yield y :: ys
}
val cp = cart(List(List(1,2), List(3,4), List(5,6))) 
assert(cp == 
  List(List(1, 3, 5), List(1, 3, 6), List(1, 4, 5), 
  List(1, 4, 6), List(2, 3, 5), List(2, 3, 6), 
  List(2, 4, 5), List(2, 4, 6)))

Ain't it beautiful so say!