In the previous chapter, we covered functional programming with Scala and how object-oriented and functional approaches complete each other. We also covered generic classes, which are often used with pattern matching. Finally, we covered how to create user-defined pattern matching and why it is useful.
In this chapter, we will cover the Scala Collection library. We will start by learning how to work with lists, which will make us familiar with some design principles of the whole collections library. Afterward, we'll generalize to sequences and cover some more relevant data structures. At the end, we'll look at how collections relate to monads and how we can use that knowledge to make some powerful abstractions in our code.
Scala's collection library is very rich, being comprised of data structures for very different use cases and performance considerations. It is particularly rich in immutable data structures, which we will be covering in greater detail during this chapter.
Collections available in the Scala collection library inherit from common high-level abstract classes and traits and, as such, share some common functionalities, which makes working with them easier once you become familiar with certain methods and design principles.
By the end of this chapter, you will be able to:
- Identify the Scala collections available in the standard library
- Identify how to abstract sequences by using higher-order functions
- Implement the important design principles for working with Scala collections
Lists are probably the most commonly used data structures in Scala programs. Learning how to work with lists is important both from a data structure standpoint but also as an entry point to designing programs around recursive data structures.
In order
to be able to use l
ists, one must learn how to construct them.
Lists are recursive in nature, and build upon two basic building blocks:
Nil (representing the empty list) and
:: (pronounced cons, from the
cons function of most Lisp dialects).
We will now create Lists in Scala:
- Start the Scala
REPL, which should provide you with a prompt:$ scala
- Create a
listof strings using the following:scala> val listOfStrings = "str1" :: ("str2" :: ("str3" :: Nil)) listOfStrings: List[String] = List(str1, str2, str3) - Show that the
::operation is the right associative by omitting the parentheses and getting the same result:scala> val listOfStrings = "str1" :: "str2" :: "str3" :: Nil listOfStrings: List[String] = List(str1, str2, str3)
- Create lists of different types.
- Show that the
applymethod of theListcompanion object offers a convenient way to create a list from a variable number of arguments:scala> val listOfStrings = List("str1", "str2", "str3") listOfStrings: List[String] = List(str1, str2, str3)
Note
If you are wondering how is it possible for the
:: operator to be right-associative, note that the associativity of an operator is determined by the operator's last character. Operators ending in a colon
: are right-associative. All other operators are left-associative. Since
:: ends with a colon, it is right-associative.
The
List class
provides the
head,
tail, and
isEmpty methods.
head returns the first element of the list, while the
tail method returns the list without its first element. The
isEmpty method
returns
true if the list is empty, and
false otherwise.
head and
tail are only defined for non-empty lists and throw an exception on empty ones.
The
method should return a list with all even integers of list l. Use the
head,
tail, and
isEmpty methods of
List. A possible solution for this problem is the following:
def evenInts(l: List[Int]): List[Int] = {
if (l.isEmpty) l
else if (l.head % 2 == 0) l.head :: evenInts(l.tail)
else evenInts(l.tail)
}Pattern matching is
a powerful mechanism for checking a value against a pattern in Scala and provides an idiomatic way to decompose lists. You can pattern match on
::, which mimics the list structure, or on
List(...) to match all of the list's values.
Let's experiment with pattern matching in the Scala
REPL. Make sure to show examples of both pattern matching with
List(...) and with
::.
One possible example to show is:
val l = List(1, 2, 3, 4, 5) List(a, b, c, d, e) = l val h :: t = l
Using
pattern matching is generally more idiomatic than using
if and
else to structure programs.
Now, we will
implement the method
evenInts again. This time, we will not use the
head,
tail, and
isEmpty methods of
List:
- Open the file where we have written the
evenIntsmethod. - Do not use the
head,tail, andisEmptymethods oflist. - A possible solution for this problem is the following:
def evenInts(l: List[Int]): List[Int] = l match { case h :: t if h % 2 == 0 => h :: evenInts(t) case _ :: t => evenInts(t) case Nil => Nil }
The
List class provides various helpful first-order methods. A first-order method
is one
that does not take a function as an argument. We'll cover some of the most-used methods in the following subsection.
We've learned about
:: to append an element at the head of a list. If we want to
append an element at the end of a list, we can use the
:+ operator. In order to concatenate two lists, we can use the
::: operator. Note, however, that the
:+ operator has a time complexity of
O(n), where
n is the number of
elements in the list. The
::: operator has a time complexity of
O(n),
n being the number of elements in the first list. Note that the
::: operator also has right-associativity, like the
:: operator.
Example code:
scala> val a = List(1, 2, 3) a: List[Int] = List(1, 2, 3) scala> val b = List(4, 5, 6) b: List[Int] = List(4, 5, 6) scala> val c = a ::: b c: List[Int] = List(1, 2, 3, 4, 5, 6) scala> val d = b :+ 7 d: List[Int] = List(4, 5, 6, 7)
Taking the
length of a list is a useful operation. All lists have a definite size and, as such, they provide the
length method that returns their size. We'll be covering potentially infinite data structures in another topic.
Note that
length is an expensive operation on lists, as it needs to traverse the whole list
to find its end, taking time proportional to the number of elements in the list.
If you
require frequent access to the end of a list, it is convenient to reverse it once and work with the result. The
reverse method creates a new list with the elements of the original list reversed. The reverse method has linear complexity.
The
take and
drop methods of
List return arbitrary prefixes or suffixes of a list. They
both take an integer as an argument: the number of
elements to take or drop, respectively.
Example code:
scala> val a = List(1, 2, 3, 4, 5) a: List[Int] = List(1, 2, 3, 4, 5) scala> val b = a.take(2) b: List[Int] = List(1, 2) scala> val c = a.drop(2) c: List[Int] = List(3, 4, 5)
Even though it is
not a common operation for lists, the
List class supports random element selection through its apply method:
scala> val a = List(1, 2, 3, 4, 5) a: List[Int] = List(1, 2, 3, 4, 5) scala> a.apply(2) res0: Int = 3
Since apply is implicitly inserted when an object appears in the function position in a method call, we can also do:
scala> a(2) res1: Int = 3
Use
toString to get
the canonical string representation of a list:
scala> val a = List(1, 2, 3, 4, 5) a: List[Int] = List(1, 2, 3, 4, 5) scala> a.toString res0: String = List(1, 2, 3, 4, 5)
The
mkString method is a
bit more flexible as it allows you to specify the prefix to print before all elements, the separator to print between elements, and the suffix to print after all elements. The
mkString method has two overloaded variants which allow you to drop the prefix and suffix arguments if they're empty strings. You can also call
mkString without arguments if you want an empty string as a separator:
scala> a.mkString("[", ", ", "]")
res1: String = [1, 2, 3, 4, 5]
scala> a.mkString(", ")
res2: String = 1, 2, 3, 4, 5
scala> a.mkString
res3: String = 12345Note
Refer to the Scaladoc for the
scala.collection.
immutable.List class at
https://www.scala-lang.org/api/current/scala/collection/immutable/List.html. If you are interested in other useful methods, you can take a look at what the class has to offer.
In this activity, we
will be building a new mode for the Chatbot that we created on the first day of this book. This new mode will be capable of keeping and updating a
todo list of entries. We will be using
lists as the primary data structure to hold our information, and we want to support at least the following commands:
todo list: Lists all current items the bot is currently aware of.todo new <item description>: Inserts a new TODO item with the provided description.todo done <item number>:Removes the item numbered <item number> from the list. The number of the item should be shown when usingtodolist.todo done <item description>: Removes the item whose description matches <item description>.
- Start by defining a new class that extends
ChatbotMode. It's enough to model our TODO list items as strings, so our new mode could just be defined ascase class TodoList(todos: List[String]) extends ChatbotMode. - Implement the required
processmethod. Regexes might come in handy to parse thelineargument. Depending on the provided input, we want to create a new instance ofTodoListwith the value oftodospossibly modified. ReturnNonein invalid inputs (unrecognizable commands or attempts to delete a non-existent item, for example). - Experiment with your newly defined mode in the previously implemented Chatbot. See how well it plays with the other already defined modes.
In this section, we covered lists in the perspective of one of the major workhorses of Scala programs. We've learned the operations we can perform on lists and covered some idiomatic ways to handle lists in Scala code.