Odersky M. Programming in Scala
Подождите немного. Документ загружается.
Section 16.5 Chapter 16 · Working with Lists 331
About pattern matching on Lists
If you review the possible forms of patterns explained in Chapter 15,
you might find that neither List(...) nor :: looks like it fits one of
the kinds of patterns defined there. In fact, List(...) is an instance
of a library-defined extractor pattern. Such patterns will be treated in
Chapter 24. The “cons” pattern x :: xs is a special case of an infix
operation pattern. You know already that, when seen as an expression,
an infix operation is equivalent to a method call. For patterns, the rules
are different: When seen as a pattern, an infix operation such as p op q
is equivalent to op(p, q). That is, the infix operator op is treated as
a constructor pattern. In particular, a cons pattern such as x :: xs is
treated as ::(x, xs). This hints that there should be a class named ::
that corresponds to the pattern constructor. Indeed there is such as class.
It is named scala.:: and is exactly the class that builds non-empty
lists. So :: exists twice in Scala, once as a name of a class in package
scala, and again as a method in class List. The effect of the method
:: is to produce an instance of the class scala.::. You’ll find out more
details about how the List class is implemented in Chapter 22.
scala> val a :: b :: rest = fruit
a: String = apples
b: String = oranges
rest: List[String] = List(pears)
Taking lists apart with patterns is an alternative to taking them apart with the
basic methods head, tail, and isEmpty. For instance, here’s insertion sort
again, this time written with pattern matching:
def isort(xs: List[Int]): List[Int] = xs match {
case List() => List()
case x :: xs1 => insert(x, isort(xs1))
}
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
case List() => List(x)
case y :: ys => if (x <= y) x :: xs
else y :: insert(x, ys)
}
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 332
Often, pattern matching over lists is clearer than decomposing them with
methods, so pattern matching should be a part of your list processing toolbox.
This is all you need to know about lists in Scala to be able to use them
correctly. However, there are also a large number of methods that capture
common patterns of operations over lists. These methods make list process-
ing programs more concise and often clearer. The next two sections present
the most important methods defined in the List class.
16.6 First-order methods on class List
This section explains most first-order methods defined in the List class. A
method is first-order if it does not take any functions as arguments. The
section also introduces by means of two examples some recommended tech-
niques to structure programs that operate on lists.
Concatenating lists
An operation similar to :: is list concatenation, written ‘:::’. Unlike ::,
::: takes two lists as operands. The result of xs ::: ys is a new list that
contains all the elements of xs, followed by all the elements of ys. Here are
some examples:
scala> List(1, 2) ::: List(3, 4, 5)
res0: List[Int] = List(1, 2, 3, 4, 5)
scala> List() ::: List(1, 2, 3)
res1: List[Int] = List(1, 2, 3)
scala> List(1, 2, 3) ::: List(4)
res2: List[Int] = List(1, 2, 3, 4)
Like cons, list concatenation associates to the right. An expression like this:
xs ::: ys ::: zs
is interpreted like this:
xs ::: (ys ::: zs)
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 333
The Divide and Conquer principle
Concatenation (:::) is implemented as a method in class List. It would also
be possible to implement concatenation “by hand,” using pattern matching
on lists. It’s instructive to try to do that yourself, because it shows a common
way to implement algorithms using lists. First, we’ll settle on a signature
for the concatenation method, which we’ll call append. In order not to mix
things up too much, assume that append is defined outside the List class.
So it will take the two lists to be concatenated as parameters. These two
lists must agree on their element type, but that element type can be arbitrary.
This can be expressed by giving append a type parameter
3
that represents
the element type of the two input lists:
def append[T](xs: List[T], ys: List[T]): List[T]
To design the implementation of append, it pays to remember the “divide
and conquer” design principle for programs over recursive data structures
such as lists. Many algorithms over lists first split an input list into simpler
cases using a pattern match. That’s the divide part of the principle. They
then construct a result for each case. If the result is a non-empty list, some of
its parts may be constructed by recursive invocations of the same algorithm.
That’s the conquer part of the principle.
To apply this principle to the implementation of the append method, the
first question to ask is on which list to match. This is less trivial in the case of
append than for many other methods because there are two choices. How-
ever, the subsequent “conquer” phase tells you that you need to construct a
list consisting of all elements of both input lists. Since lists are constructed
from the back towards the front, ys can remain intact whereas xs will need
to be taken apart and prepended to ys. Thus, it makes sense to concentrate
on xs as a source for a pattern match. The most common pattern match over
lists simply distinguishes an empty from a non-empty list. So this gives the
following outline of an append method:
def append[T](xs: List[T], ys: List[T]): List[T] =
xs match {
case List() => // ??
case x :: xs1 => // ??
}
3
Type parameters will be explained in more detail in Chapter 19.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 334
All that remains is to fill in the two places marked with “??”. The first
such place is the alternative where the input list xs is empty. In this case
concatenation yields the second list:
case List() => ys
The second place left open is the alternative where the input list xs consists
of some head x followed by a tail xs1. In this case the result is also a non-
empty list. To construct a non-empty list you need to know what the head
and the tail of that list should be. You know that the first element of the result
list is x. As for the remaining elements, these can be computed by appending
the rest of the first list, xs1, to the second list ys. This completes the design
and gives:
def append[T](xs: List[T], ys: List[T]): List[T] =
xs match {
case List() => ys
case x :: xs1 => x :: append(xs1, ys)
}
The computation of the second alternative illustrated the “conquer” part of
the divide and conquer principle: Think first what the shape of the desired
output should be, then compute the individual parts of that shape, using re-
cursive invocations of the algorithm where appropriate. Finally, construct
the output from these parts.
Taking the length of a list: length
The length method computes the length of a list.
scala> List(1, 2, 3).length
res3: Int = 3
On lists, unlike arrays, length is a relatively expensive operation. It needs to
traverse the whole list to find its end and therefore takes time proportional to
the number of elements in the list. That’s why it’s not a good idea to replace
a test such as xs.isEmpty by xs.length == 0. The result of the two tests
are equivalent, but the second one is slower, in particular if the list xs is long.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 335
Accessing the end of a list: init and last
You know already the basic operations head and tail, which respectively
take the first element of a list, and the rest of the list except the first element.
They each have a dual operation: last returns the last element of a (non-
empty) list, whereas init returns a list consisting of all elements except the
last one:
scala> val abcde = List('a', 'b', 'c', 'd', 'e')
abcde: List[Char] = List(a, b, c, d, e)
scala> abcde.last
res4: Char = e
scala> abcde.init
res5: List[Char] = List(a, b, c, d)
Like head and tail, these methods throw an exception when applied to an
empty list:
scala> List().init
java.lang.UnsupportedOperationException: Nil.init
at scala.List.init(List.scala:544)
at ...
scala> List().last
java.util.NoSuchElementException: Nil.last
at scala.List.last(List.scala:563)
at ...
Unlike head and tail, which both run in constant time, init and last need
to traverse the whole list to compute their result. They therefore take time
proportional to the length of the list.
It’s a good idea to organize your data so that most accesses
are at the head of a list, rather than the last element.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 336
Reversing lists: reverse
If at some point in the computation an algorithm demands frequent accesses
to the end of a list, it’s sometimes better to reverse the list first and work with
the result instead. Here’s how to do the reversal:
scala> abcde.reverse
res6: List[Char] = List(e, d, c, b, a)
Note that, like all other list operations, reverse creates a new list rather than
changing the one it operates on. Since lists are immutable, such a change
would not be possible, anyway. To verify this, check that the original value
of abcde is unchanged after the reverse operation:
scala> abcde
res7: List[Char] = List(a, b, c, d, e)
The reverse, init, and last operations satisfy some laws which can be
used for reasoning about computations and for simplifying programs.
1. reverse is its own inverse:
xs.reverse.reverse equals xs
2. reverse turns init to tail and last to head, except that the ele-
ments are reversed:
xs.reverse.init equals xs.tail.reverse
xs.reverse.tail equals xs.init.reverse
xs.reverse.head equals xs.last
xs.reverse.last equals xs.head
Reverse could be implemented using concatenation (:::), like in the follow-
ing method, rev:
def rev[T](xs: List[T]): List[T] = xs match {
case List() => xs
case x :: xs1 => rev(xs1) ::: List(x)
}
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 337
However, this method is less efficient than one would hope for. To study
the complexity of rev, assume that the list xs has length n. Notice that
there are n recursive calls to rev. Each call except the last involves a list
concatenation. List concatenation xs ::: ys takes time proportional to the
length of its first argument xs. Hence, the total complexity of rev is:
n + (n − 1)+ ... + 1 = (1 + n) ∗ n/2
In other words, rev’s complexity is quadratic in the length of its input ar-
gument. This is disappointing when compared to the standard reversal of a
mutable, linked list, which has linear complexity. However, the current im-
plementation of rev is not the best implementation possible. You will see in
Section 16.7 how to speed it up.
Prefixes and suffixes: drop, take and splitAt
The drop and take operations generalize tail and init in that they return
arbitrary prefixes or suffixes of a list. The expression “xs take n” returns
the first n elements of the list xs. If n is greater than xs.length, the whole
list xs is returned. The operation “xs drop n” returns all elements of the list
xs except the first n ones. If n is greater than xs.length, the empty list is
returned.
The splitAt operation splits the list at a given index, returning a pair of
two lists.
4
It is defined by the equality:
xs splitAt n equals (xs take n, xs drop n)
However, splitAt avoids traversing the list xs twice. Here are some exam-
ples of these three methods:
scala> abcde take 2
res8: List[Char] = List(a, b)
scala> abcde drop 2
res9: List[Char] = List(c, d, e)
scala> abcde splitAt 2
res10: (List[Char], List[Char]) = (List(a, b),List(c, d, e))
4
As mentioned in Section 10.12, the term pair is an informal name for Tuple2.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 338
Element selection: apply and indices
Random element selection is supported through the apply method; however
it is a less common operation for lists than it is for arrays.
scala> abcde apply 2 // rare in Scala
res11: Char = c
As for all other types, apply is implicitly inserted when an object appears in
the function position in a method call, so the line above can be shortened to:
scala> abcde(2) // rare in Scala
res12: Char = c
One reason why random element selection is less popular for lists than for
arrays is that xs(n) takes time proportional to the index n. In fact, apply is
simply defined by a combination of drop and head:
xs apply n equals (xs drop n).head
This definition also makes clear that list indices range from 0 up to the length
of the list minus one, the same as for arrays. The indices method returns a
list consisting of all valid indices of a given list:
scala> abcde.indices
res13: List[Int] = List(0, 1, 2, 3, 4)
Zipping lists: zip
The zip operation takes two lists and forms a list of pairs:
scala> abcde.indices zip abcde
res14: List[(Int, Char)] = List((0,a), (1,b), (2,c), (3,d),
(4,e))
If the two lists are of different length, any unmatched elements are dropped:
scala> val zipped = abcde zip List(1, 2, 3)
zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))
A useful special case is to zip a list with its index. This is done most effi-
ciently with the zipWithIndex method, which pairs every element of a list
with the position where it appears in the list.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 339
scala> abcde.zipWithIndex
res15: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3),
(e,4))
Displaying lists: toString and mkString
The toString operation returns the canonical string representation of a list:
scala> abcde.toString
res16: String = List(a, b, c, d, e)
If you want a different representation you can use the mkString method. The
operation xs mkString (pre, sep, post) involves four operands: the list
xs to be displayed, a prefix string pre to be displayed in front of all elements,
a separator string sep to be displayed between successive elements, and a
postfix string post to be displayed at the end. The result of the operation is
the string:
pre + xs(0) + sep + . . . + sep + xs(xs.length - 1) + post
The mkString method has two overloaded variants that let you drop some
or all of its arguments. The first variant only takes a separator string:
xs mkString sep equals xs mkString ("", sep, "")
The second variant lets you omit all arguments:
xs.mkString equals xs mkString ""
Here are some examples:
scala> abcde mkString ("[", ",", "]")
res17: String = [a,b,c,d,e]
scala> abcde mkString ""
res18: String = abcde
scala> abcde.mkString
res19: String = abcde
scala> abcde mkString ("List(", ", ", ")")
res20: String = List(a, b, c, d, e)
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.6 Chapter 16 · Working with Lists 340
There are also variants of the mkString methods called addString which
append the constructed string to a StringBuilder object,
5
rather than re-
turning them as a result:
scala> val buf = new StringBuilder
buf: StringBuilder =
scala> abcde addString (buf, "(", ";", ")")
res21: StringBuilder = (a;b;c;d;e)
The mkString and addString methods are inherited from List’s super trait
Iterable, so they are applicable to all sorts of iterable collections.
Converting lists: elements, toArray, copyToArray
To convert data between the flat world of arrays and the recursive world of
lists, you can use method toArray in class List and toList in class Array:
scala> val arr = abcde.toArray
arr: Array[Char] = Array(a, b, c, d, e)
scala> arr.toString
res22: String = Array(a, b, c, d, e)
scala> arr.toList
res23: List[Char] = List(a, b, c, d, e)
There’s also a method copyToArray, which copies list elements to succes-
sive array positions within some destination array. The operation:
xs copyToArray (arr, start)
copies all elements of the list xs to the array arr, beginning with position
start. You must ensure that the destination array arr is large enough to
hold the list in full. Here’s an example:
scala> val arr2 = new Array[Int](10)
arr2: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
scala> List(1, 2, 3) copyToArray (arr2, 3)
scala> arr2.toString
res25: String = Array(0, 0, 0, 1, 2, 3, 0, 0, 0, 0)
5
This is class scala.StringBuilder, not java.lang.StringBuilder.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index