1. CS-A1110
  2. Week 9
  3. Chapter 9.2: Pairs and Maps

Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on testatumpi ja hieman laajempi ja muutenkin mukava.

Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit.

Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.


Chapter 9.2: Pairs and Maps

../_images/person02.png

Introduction: Two Return Values?

Frequently asked question

Can a function return two values? Could we, for instance, define a function toMinsAndSec that takes in a number of seconds and returns two integers: the number of whole minutes and the leftover seconds? Perhaps it would work like this:

toMinsAndSecs(187)res0: (Int, Int) = (3,7)

It would be nice if we could also save the returned values for later use in two separate variables; say, min and s.

Possible solutions

Functions can’t really return more than a single value, but we can work around that restriction so that it’s as if they could.

One workaround is to return a collection of two elements, say, a Vector[Int].

val returnedValues = toMinsAndSecs(187)returnedValues: Vector[Int] = Vector(3,7)
val min = returnedValues(0)min: Int = 3
val s = returnedValues(1)s: Int = 7

This solution isn’t terrible, but the type Vector[Int] doesn’t express how we’re always returning exactly two numbers. That solution is also impractical if you wish to return two values of different types.

Another workaround is to write a custom class that represents the sort of composite information that the function returns. For instance, we might define a Time class with methods for minutes and seconds, and have our function return a Time object. This can be a good choice in case the returned information corresponds to a concept and can be naturally represented as a class.

A third workaround makes use of pairs (pari). Pairs are not only good for returning multiple values; you’ll see in this chapter that they have other uses as well.

Let’s have a look at pairs in general before we return to minutes and seconds.

Pairs

Basic use of pairs in Scala

You can form a pair with brackets and a comma, as shown here:

("good thing", "another thing")res1: (String, String) = (good thing,another thing)

There are brackets in the REPL output, too. (String, String) means a pair whose members are both strings.

Here’s a familiar-looking way to access the members of a pair:

var myPair = ("good thing", "another thing")myPair: (String, String) = (good thing,another thing)
myPair(0)res2: String = good thing
myPair(1)res3: String = another thing

A key difference between a pair and, say, a two-element vector is that a pair’s members can have different static types:

val nameAndShoeSize = ("Juha", 43)nameAndShoeSize: (String, Int) = (Juha,43)

Another significant difference is that the size of a pair is known in advance. This attempt produces a compile-time error and thus cannot crash a program at runtime:

nameAndShoeSize(2)-- Error:
  nameAndShoeSize(2)
                 ^

It’s easy to copy the two members of a pair into two separate variables. Just use brackets:

val (name, shoeSize) = nameAndShoeSizename: String = Juha
shoeSize: Int = 43

A minute assignment

Implement the toMinsAndSecs function we contemplated earlier. It should work like this:

toMinsAndSecs(187)res4: (Int, Int) = (3,7)
val (min, s) = toMinsAndSecs(200)min: Int = 3
s: Int = 20

Write your solution in o1/misc.scala in module Miscellaneous.

A+ presents the exercise submission form here.

Here’s a variation on a question from Chapter 1.4

Once upon a time, there were two var variables named hansel and gretel, who had the same data type. With that in mind, let’s examine the following piece of code:

val (hansel2, gretel2) = (gretel, hansel)

Which of the following claims best describes what happens to the values of the two variables? Assume that the variables have been created and initialized to some values before this line of code executed.

Dividing collections

Pairs feature in various API methods. There are a couple of examples below.

Collections have a splitAt method that returns a pair whose members are collections:

val temperatures = Vector(3, 6, -1, -5, 3, -1, 2)temperatures: Vector[Int] = Vector(3, 6, -1, -5, 3, -1, 2)
temperatures.splitAt(3)res5: (Vector[Int], Vector[Int]) = (Vector(3, 6, -1),Vector(-5, 3, -1, 2))
val (workingWeek, weekend) = temperatures.splitAt(5)workingWeek: Vector[Int] = Vector(3, 6, -1, -5, 3)
weekend: Vector[Int] = Vector(-1, 2)

splitAt takes in a number that indicates a position in the collection.

The first member of the returned pair lists all the elements that are located before the indicated position in the original collection. The second member lists the rest of the elements.

partition also divides the elements of the original collection in two and returns a pair of collections:

val (freezing, aboveFreezing) = temperatures.partition( _ < 0 )freezing: Vector[Int] = Vector(-1, -5, -1)
aboveFreezing: Vector[Int] = Vector(3, 6, 3, 2)

As you can see, this method divides the elements by calling the given function on each one and checking whether it returns true or false.

Mini-assignment: dividing a collection

Go to package o1.people in module Miscellaneous and find YoungAndOldApp. The comments in this app object explain how the program should work. Implement the missing parts of the program. Use one of the methods just introduced.

A+ presents the exercise submission form here.

Zipping collections together

You just saw some pairs whose members were collections. You can also have a collection whose elements are pairs.

Collections have a handy method named zipWithIndex. It forms a new collection where each element is the original element paired with its index:

val species = Vector("llama", "alpaca", "vicuña")species: Vector[String] = Vector(llama, alpaca, vicuña)
species.zipWithIndexres6: Vector[(String, Int)] = Vector((llama,0), (alpaca,1), (vicuña,2))

We get a vector of pairs, each of which contains a string and an integer.

When you loop over such a collection of pairs, you can again use round brackets to deal with two variables at once. Here are two ways of printing out a collection of pairs:

for pair <- species.zipWithIndex do
  println(pair(0) + " is at index #" + pair(1))llama is at index #0
alpaca is at index #1
vicuña is at index #2
for (element, index) <- species.zipWithIndex do
  println(element + " is at index #" + index)llama is at index #0
alpaca is at index #1
vicuña is at index #2

zipWithIndex is a special case of the more generic zip method, which pairs up the elements of two collections:

val heights = Vector(120, 90, 80)heights: Vector[Int] = Vector(120, 90, 80)
val heightsAndSpecies = heights.zip(species)heightsAndSpecies: Vector[(Int, String)] = Vector((120,llama), (90,alpaca), (80,vicuña))

If the collections have different lengths, the longer collection’s tail end is ignored:

val moreSpecies = Vector("llama", "alpaca", "vicuña", "guanaco", "wooly")moreSpecies: Vector[String] = Vector(llama, alpaca, vicuña, guanaco, wooly)
val justThreePairs = heights.zip(moreSpecies)justThreePairs: Vector[(Int, String)] = Vector((120,llama), (90,alpaca), (80,vicuña))

You can also unzip a collection of pairs to obtain a pair of collections:

heightsAndSpecies.unzipres7: (Vector[Int], Vector[String]) = (Vector(120, 90, 80),Vector(llama, alpaca, vicuña))

A pair as a parameter

Naturally, you can also define a function that takes a pair as a parameter. The example function below takes a pair of numbers and returns the absolute value of their difference.

def absDiff(pairOfNumbers: (Int, Int)) =
  (pairOfNumbers(0) - pairOfNumbers(1)).abs

Usage example:

val myPair = (10, 30)myPair: (Int, Int) = (10,30)
absDiff(myPair)res8: Int = 20
absDiff((-300, 100))res9: Int = 400

This works, too:

absDiff(-300, 100)res10: Int = 400

We’ve left out the extra pair of brackets that defines a pair. We’re invoking the single-parameter function absDiff as though it took two separate Int parameters. Scala automatically constructs a pair from the two values, so this does the same as absDiff((-300, 100)).

A similar principle is at work in the following example.

Combining pairs with higher-order functions

Let’s use this familiar example data from above:

val species = Vector("llama", "alpaca", "vicuña")species: Vector[String] = Vector(llama, alpaca, vicuña)
val heights = Vector(120, 90, 80)heights: Vector[Int] = Vector(120, 90, 80)
val heightsAndSpecies = heights.zip(species)heightsAndSpecies: Vector[(Int, String)] = Vector((120,llama), (90,alpaca), (80,vicuña))

One way to print out a report of each species is this:

def heightDescription(heightSpeciesPair: (Int, String)) =
  "a typical " + heightSpeciesPair(1) + " is " + heightSpeciesPair(0) + " cm at the shoulder"def heightDescription(heightSpeciesPair: (Int, String)): String
heightsAndSpecies.map(heightDescription).foreach(println)a typical llama is 120 cm at the shoulder
a typical alpaca is 90 cm at the shoulder
a typical vicuña is 80 cm at the shoulder

Since the collection contains pairs, we give its map method a function that takes in a pair and determines how to report it.

Since Scala lets us use a two-parameter function in place of a function that takes a single pair, we can alternatively write this:

def heightDescription(cm: Int, species: String) =
  s"a typical $species is $cm cm at the shoulder"def heightDescription(cm: Int, species: String): String
heightsAndSpecies.map(heightDescription).foreach(println)a typical llama is 120 cm at the shoulder
a typical alpaca is 90 cm at the shoulder
a typical vicuña is 80 cm at the shoulder

We write a perfectly normal two-parameter function that takes in a number and a string.

We may pass that function to the map method of a collection that consists of pairs. Scala ensures that our two-parameter function gets invoked on the members of each pair in the collection.

Assignment: isAscending

Write a function isAscending that takes in a vector of integers and reports whether those integers are in ascending order. Here are some examples:

isAscending(Vector(-10, 1, 5, 10))res11: Boolean = true
isAscending(Vector(-10, 1, 5, 5, 10))res12: Boolean = true
isAscending(Vector(-10, 1, 5, 9, 5, 10))res13: Boolean = false
isAscending(Vector(10, 5, 1, -10))res14: Boolean = false

Your method must not do extra work by actually sorting the collection. It should merely check if the elements are already sorted.

With clever use of the collections methods from this chapter and earlier ones, you can solve the assignment in a single, short line of code.

Write your code in misc.scala again.

You may assume that the vector contains at least one element.

A detailed hint on which methods to use

You may find the methods zip, tail, and forall useful. (Alternatively, you could try using the sliding method introduced in 7.1’s drySpell assignment.)

You can use forall to check whether it’s true, for each pair of consecutive elements, that they are in the right order. The auxiliary function that you pass to forall you could either define as a named function or type in as an anonymous function literal.

A+ presents the exercise submission form here.

Pairs are tuples

A pair is a two-membered tuple (monikko). A tuple may have more members than just two:

("This tuple has four members of different types.", 100, 3.14159, false)res15: (String, Int, Double, Boolean) = (This tuple has four members of different types.,100,3.14159,false)

Does that mean a tuple is a collection, like buffers and vectors are? Not quite.

First of all, tuples and collections have different purposes. Tuples tend to be most useful when: 1) there is a small, constant number of members (e.g., only two), and 2) each member has a meaning separate from the others (e.g., one signifies minutes, the other seconds; one is a name, the other is a shoe size), but 3) it nevertheless feels like overkill to write a custom class.

Here are some of the technical differences between tuples and collections:

  • In a tuple, each member has a distinct static type. In a collection, the elements share a static type.

  • Tuples are always immutable in size and content. Collections come in both mutable and immutable varieties.

  • Tuples don’t have the familiar collection methods (size, map, indexOf, etc.) and you can’t use a for loop to iterate over a tuple (without resorting to additional trickery).

Tuples and case classes

The optional material in Chapter 4.4 briefly introduced Scala’s case class construct. In a sense, a case class is a sort of customized tuple. For more on case classes, see the spring course Programming Studio 2.

One massively helpful and common thing to do with tuples — pairs, specifically — is to construct “maps” out of them. We’ll say more about that in just a bit.

Another Introduction: Keys and Values

How would you implement the following? What do all these scenarios have in common?

  • A dictionary: given a word in Finnish, we want to be able to find the corresponding word in English.

  • A student register: we want to be able to search for students by their student ID number.

  • An address book: we want to be able to find the person object that details an individual whose name we know.

  • An encyclopedia: given a string keyword, we want to access the encyclopedia article that matches that keyword.

  • Counting frequencies: We have a bunch of objects that all have a particular property. We want to know the distribution of different values of that property among the objects.

    • For instance, consider a theme we already touched on in Chapter 1.6: we have a list of top-rated movies, each of which has a director (or several), and we want to find out how many times each director features in the list.

It’s possible to solve these problems with the tools we’ve already covered. For example, here’s a buffer-based implementation for a primitive sort of dictionary:

val searchTerms = Buffer("kissa", "laama", "tapiiri", "koira")searchTerms: Buffer[String] = ArrayBuffer(kissa, laama, tapiiri, koira)
val englishTranslation = Buffer("cat", "llama", "tapir", "puppy")englishTranslation: Buffer[String] = ArrayBuffer(cat, llama, tapir, puppy)

We can use these two buffers to look up the translation of a Finnish word. (Recall the indexOf method from Chapter 4.2.)

val index = searchTerms.indexOf("tapiiri")index: Int = 2
englishTranslation(index)res16: String = tapir
englishTranslation(searchTerms.indexOf("koira"))res17: String = puppy

We can also update the dictionary by replacing an element. The Finnish word “koira” is better translated as “dog” than “puppy”, so let’s make that change:

englishTranslation(searchTerms.indexOf("koira")) = "dog"englishTranslation(searchTerms.indexOf("koira"))res18: String = dog

Pause to consider what we’re doing here. Our dictionary contains Finnish words, which we use to look up the corresponding English words. Here’s one way to put it: the Finnish words in searchTerms serve as keys (avain) that we use to locate the values (arvo) stored in englishTranslation.

The same basic pattern repeats in all the other scenarios listed above: student ID numbers as keys, the student objects as values; director names as keys, the movie counts of the directors as values; etc. In the following text, we will use the terms “key” and “value” in this sense.

Our buffer-based solution relies on the assumption that the two buffers store their elements in a specific order and the indices of the keys (in searchTerms) are the same as those of the corresponding values (in englishTranslation). The solution does work, but it’s not ideal, for multiple reasons.

First, we used two separate buffers for keys and values, even though we conceive of the dictionary as a single entity.

Second, it feels unnecessary to have to mess about with indices in order to look up a word. Nobody really cares which index the source or target word has in the buffer.

Third, What if the key is not found? For example:

englishTranslation(searchTerms.indexOf("Mikki-Hiiri"))

indexOf will then return -1, and we end up with a runtime error if we access a negative index of englishTranslation. We could work around that with an ´if`, but that’s additional work and we might forget to do so.

(Fourth, if we had lots of words in the dictionary, we might also wish for improved efficiency. indexOf checks each index of the buffer in order, one by one, until it reaches the target element. This search strategy isn’t even close to optimal.)

Maps

Let’s use a collection that stores both keys and values. A map (hakurakenne) is a tremendously useful and common collection type, and rather unlike the index-based collections that we’ve used so far in O1.

A map contains key–value pairs. When you use, say, a buffer, you look up elements by their positions in the collection; when you use a map, you instead look up values by their keys.

You can use any objects as keys. Those objects form a set in the mathematical sense of the word; in practice, that means that all of a map’s keys must be different from each other (e.g., no identical Finnish words as search terms, no identical student ID numbers, etc.).

In the Scala API, maps have been implemented as class Map.

Hold up! map is a method on collections — not a type of collection, right?

It’s true that we’ve been already using a method named map. The two concepts are distinct but there is a reason why their names are similar.

The familiar map-that-is-a-method takes an existing collection and uses its elements to generate another. The parameter function of map defines a mapping from the original elements to the generated elements.

A Map object — a map-that-is-a-collection — is a collection of key–value pairs. It stores a mapping from keys to values.

The map method is available on all sorts of collections, not just on Maps.

But Before We Get to Maps: Key–Value Pairs

Here’s some Scala code that defines a key–value pair. This is just a regular pair that happens to contain data that we intend to use as a key and a value.

("koira", "dog")res19: (String, String) = (koira,dog)

However, when defining key–value pairs, it’s common to use another notation. This other notation highlights that each key “points at” the corresponding value. The following code produces precisely the same outcome as the code above:

"koira" -> "dog"res20: (String, String) = (koira,dog)

The -> arrow defines a pair.

We put the key on the left and the value on the right.

We get a pair of data items.

Either notation works for creating any pair. In O1, we’ll prefer the arrow notation when we define pairs that represent a Map’s keys and values.

You can use any objects in a key–value pair. In the above example, both the key and the value were strings, as befits our dictionary. It is equally possible to, say, associate an integer key with a string value or the other way around:

233524 -> "Susan Student"res21: (Int, String) = (233524,Susan Student)
"Sergio Leone" -> 5res22: (String, Int) = (Sergio Leone,5)
../_images/p%C3%A4%C3%A4kirjoitus.png

Is this Scala or Sumerian?

Note that the arrow -> that we’re using here to construct pairs is not the same as the arrow => that we’ve used in function types and case branches.

I’m starting to get my arrows all mixed up.

More about the arrow

-> is an ordinary method.

"seikkailija" -> "adventurer"res23: (String, String) = (seikkailija,adventurer)

The target object whose method we call.

This method, whose name consists of a hyphen and a greater-than sign, is available on all Scala objects. Here, we have used operator notation (Chapter 5.2), which omits the period-dot between the target object and the method name.

The second string is passed as a parameter to the method. In the operator notation, we can omit the brackets around the parameter.

The method returns a pair that comprises the target object and the parameter object.

We could have used the dot notation. These two expressions are equivalent:

"polvi".->("knee")res24: (String, String) = (polvi,knee)
"polvi" -> "knee"res25: (String, String) = (polvi,knee)

Since the idea is to visually suggest an arrow, the operator notation is understandably much more common here.

Maps in Scala: Class Map

It’s straightforward to implement a little Finnish-to-English dictionary as a Map.

First, we’ll need to import the Map class that we intend to use:

import scala.collection.mutable.Map

As you’ll know by now, objects can be mutable or immutable. Since Scala is designed to support different styles of programming, its standard API comes with two different Map classes, one for mutable maps and one for immutable ones. For now, we’ll mostly use mutable maps: map objects whose keys and values can be modified. The corresponding class is in package scala.collection.mutable and needs to be imported as we did above.

We can create a Map object like this:

val finnishToEnglish = Map("kissa" -> "cat", "laama" -> "llama", "tapiiri" -> "tapir", "koira" -> "puppy")finnishToEnglish: Map[String,String] = Map(koira -> puppy, tapiiri -> tapir, kissa -> cat, laama -> llama)

The difference to the familiar collection types is that a map’s elements are always key–value pairs.

A map has two type parameters: the type of the keys and the type of the values. In this example, we have a map whose keys and values are both strings.

A look at the REPL output is enough to suggest that this isn’t a numerically indexed collection. The elements are all over the map in what looks like an arbitrary order. They have no indices. The logic that dictates how a map orders its contents depends on the map’s internal implementation and is unimportant for present purposes.

The sections below demonstrate a selection of the methods available on Map objects. Once again, the intention is not that you memorize them all but that you get an overall sense of what you can do with this collection type.

As you read these examples, you’ll see that there are (again) a number of ways to do the same thing. It’s unlikely that you’ll be able to tell right away which solution is the best fit for which situation. Then again, you don’t need to; that’s the sort of thing that improves with experience. It’s good to learn to recognize different kinds of solutions already, though.

Accessing a single value

It’s simple to fetch a value that matches a key:

finnishToEnglish.get("kissa")res26: Option[String] = Some(cat)
finnishToEnglish.get("Mikki-Hiiri")res27: Option[String] = None

The get method takes a key as a parameter.

Its return type is Option[TypeOfValuesInMap].

If the key was present in the map, we get a Some that holds the corresponding value. If not, we get None.

Replacing a value

When working with a mutable map, we can update it as shown below.

finnishToEnglish.get("koira")res28: Option[String] = Some(puppy)
finnishToEnglish("koira") = "dog"finnishToEnglish.get("koira")res29: Option[String] = Some(dog)

Remember: the keys of a map are unique. A map cannot contain multiple key–value pairs whose keys are equal. So what happens above is that the pair "koira" -> "puppy" is replaced by the pair "koira" -> "dog".

Adding a key–value pair

There are a number of ways to add a key–value pair to a mutable map. One of them is to assign a value to a previously unused key:

finnishToEnglish("hiiri") = "mouse"

Another way to add or replace a key–value pair is the += operator, which you’ve previously used on buffers:

finnishToEnglish += "sika" -> "pig"res30: Map[String, String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat, sika -> pig, hiiri -> mouse,
laama -> llama)

This command also replaces any previously stored key–value pair that has the same key.

The rest of this ebook uses this second notation to add pairs to a map. You can use whichever you prefer.

Removing a key–value pair

Here’s one way to remove a pair:

finnishToEnglish -= "laama"res31: Map[String, String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat, sika -> pig, hiiri -> mouse)

There’s also a remove method that returns the removed value in an Option wrapper:

finnishToEnglish.remove("laama")res32: Option[String] = Some(llama)

Checking a key

The contains method tells us if a given key is present in the map. In the example below, "tapiiri" is present in the dictionary whereas "laama", which we just removed, is not.

finnishToEnglish.contains("tapiiri")res33: Boolean = true
finnishToEnglish.contains("laama")res34: Boolean = false

Can you use this same method to check if the English word "tapir" is in our dictionary? That is, does contains search the values like it searches the keys? Try it.

Getting all the keys or all the values

The methods keys and values return all the keys and all the values of a map, respectively. These methods return collections that you can process with the usual collection methods, such as foreach. Here, for instance, we first print out all the keys followed by all the values.

finnishToEnglish.keys.foreach(println)koira
tapiiri
kissa
sika
hiiri
finnishToEnglish.values.foreach(println)dog
tapir
cat
pig
mouse

Familiar methods on Maps

Maps are collections and, as such, have many familiar methods. Here are just a few examples of the collection methods from Chapters 4.2 and 6.3:

val finToEng = Map("kissa" -> "cat", "tapiiri" -> "tapir", "koira" -> "dog")finToEng: Map[String,String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat)
finToEng.isEmptyres35: Boolean = false
finToEng.sizeres36: Int = 3
finToEng.foreach(println)(koira,dog)
(tapiiri,tapir)
(kissa,cat)

The map method (lower case) is worth a special mention. You can use it to process the key–value pairs of a Map (upper case) in order to create a new Map:

val myTestMap = finToEng.map( finEngPair => finEngPair(0).toUpperCase -> (finEngPair(1) + "!!!") )myTestMap: Map[String,String] = Map(KISSA -> cat!!!, TAPIIRI -> tapir!!!, KOIRA -> dog!!!)

Since a Map consists of pairs, we pass the map method a function that operates on pairs.

Our example function forms a new pair that consists of an upper-case version of the original pair’s first member (the Finnish key)...

... and a string consisting of the original pair’s second member (the English value) and some exclamation marks.

These new pairs form a new Map, which maps upper-case Finnish words to shouty English words.

We can write that code to be easier to read and more elegant. Let’s make use of something that already came up in this chapter: Scala lets us use a two-parameter function in place of a function that takes a single pair as a parameter. Like so:

val myTestMap = finToEng.map( (fin, eng) => fin.toUpperCase -> (eng + "!!!") )myTestMap: Map[String,String] = Map(KISSA -> cat!!!, TAPIIRI -> tapir!!!, KOIRA -> dog!!!)

We use a two-parameter function literal whose parameters have descriptive names. There’s no need to mess about with indices.

In many programs, it is useful to construct a new Map whose keys are identical to an existing Map’s keys but whose values are different from the original map’s. As a little example, let’s construct a Map from Finnish words to the lengths of their English translations’:

val lengthOfEnglish = finToEng.map( (fin, eng) => fin -> eng.length )lengthOfEnglish: Map[String,Int] = Map(kissa -> 3, tapiiri -> 5, koira -> 3)

We give the map method a function that leaves the first member of each key–value pair untouched.

Flipping a Map

A frequently asked question: how can you make a Map whose keys are the values of an existing Map and whose values are the original Map’s keys?

In simple cases, that’s easy enough to do, especially if you use the swap method that’s available on pairs and works like this:

val myPair = "key" -> "value"myPair: (String, String) = (key,value)
myPair.swapres37: (String, String) = (value,key)

Here’s the swap operation applied to an entire Map:

val finnishToEnglish = Map("kissa" -> "cat", "koira" -> "dog", "laama" -> "llama")finnishToEnglish: Map[String,String] = Map(kissa -> cat, koira -> dog, laama -> llama)
val englishToFinnish = finnishToEnglish.map( _.swap )englishToFinnish: Map[String,String] = Map(cat -> kissa, dog -> koira, llama -> laama)

We call swap on every key–value pair.

If you do something like this, watch out: the keys of a map are unique. If our mini-dictionary had contained multiple words that translate to the same English word, we would have lost information while swapping. (Try it.)

If you want a key to be associated with multiple values, you can pair the key with a collection that holds all those values. You may also want to explore existing libraries. (Search for scala multidict.)

What If You Don’t Find a Key?

When you use a map, you often need to be alert to the possibility that the key you’re looking for is not present. There are several alternative ways of dealing with that contingency.

You already know that a Map’s get method returns an Option, which is None in case the key wasn’t found:

finToEng.get("Mikki-Hiiri")res38: String = None

Often, you’ll do fine calling get and using the Option it returns. But depending on what you’re trying to achieve, there may be better alternatives.

The getOrElse method

One way to deal with missing values is to use getOrElse instead. This method greatly resembles the method of the same name on Options (Chapter 4.3).

On Options, the getOrElse method essentially tells the Option object: “Give me the value you contain or, failing that, use this value instead.” The getOrElse method of a Map similarly tells the Map: “Give me the value that corresponds to this key or, failing that, use this value instead.”

finToEng.getOrElse("kissa", "unknown word")res39: String = cat
finToEng.getOrElse("Mikki-Hiiri", "unknown word")res40: String = unknown word

We give getOrElse the search key and a “default value” that should match the type of the Map’s values.

If the key is present in the Map, getOrElse returns the corresponding value.

If the key isn’t present, the method returns the value of its second parameter.

The return type is String rather than Option[String]. We don’t need an Option wrapper since we have a meaningful String value in both cases. Lovely.

The default method apply (and its dangers)

You’re already used to indexing collections with expressions like myCollection(index), which Chapter 5.3 revealed to be shorthand for method calls like myCollection.apply(index). As you learned then, apply is a sort of implicit “default method” for objects.

Maps, too, have an apply method. It works much like get, but there is a substantial difference. Compare:

val engToFin = Map("kissa" -> "cat", "tapiiri" -> "tapir", "koira" -> "dog")engToFin: Map[String,String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat)
engToFin("tapiiri")res41: String = tapir
engToFin("Mikki-Hiiri")java.util.NoSuchElementException: key not found: Mikki-Hiiri
   ...
   at scala.collection.mutable.HashMap.apply(HashMap.scala:64)
   ...
engToFin.get("kissa")res42: Option[String] = Some(cat)
engToFin.get("Mikki-Hiiri")res43: Option[String] = None

The nice thing about apply, compared to get, it gives you a plain result without an Option, so the return value is a little bit easier to work with. The not-nice-at-all thing about apply is that it causes a runtime error if you pass in a non-existent key, so you need to be extra careful when you use this method.

get is usually the better and safer choice.

get — good or bad?

So, the get method of Map objects is good? Even though the get method of Option objects is bad (as discussed in the optional sections of 4.4 and 8.3)?

Yes, that’s right.

Practice on get, apply, and getOrElse

Suppose we’ve created a Map and a variable that refers to it:

val finnishScrabble = Map('A'->10, 'I'->10, 'N'->9, 'S'->7, 'T'->9, 'E'->8, 'K'->5, 'L'->5, 'O'->5,
                          'Ä'->5,  'U'->4,  'M'->3, 'H'->2, 'J'->2, 'P'->2, 'R'->2, 'U'->2, 'Y'->2)

Which of the claims below are correct?

A Map in an Instance Variable

You can use Maps as building blocks for your own classes. A simple example is shown below; you’ll see additional examples in later chapters.

Example: societies and their members

We’ll use the Member class from Chapter 4.4 as part of this example. Here is the relevant code:

class Member(val id: Int, val name: String, val yearOfBirth: Int, val yearOfDeath: Option[Int]):
  // etc.

Now, let’s write another class, Society, that stores the members of a society in an instance variable that refers to a Map.

class Society(val name: String):

  private val members = Map[Int, Member]()

  def add(newMember: Member) =
    this.members(newMember.id) = newMember

  def getByID(memberID: Int) = this.members.get(memberID)

end Society

Each Society object has a name. It also has a Map whose values are the society’s members and whose keys are the members’ ID numbers. For a newly created Society object, this Map is empty.

The Society object has methods for adding members and finding existing members by their ID. These methods have been implemented by calling the Map’s methods.

Mini-assignment: Maps and Option

You’ll find Society in module Miscellaneous. Add a yearOfDeath method to the class. The method should:

  • receive a member ID as a parameter;

  • return an Option[Int] that wraps the year of death of the member with the given ID; except that

  • if the member doesn’t exist or is not dead yet, the method should return None.

Don’t make any other changes to Society. Don’t edit Member.

Hint: there is a method that supplies a simple solution. It was introduced in a recent chapter.

A+ presents the exercise submission form here.

Optional Reading

Setting a default value on a Map

When we call getOrElse, we pass in a “default value”, which the method uses in case the key isn’t found. We can also associate a Map with a generic default value. For instance, we might wish our dictionary to default to the string "not found" on any look-up of any non-existent key. The method withDefaultValue does just that:

val engToFin = Map("kissa" -> "cat", "tapiiri" -> "tapir", "koira" -> "dog").withDefaultValue("not found")engToFin: Map[String,String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat)
engToFin("kissa")res44: String = cat
engToFin("Mikki-Hiiri")res45: String = not found

We use withDefaultValue to indicate which value the map should default to.

Now when we apply for a missing key, we get this default value.

Suppose we create finnishScrabble as before and further define finnishScrabble2 as shown below:

val finnishScrabble = Map('A'->10, 'I'->10, 'N'->9, 'S'->7, 'T'->9, 'E'->8, 'K'->5, 'L'->5, 'O'->5,
                          'Ä'->5,  'U'->4,  'M'->3, 'H'->2, 'J'->2, 'P'->2, 'R'->2, 'U'->2, 'Y'->2)
val finnishScrabble2 = finnishScrabble.withDefaultValue(1)

Which of the claims below are correct?

What’s the hash?

The “hash” in HashMap has nothing to do with social media or other pastimes. It refers to a particular way of implementing Maps.

In the Scala API, the data type Map is defined as a trait with multiple abstract methods: it specifies what all Maps can do without specifying how any Maps actually implement those things. HashMap, in turn, is a concrete class that implements the abstract methods of the Map trait using an implementation strategy known as hashing (hajautus). The Maps we’ve created have had both the general type Map and its subtype HashMap.

This chapter’s introductory section mentioned in passing that the two-buffer dictionary implementation wasn’t too efficient, because it processed each index in turn and any key–value pair could appear just anywhere in the buffers. In a typical scenario, a HashMap is more efficient because it organizes the key–value pairs cleverly so that the key suggests where to find the value.

In O1, we gloss over most efficiency concerns and won’t cover hashing in more detail, but you can read more on Wikipedia, for instance, or take Aalto’s Data Structures and Algorithms course.

Summary of Key Points

  • Multiple data items — even items of different types — can be combined into a tuple. A pair is a tuple with two members.

  • Maps are a tremendously useful and common sort of collection. A map contains key–value pairs. It differs from numerically indexed collections in that:

    • a map’s elements don’t have an order determined by running numbers;

    • nor can you use indices to select a particular element of a map. Instead,

    • you commonly use a map via keys: it’s easy and efficient to fetch a value that corresponds to a key.

  • The Scala API gives us a Map class with useful methods.

  • Links to the glossary: tuple, pair; map, key–value pair.

Feedback

Please note that this section must be completed individually. Even if you worked on this chapter with a pair, each of you should submit the form separately.

Credits

Thousands of students have given feedback and so contributed to this ebook’s design. Thank you!

The ebook’s chapters, programming assignments, and weekly bulletins have been written in Finnish and translated into English by Juha Sorva.

The appendices (glossary, Scala reference, FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.

The automatic assessment of the assignments has been developed by: (in alphabetical order) Riku Autio, Nikolas Drosdek, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Onni Komulainen, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Joel Toppinen, Anna Valldeoriola Cardó, and Aleksi Vartiainen.

The illustrations at the top of each chapter, and the similar drawings elsewhere in the ebook, are the work of Christina Lassheikki.

The animations that detail the execution Scala programs have been designed by Juha Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio did the technical implementation, relying on Teemu’s Jsvee and Kelmu toolkits.

The other diagrams and interactive presentations in the ebook are by Juha Sorva.

The O1Library software has been developed by Aleksi Lukkarinen, Juha Sorva, and Jaakko Nakaza. Several of its key components are built upon Aleksi’s SMCL library.

The pedagogy of using O1Library for simple graphical programming (such as Pic) is inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and Krishnamurthi and Picturing Programs by Stephen Bloch.

The course platform A+ was originally created at Aalto’s LeTech research group as a student project. The open-source project is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT services; dozens of Aalto students and others have also contributed.

The A+ Courses plugin, which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and implemented by various students in collaboration with O1’s teachers.

For O1’s current teaching staff, please see Chapter 1.1.

Additional credits appear at the ends of some chapters.

a drop of ink
Posting submission...