Scala Succinctly®
CHAPTER 6
Other Collection Types
Scala has many useful collection types. The most fundamental are the array and the list, but if we want to quickly implement various algorithms, we often use other data types, such as stacks, queues, and maps. In this section, we will look at some of the other useful collection types.
Stacks and Queues
A Stack is a LIFO data structure. We add items to the Stack using the push function, and we remove items using the pop function. The order that items are popped is the opposite of the way they are pushed. For instance, if we push the values 1, 2, and 3, the Stack will return 3, then 2, then 1 when we pop the items.
A Queue is similar to a Stack in that it also allows only two operations. For a Queue, the two operations are enqueue and dequeue. We use enqueue to add items to the Queue, and we use dequeue to remove items. A Queue returns items in the same order they are enqueued. A Queue is sometimes called a FIFO data structure, which is short for first-in-first-out. For instance, if we enqueue the items 1, 2, then 3, a Queue will dequeue them in the same order: 1, 2, then 3.
Code Listing 50 shows some basic operations using a Stack, and Code Listing 51 shows similar operations using a Queue. Note that when we use these data structures (and many others), we need to include an import in order to import the class from the appropriate library.
Code Listing 50: Basic Operations with Stacks
import scala.collection.mutable.Stack object MainObject { def main(args: Array[String]): Unit = { // Define a stack var myStack = new Stack[Int]
// Push a new item to the stack: myStack.push(89) println("Number of items: " + myStack.length) println("Item at the top of the stack: " + myStack.top)
// Push a new item to the stack: myStack.push(21) println("Number of items: " + myStack.length) println("Item at the top of the stack: " + myStack.top)
// Pop off the newest item: var itemFromStack = myStack.pop println("Popped item: " + itemFromStack) println("Number of items: " + myStack.length) println("Item at the top of the stack: " + myStack.top)
// Push a new item to the stack: myStack.push(44) println("Number of items: " + myStack.length) println("Item at the top of the stack: " + myStack.top)
// Pop off all remaining items: // Note: This is a stack, so the items are popped // off in reverse order! while(myStack.length != 0) println("Popped item: " + myStack.pop) } } |
Code Listing 51: Basic Operations with Queues
import scala.collection.mutable.Queue object MainObject { def main(args: Array[String]): Unit = {
// Define a queue: var myQueue = new Queue[Int]
// Add an item to the queue: myQueue.enqueue(47) println("Number of items: " + myQueue.length) println("Item at the front of the queue: " + myQueue.front)
// Add another item to the queue: myQueue.enqueue(83) println("Number of items: " + myQueue.length) println("Item at the front of the queue: " + myQueue.front)
// Remove the oldest item from the queue: var itemFromStack = myQueue.dequeue println("Dequeued item: " + itemFromStack) println("Number of items: " + myQueue.length) println("Item at the front of the queue: " + myQueue.front)
// Add an item to the queue: myQueue.enqueue(23) println("Number of items: " + myQueue.length) println("Item at the front of the queue: " + myQueue.front)
// Loop until the queue is empty: // Note this is a queue, so items will be dequeued // in the same order they were queued! while(myQueue.length != 0) println("Dequeued item: " + myQueue.dequeue) } } |
Sets
Sets are a collection type that hold only distinct elements. Sets are a representation of a mathematical entity with the same name. They are designed to allow the same operations as mathematical sets—except that a mathematical set can be defined as containing an infinite number of items, whereas Scala sets contain a finite number of elements. Code Listing 52 shows some basic operations with sets.
Code Listing 52: Operations with Sets
object MainObject { def main(args: Array[String]): Unit = {
// Define a Set val evenNumbers = Set(2, 4, 6, 8, 10, 12, 14)
// Print out some properties: println("Head: " + evenNumbers.head) println("Tail: " + evenNumbers.tail) println("IsEmpty: " + evenNumbers.isEmpty)
// Testing if the set contains 3: if(evenNumbers.contains(3)) println("Set contains 3!") else println("Set does not contain 3...")
// Test if the set contains 2: if(evenNumbers.contains(2)) println("Set contains 2!") else println("Set does not contain 2...") } } |
In order to join two sets together, we use the ++ operator (the ++ operator forms the mathematical union of two sets). In Code Listing 52, we join a set containing (1, 2, 3) with another containing (3, 4, 5). When we run the program from Code Listing 52, notice that the output shows set3 containing (5, 1, 2, 3, 4). Notice also that although set1 and set2 both contain 3, the concatenated set contains only one copy of 3. Code Listing 53 also shows that we can easily add and remove items using the + and – operators, respectively.
Code Listing 53: Adding and Removing Elements
object MainObject { def main(args: Array[String]): Unit = { // Define some sets: var set1 = Set(1, 2, 3) var set2 = Set(3, 4, 5) // Concatenate with ++ operator: var set3 = set1 ++ set2 // Output the concatenated set: println("Set3: " + set3)
// Adding items to a set: println("Set containing an extra 10: " + (set3 + 10))
// Removing items from a set: println("Joined set without the 3's: " + ((set1 ++ set2) - 3)) } } |
Sets are designed to allow fast item lookups. But the order of the elements in a set is meaningless—notice that when we run the program from Code Listing 53, the final ordering of items, (5, 1, 2, 3, 4), is not the same as the order we specified the items in the original sets (indeed, depending on the implementation of the particular Java Runtime you have installed, the order in my machine might be different than in yours). This is because the implementation of sets employs hashing techniques. If the order of elements in your collection is important, you should not use a set, or you should use the Scala SortedSet collection. However, if you know that every element in your collection will be unique and you want fast item lookups, a Set is perfect.
Mutable sets
By default, we cannot add and remove items from a set—they are immutable (which means the elements are all fixed). Code Listing 53 showed how to add and remove items, but the example actually created a new set, it did not add and remove items from the immutable set. If you want to add and remove items from a set without creating a new set, use a mutable set (which means the elements are not fixed and we are free to change them) by importing scala.collections.mutable.set. In order to add items to a mutable set, we can use the + operator, and to remove items we can use the – operator. Also notice that when we create a mutable set, we do so using var someName = Set[dataType](), where dataType is the type of data the set contains and someName is the identifier we want to use for the set.
Code Listing 54: Adding and Removing Items from a Set
import scala.io.StdIn.readInt import scala.collection.mutable.Set object MainObject { def main(args: Array[String]): Unit = { // Create a mutable set: var setOfInts = Set[Int]() var newNumber = 0
while(newNumber != -1) { // Print a prompt: print("Input a number (use -1 to quit): ")
// Read a new number: newNumber = readInt // If the set contains the new number, remove it: if(setOfInts.contains(newNumber)) setOfInts = setOfInts - newNumber
// Otherwise, add it (if not -1): else if (newNumber != -1) setOfInts = setOfInts + newNumber // Print out the items in the set so far: println("Set contains: " + setOfInts) } } } |
Code Listing 54 shows a program that uses sets to test an interesting phenomenon called “The Birthday Paradox.” The question used to demonstrate the phenomenon is: How many people, on average, would you need in a room before it is likely that at least two people share a birthday? The program in Code Listing 54 uses a set of integers from which we repeatedly generate random birthdays until there is a duplicate. At this point, we record the number of birthdays generated so far, add this to a total, and repeat. The experiment is repeated as many times as specified by the iterations variable—I have set this variable to 1,000,000. The more iterations we repeat, the closer we will get to finding the actual average number of people we would need in a room before two or more of them share a birthday.
The Birthday Paradox is not actually a paradox, but it is surprising how few people are needed in a room before two might share a birthday. The program also demonstrates the speed of sets for looking up items. There are a million trials, and the program will likely finish in a second or two on any modern desktop PC. Each trial contains multiple lookups of a set with many elements.
Code Listing 55: Birthday Paradox Tester
import scala.collection.mutable.Set object MainObject { def main(args: Array[String]): Unit = { // Define a mutable set: var birthdays = Set[Int]()
// Define how many trials to run: var iterations = 1000000
// Set total to 0 birthdays counted so far: var totalBirthdays = 0.0
println("Beginning trials...")
// Repeat the experiment up to iterations times: for(i <- 1 to iterations) {
// Reset the birthdays: var duplicateDetected = false birthdays.clear while(!duplicateDetected) {
// Generate a new random birthday: val newBirthday = (Math.random() * 365.0).toInt
// Check if the birthday exists in the set or not: if(birthdays.contains(newBirthday)) { totalBirthdays += birthdays.size.toDouble duplicateDetected = true } else { // Add the birthday to the set: birthdays += newBirthday } } }
// Output the total and average number of days: println("Total birthays: " + totalBirthdays) println("Average birthdays before duplicate: " + (totalBirthdays / iterations)) } } |
As with mathematical sets, sets in Scala allow us to form new sets by selecting the intersecting items from two sets or from selecting the items that are not shared between sets. Also note that instead of concatenating sets with the ++ operator, we can use the OR operator |. See Code Listing 56 for an example of the &, |, and &~ operators.
Code Listing 56: Set-Like Operations on Sets
import scala.collection.mutable.Set object MainObject { def main(args: Array[String]): Unit = { // Define two sets: var set1 = Set(1, 5, 4, 6, 9) var set2 = Set(5, 3, 7, 1, 6)
// Output the shared elements: // Note: & operator is the same as: set1.intersects(set2) println("Shared elements: " + (set1 & set2))
// Using | combines all elements: println("All Elements: " + (set1 | set2))
// Using &~ filters to items not shared between sets: // Note: &~ is the same as: set1.diff(set2) println("Elements in set1, not in set2: " + (set1 &~ set2)) println("Elements in set2, not in set1: " + (set2 &~ set1)) } } |
We can also filter and count elements in sets that match a particular Boolean expression. Code Listing 57 shows an example of using the filter function.
Code Listing 57: Counting Elements in Filtered Sets
object MainObject { def main(args: Array[String]): Unit = {
// Define a set: val mySet = Set(1, 5, 4, 6, 9)
// Filtering: println("Number of odd elements in mySet: " + mySet.count(x => x % 2 == 1)) println("Number of even elements in mySet: " + mySet.count(x => x % 2 == 0)) // For these operations, we can also create new sets, // instead of just counting elements: val evenNumbers = mySet.filter { x => x % 2 == 0 } val oddNumbers = mySet.filter { x => x % 2 == 1 } println("Set of Even Elements: " + evenNumbers) println("Set of Odd Elements: " + oddNumbers) } } |
Sets are extremely powerful and versatile, and this has necessarily been a brief introduction to them. For more information, consult the Scala documentation for the set class at http://docs.scala-lang.org/overviews/collections/sets.html.
Tuples
A Tuple is a collection of objects that can be of different types and that we can pass and use as a single entity. This is different from other collections, such as Array, that contain objects that all have the same type. Tuples are useful for many things, including returning multiple values from a function—instead of actually defining a function with multiple returns, we can pass a Tuple and modify its values to act as multiple returned values.
Code Listing 58: Defining Tuples
object MainObject { def main(args: Array[String]): Unit = { // Verbose syntax for tuple of 3 elements: val tupleSlow = new Tuple3(2, "Banana", 2.6) // Quick syntax for tuple of 3 elements: val tupleQuick = (1, "Pineapple", 3.5)
// Many element tuple: val oneOne = (1, 1, "was", 'a', "racehorse", 2, 2, "was", 1, 2, 1, 1, 1, 1, "race", 2, 2, 1, 1, 2) } } |
Code Listing 58 shows the definition of three Tuples. The first example shows the verbose syntax in which we use the new operator and define a Tuple in the same way as we would any other object, i.e. calling the constructor and pass parameters.
The second example shows a simpler syntax for Tuples. We can omit the new Tuple3 and simply specify the parameter list in brackets.
The final example uses the quick syntax, but the Tuple has many elements. At the time of writing, the latest version of Scala can contain from 1 to 22 number of elements.
The data type of the Tuple is implied by the items passed to the constructor. So the line new Tuple3(2, "Banana", 2.6) will create a Tuple with data types Int, String, and Double. Likewise, the final example creates a 20-element Tuple with data types (Int, Int, String, Char, …, String, Int, Int, Int, Int, Int).
Accessing elements of a Tuple
Code Listing 59: Accessing Tuple Elements
object MainObject { def main(args: Array[String]): Unit = {
// Define two complex numbers as tuples: var complexNumberA = (1.5, 7.8) var complexNumberB = (2.6, 5.1)
// Multiply them together to get complex product: var complexProduct = ( complexNumberA._1 * complexNumberB._1 - complexNumberA._2 * complexNumberB._2, complexNumberA._1 * complexNumberB._2 + complexNumberA._2 * complexNumberB._1 )
// Output results: println("Complex product of " + complexNumberA + " and " + complexNumberB + " is " + complexProduct) } } |
Code Listing 59 shows an example of accessing elements of tuples. The elements are numbered from 1 to N, where N is the number of items in the Tuple. Note that we define two complex numbers as Tuple2 objects, then we multiply them together to produce the complex product. Notice also the use of complexNumberA._1 in order to access the first element of complexNumberA.
When we print a Tuple to the console, Scala will surround the elements as a comma-separated list with brackets. So, when we print complexNumberA, Scala will output (1.5, 7.8).
Code Listing 60 shows an example of using foreach to iterate over the items in a Tuple. The example will assign the elements of the Tuple to the variable x and will print each element out on a separate line.
Code Listing 60: Iterating over Elements of a Tuple
object MainObject { def main(args: Array[String]): Unit = {
// Define a tuple: val tuple5 = ("One", 2, 3.0f, 4.0, '5')
// Output elements by iterating over tuple: println("Elements of tuple: ") tuple5.productIterator.foreach { x => println(x) } } } |
Note: It may seem awkward to access elements of a tuple as suchAndSuch._1. If you are wondering why we are not able to use the syntax suchAndSuch(1), it is because the ( and ) parentheses define a function implicitly, and functions need to have some specific return type—they are not able to return each of the possible types in the tuple.
Naming elements of a Tuple
We can name the elements of a Tuple, then refer to them by name instead of index. Code Listing 61 shows an example of naming the elements of a Tuple.
Code Listing 61: Naming Elements of a Tuple
object MainObject { def main(args: Array[String]): Unit = {
// Define a tuple: val point3D = (-9.5, 5.6, 7.2)
// Name the elements of the tuple: val (x, y, z) = point3D
// Print out the elements using names: println("Element x: " + x) println("Element y: " + y) println("Element z: " + z) } } |
Notice that in Code Listing 61 the names x, y, and z refer to the elements of the Tuple called point3D. This is not a method for naming the elements of Tuples in general, but only a method for naming the elements of a specific Tuple.
Two elements Tuples shortcut
Code Listing 62 shows a shorthand for creating Tuple2 objects. We use the syntax “element1 -> element2” as in the definition of point2D. Note that we cannot create a Tuple3 this way. The line val point3D = -9.5 -> 5.6 -> 7.2 actually creates a Tuple2 inside another Tuple2: ((-9.5, 5.6), 7.2).
Code Listing 62: Shorthand for Tuple2
object MainObject { def main(args: Array[String]): Unit = { // Short hand for two element tuple: val point2D = -9.5 -> 5.6
// Be careful, the following is not a Tuple3! val point3D = -9.5 -> 5.6 -> 7.2
// Print out the tuples: println(point2D) println(point3D) } } |
Maps and Tuples
One of the most common uses of Tuples is with Maps. A Map is a collection of Key/Value pairs, which means Tuple2 is perfect. Maps are sometimes called mappings or associations; they represent a mapping of the keys to the values.
Maps come in two flavors: Immutable and Mutable. The default is Immutable, and in order to use a Mutable map, you should use import scala.collection.mutable.map. Code Listing 63 shows some examples of how to use an Immutable Map. Note that once an Immutable Map is created, the items are fixed.
Code Listing 63: Immutable Maps
object MainObject { def main(args: Array[String]): Unit = {
// Immutable map: val staff = Map(1 -> "Tom", 2 -> "Tim", 3 -> "Jenny") val staff2 = Map(10 -> "Geoff", 7 -> "Sara")
// Print out some info the staff map: println("Keys: " + staff.keys) println("Values: " + staff.values) println("IsEmpty: " + staff.isEmpty)
// Concatenate two maps with the ++ operator: val staffConcat = staff ++ staff2 println("All staff: " + staffConcat.values)
// Access values by key: println("Element with key 1: " + staffConcat(1)) println("Element with key 7: " + staffConcat(7)) // The following will throw an exception because the key // does not exist: // println("Element with key 12: " + staffConcat(12))
// To check if a key exists: if(staffConcat.contains(12)) println("Element with key 12: " + staffConcat(12)) else println("Element with key 12: Does not exist!")
// Removing elements by key: val timGotFired = staffConcat - 2 // 2 is the key for Tim // Now timGotFired will be the same as staffConcat, but Tim has // been removed: println(timGotFired) } } |
Note: As with Sets, Scala’s Maps are extremely useful and fast. There are many operations available for them, and the interested reader should have a look at http://docs.scala-lang.org/overviews/collections/maps.html for more information.
Mutable Maps
Mutable Maps are essentially the same as Immutable Maps, except that we can add and remove items without creating a new map each time.
Code Listing 64: Mutable Maps
import scala.collection.mutable.Map object MainObject { def main(args: Array[String]): Unit = {
// Create a new map object: val staff: Map[Int, String] = Map()
// Adding tuples (key/value pairs) to a map with += staff += (5 -> "Teddy") staff += (1 -> "Rene") staff += new Tuple2(3, "Ronnie")
// Print out some info on the map: println("Keys: " + staff.keys) println("Values: " + staff.values) println("IsEmpty? " + staff.isEmpty)
// To remove an item by key: staff -= 5 println(staff) // Teddy got fired!
staff += (5 -> "Dean") // Dean took Teddy's old key. // We are not able to add multiple items with the // same key so the following is illegal: // staff += (5, "Teddy")
// Iterating through a map: for(i <- staff.keys) { println("Staff Member ID: " + i + " -> " + staff(i)) } // To set map elements, we use map(x)=xyz for(i <- staff.keys) { staff(i) = "Teddy" }
println(staff) } } |
Code Listing 64 shows the use of a Mutable map. The only real difference is that Mutuable maps can add items and change the values of the keys. Also, note that the operations for Maps are the same as those for sets because the keys for a map are a Set.
There are many other types of collection available in Scala. Each has a different implementation and is designed for different types of data and algorithms. The interested reader can visit the page http://docs.scala-lang.org/overviews/collections/concrete-mutable-collection-classes.html for more information on the available collection types.
- 1800+ high-performance UI components.
- Includes popular controls such as Grid, Chart, Scheduler, and more.
- 24x5 unlimited support by developers.