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!
Great post, thank you!
ReplyDelete@Iaroslav, Thanks, I'm glad you liked it
ReplyDelete