ch6-CommonCollections.asciidoc

1) Create a list of the first 20 odd Long numbers. Can you create this with a for-loop, with the filter operation, and with the map operation? What’s the most efficient and expressive way to write this?

Answer

There’s many ways to generate this list with the collections library, too many to list here. Here are some examples of generating it with a for-loop, filtering, and mapping.

scala> for (i <- 0L to 9L; j = i * 2 + 1) yield j
res0: scala.collection.immutable.IndexedSeq[Long] = Vector(1, 3, 5, 7, 9,
11, 13, 15, 17, 19)

scala> 0L to 20L filter (_ % 2 == 1)
res1: scala.collection.immutable.IndexedSeq[Long] = Vector(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)

scala> 0L to 9L map (_ * 2 + 1)
res2: scala.collection.immutable.IndexedSeq[Long] = Vector(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)

2) Write a function titled "factors" that takes a number and returns a list of its factors, other than 1 and the number itself. For example, factors(15) should return List(3, 5).

Then write a new function that applies "factors" to a list of numbers. Try using the list of Long numbers you generated in exercise 1. For example, executing this function with the List(9, 11, 13, 15) should return List(3, 3, 5), as the factor of 9 is 3 while the factors of 15 are 3 again and 5. Is this a good place to use map and flatten? Or, would a for-loop be a better fit?

Answer

Here’s the "factors" function.

scala> def factors(x: Int) = { 2 to (x-1) filter (x % _ == 0) }
factors: (x: Int)scala.collection.immutable.IndexedSeq[Int]

We could use map to map each item in the list to a new factor list and then flatten the list of lists into a single list. Or just use flatMap once.

scala> def uniqueFactors(l: Seq[Int]) = l flatMap factors
uniqueFactors: (l: Seq[Int])Seq[Int]

scala> uniqueFactors(List(9, 11, 13, 15))
res13: Seq[Int] = List(3, 3, 5)

3) Write a function, first[A](items: List[A], count: Int): List[A], that returns the first x number of items in a given list. For example, first(List('a','t','o'), 2) should return List('a','t'). You could make this a one-liner by invoking one of the built-in list operations that already performs this task, or (preferably) implement your own solution. Can you do so with a for-loop? With foldLeft? With a recursive function that only accessed head and tail?

Answer

Although using a built-in list operation won’t help you build out your Scala collection skills, it does let you solve the problem with a simple one-liner. And this is often the solution you will choose first while writing your own applications.

scala> val chars = ('a' to 'f').toList
chars: List[Char] = List(a, b, c, d, e, f)

scala> def first[A](items: List[A], count: Int): List[A] = items take count
first: [A](items: List[A], count: Int)List[A]

scala> first(chars, 3)
res0: List[Char] = List(a, b, c)

Now that we have the easy solution working, let’s try writing out our own solutions. Here’s one that uses a for-loop.

scala> def first[A](items: List[A], count: Int): List[A] = {
     |   val l = for (i <- 0 until count) yield items(i)
     |   l.toList
     | }
first: [A](items: List[A], count: Int)List[A]

scala> first(chars, 3)
res1: List[Char] = List(a, b, c)

This works, but it’s performance is going to be terrible with long non-indexed collections such as linked lists.

Here’s a version using foldLeft, which then relies on reverse to return the items in their original order. Starting with an empty list, this function adds each element in the input list to its accumulated list.

scala> def first[A](items: List[A], count: Int): List[A] = {
     |   items.foldLeft[List[A]](Nil) { (a: List[A], i: A) =>
     |     if (a.size >= count) a else i :: a
     |   }.reverse
     | }
first: [A](items: List[A], count: Int)List[A]

scala> first(chars, 3)
res2: List[Char] = List(a, b, c)

Finally, let’s solve this with an old-fashioned recursive function. Limited to accessing the head and tail components, this uses non-tail recursion to accumulate a list starting with the final recursive call.

scala> def first[A](items: List[A], count: Int): List[A] = {
     |   if (count > 0 && items.tail != Nil) items.head :: first(items.tail, count - 1)
     |   else Nil
     | }
first: [A](items: List[A], count: Int)List[A]

scala> first(chars, 3)
res3: List[Char] = List(a, b, c)

4) Write a function that takes a list of strings and returns the longest string in the list. Can you avoid using mutable variables here? This is an excellent candidate for the list-folding operations we studied. Can you implement this with both fold and reduce ? Would your function be more useful if it took a function parameter that compared two strings and returned the preferred one? How about if this function was applicable to generic lists, ie lists of any type?

Answer

Again, let’s start with a short and simple implementation that takes advantage of the collections library.

scala> def longest(l: List[String]): String = names.sortBy(0 - _.size).head
longest: (l: List[String])String

scala> val names = List("Harry", "Hermione", "Ron", "Snape")
names: List[String] = List(Harry, Hermione, Ron, Snape)

scala> longest(names)
res0: String = Hermione

Using fold and reduce is a natural fit for this function, as we’re reducing a list down to one of its elements.

scala> def longest(l: List[String]): String = {
     |   names.fold("")((a,i) => if (a.size < i.size) i else a)
     | }
longest: (l: List[String])String

scala> longest(names)
res1: String = Hermione

scala> def longest(l: List[String]): String = {
     |   names.reduce((a,i) => if (a.size < i.size) i else a)
     | }
longest: (l: List[String])String

scala> longest(names)
res2: String = Hermione

Now, if we’re going to make this function applicable to any kind of list we will need a new way to compare elements. Here’s a solution that takes a plain comparison function and uses it to reduce the list. We can invoke it with a function literal that returns the string with the longer size.

scala> def greatest[A](l: List[A], max: (A,A) => A): A = {
     |   l reduce ((a,i) => max(a,i))
     | }
greatest: [A](l: List[A], max: (A, A) => A)A

scala> greatest[String](names, (x,y) => if (x.size > y.size) x else y)
res3: String = Hermione

5) Write a function that reverses a list. Can you write this as a recursive function? This may be a good place for a match expression.

Answer

We have already made use of "reverse" in answers to previous exercise questions, so it’s a good idea to try and provide it ourselves. This version uses two list parameters, one of which gets initialized to Nil, to reverse the elements one at a time.

scala> def reverse[A](src: List[A], dest: List[A] = Nil): List[A] = {
     |   if (src == Nil) dest else reverse(src.tail, src.head :: dest)
     | }
reverse: [A](src: List[A], dest: List[A])List[A]

scala> val names = List("Harry", "Hermione", "Ron", "Snape")
names: List[String] = List(Harry, Hermione, Ron, Snape)

scala> reverse(names)
res0: List[String] = List(Snape, Ron, Hermione, Harry)

6) Write a function that takes a List[String] and returns a (List[String],List[String]), a tuple of string lists. The first list should be items in the original list that are palindromes (written the same forwards and backwards, like "racecar"). The second list in the tuple should be all of the remaining items from the original list. You can implement this easily with partition, but are there other operations you could use instead?

Answer

First, the easy way! Let’s invoke partition with a function that returns true if the string is a palindrome.

scala> def splitPallies(l: List[String]) = l partition (s => s == s.reverse)
splitPallies: (l: List[String])(List[String], List[String])

scala> val pallies = List("Hi", "otto", "yo", "racecar")
pallies: List[String] = List(Hi, otto, yo, racecar)

scala> splitPallies(pallies)
res0: (List[String], List[String]) = (List(otto, racecar),List(Hi, yo))

If you think about it, partition is a kind of list reduction function. It reduces a list to a single tuple, which happens to contain two lists. Let’s use foldLeft to reduce the list down to the tuple.

scala> def splitPallies(l: List[String]) = {
     |   l.foldLeft((List[String](),List[String]())) { (a, i) =>
     |     if (i == i.reverse) (i :: a._1, a._2) else (a._1, i :: a._2)
     |   }
     | }
splitPallies: (l: List[String])(List[String], List[String])

scala> splitPallies(pallies)
res0: (List[String], List[String]) = (List(racecar, otto),List(yo, Hi))

7) The last exercise in this chapter is a multi-part problem. We’ll be reading and processing a forecast from the excellent and free OpenWeatherMap API.

To read content from the url we’ll use the Scala library operation io.Source.fromURL(url: String), which returns an io.Source instance. Then we’ll reduce the source to a collection of individual lines using the getLines.toList operation. Here is an example of using io.Source to read content from a url, separate it into lines and return the result as a list of strings.

scala> val l: List[String] = io.Source.fromURL(url).getLines.toList

Here is the url we will use to retrieve the weather forecast, in XML format.

scala> val url =
  "http://api.openweathermap.org/data/2.5/forecast?mode=xml&lat=55&lon=0"

Go ahead and read this url into a list of strings. Once you have it, print out the first line to verify you’ve captured an xml file. The result should look pretty much like this:

scala> println( l(0) )
<?xml version="1.0" encoding="utf-8"?>

If you don’t see an xml header, make sure that your url is correct and your internet connection is up.

Let’s begin working with this List[String] containing the xml document.

a) To make doubly sure we have the right content, print out the top 10 lines of the file. This should be a one-liner.

b) The forecast’s city’s name is there in the first 10 lines. Grab it from the correct line and print out its xml element. Then extract the city name and country code from their xml elements and print them out together (e.g., "Paris, FR"). This is a good place to use regular expressions to extract the text from xml tags (see [regular_expressions_section]).

If you don’t want to use regular expression capturing groups, you could instead use the replaceAll() operation on strings to remove the text surrounding the city name and country name.

c) How many forecast segments are there? What is the shortest expression you can write to count the segments?

d) The "symbol" xml element in each forecast segment includes a description of the weather forecast. Extract this element in the same way you extracted the city name and country code. Try iterating through the forecasts, printing out the description.

Then create an informal weather report by printing out the weather descriptions over the next 12 hours (not including the xml elements).

e) Let’s find out what descriptions are used in this forecast. Print a sorted listing of all of these descriptions in the forecast, with duplicate entries removed.

f) These descriptions may be useful later. Included in the "symbol" xml element is an attribute containing the symbol number. Create a Map from the symbol number to the description. Verify this is accurate by manually accessing symbol values from the forecast and checking that the description matches the xml document.

g) What are the high and low temperatures over the next 24 hours?

h) What is the average temperature in this weather forecast? You can use the "value" attribute in the temperature element to calculate this value.

Answer

a) We’ll load the url and verify the first 10 lines here.

scala> val url = "http://api.openweathermap.org/data/2.5/forecast?mode=xml&lat=55&lon=0"
url: String = http://api.openweathermap.org/data/2.5/forecast?mode=xml&lat=55&lon=0

scala> val l: List[String] = io.Source.fromURL(url).getLines.toList
l: List[String] = List(<?xml version="1.0" encoding="utf-8"?>, <weatherdata>, "  <location>", "    <name>Whitby</name>", "    <type/>", "    <country>GB</country>", "    <timezone/>", "    <location altitude="0" latitude="54.48774" longitude="-0.61498" geobase="geonames" geobaseid="0"/>", "  </location>", "  <credit/>", "  <meta>", "    <lastupdate/>", "    <calctime>1.067</calctime>", "    <nextupdate/>", "  </meta>", "  <sun rise="2014-12-26T08:24:05" set="2014-12-26T15:42:23"/>", "  <forecast>", "    <time from="2014-12-26T21:00:00" to="2014-12-27T00:00:00">", "      <symbol number="500" name="light rain" var="10n"/>", "      <precipitation value="0.5" unit="3h" type="rain"/>", "      <windDirection deg="175.502" code="S" name="South"/>", "      <windSpeed mps="4.46" name="Gentle Bre...

scala> l take 10
res0: List[String] = List(<?xml version="1.0" encoding="utf-8"?>, <weatherdata>, "  <location>", "    <name>Whitby</name>", "    <type/>", "    <country>GB</country>", "    <timezone/>", "    <location altitude="0" latitude="54.48774" longitude="-0.61498" geobase="geonames" geobaseid="0"/>", "  </location>", "  <credit/>")

b) To make parsing easier, trim that white space from each line. Also, a function to retrieve the child text of a simple xml block makes the job easier.

scala> val k = l map (_.trim)
k: List[String] = List(<?xml version="1.0" encoding="utf-8"?>, ...

scala> def getChild(tag: String) = k filter (_ contains s"<$tag>") mkString "" replaceAll(".*>(\\w+)</.*","$1")
getChild: (tag: String)String

scala> val cityName = getChild("name")
cityName: String = Whitby

scala> val countryCode = getChild("country")
countryCode: String = GB

c) Measuring the number of lines with the end segment "</time>" seems like a good way to do this.

scala> val segments = l.filter(_ contains "</time>").size
segments: Int = 41

d) To get the weather description, we’ll need to grab the "<symbol>" lines and retrieve the contents of the "name" field. I’m writing this as a reusable function because, yes, we’ll be reusing it!

scala> def attribute(tag: String, attr: String) = {
     |   k.filter(_ contains s"<$tag")
     |     .filter(_ contains s"$attr=")
     |     .map { s => s.replaceAll(s""".*$attr="([^"]+)".*""", "$1") }
     | }
attribute: (tag: String, attr: String)List[String]

scala> val names = attribute("symbol", "name")
names: List[String] = List(light rain, light rain, light rain, overcast clouds, ...

Looking at the full weather feed, you can see that each time segment covers three hours. To do a 12-hour forecast all we need are the first four segments. Plus, it would be nice to include the start time of each period in the forecast.

It’s a good thing we have an "attribute" function. First, let’s use it to retrieve a tuple of the time and description for the next 12 hours. Then we’ll print it out with minor improvements to the time.

scala> val forecast = attribute("time", "from") zip attribute("symbol", "name") take 4
forecast: List[(String, String)] = List((2014-12-26T21:00:00,light rain), (2014-12-27T00:00:00,light rain), (2014-12-27T03:00:00,light rain), (2014-12-27T06:00:00,overcast clouds))

scala> {
     |   println("12 hour forecast")
     |   forecast foreach { case (time, desc) =>
     |     val when = time.replaceAll("""T(\d+).*""",""" at $100""")
     |     println(s"$when | $desc")
     |   }
     | }
12 hour forecast
2014-12-26 at 2100 | light rain
2014-12-27 at 0000 | light rain
2014-12-27 at 0300 | light rain
2014-12-27 at 0600 | overcast clouds

Very nice, if I do say so myself.

e) Easy enough with our "attribute" function.

scala> val terms = attribute("symbol", "name").distinct.sorted
terms: List[String] = List(broken clouds, few clouds, light rain, overcast clouds, scattered clouds, sky is clear)

f) Let’s make another list of tuples, and then turn them into a map. Fortunately there’s a helper function called "toMap" which will build one from a list of 2-sized tuples.

scala> val symbolsToDescriptions = attribute("symbol", "number") zip attribute("symbol", "name")
symbolsToDescriptions: List[(String, String)] = List((500,light rain), (500,light rain), (500,light rain), (804,overcast clouds), (500,light rain), ...

scala> val symMap = symbolsToDescriptions.distinct.map(t => t._1.toInt -> t._2).toMap
symMap: scala.collection.immutable.Map[Int,String] = Map(500 -> light rain, 802 -> scattered clouds, 804 -> overcast clouds, 800 -> sky is clear, 801 -> few clouds, 803 -> broken clouds)

scala> println("Light rain? Yup, " + symMap(500))
Light rain? Yup, light rain

g) The "max" and "min" functions for numeric lists are really helpful here.

scala> val maxC = attribute("temperature", "max").map(_.toDouble).max
maxC: Double = 7.743

scala> val minC = attribute("temperature", "min").map(_.toDouble).min
minC: Double = 3.042

h) This time I’ll use the "sum" function for numeric lists along with the handy "attribute" function.

scala> val temps = attribute("temperature", "value").map(_.toDouble)
temps: List[Double] = List(4.04, 3.96, 5.03, 5.61, 5.92, 5.5, 5.11, 4.93, 6.47, 6.8200000000001, 6.88, 6.51, 6.01, 7.22, 7.22, 6.4, 5.4, 5.06, 5.95, 6.37, 6.808, 7.42, 7.743, 7.701, 7.41, 6.236, 5.508, 5.34, 5.476, 6.644, 6.794, 6.043, 5.701, 5.199, 4.482, 3.755, 3.042, 4.897, 4.507, 3.824, 3.902)

scala> val avgC = temps.sum / temps.size
avgC: Double = 5.7278536585365885