Файл: Programming_in_Scala,_2nd_edition.pdf

Listing 22.6 · The definition of the :: subclass of List.

of a cons cell. In fact the elements of a list buffer are represented as a list and appending new elements involves a modification of tl field of the last :: cell in that list. Here’s the start of class ListBuffer:

package scala.collection.immutable

final class ListBuffer[T] extends Buffer[T] { private var start: List[T] = Nil

private var last0: ::[T] = _

private var exported: Boolean = false

...

You see three private fields that characterize a ListBuffer:

start points to the list of all elements stored in the buffer last0 points to the last :: cell in that list

exported indicates whether the buffer has been turned into a list using a toList operation

The toList operation is very simple:

override def toList: List[T] = { exported = !start.isEmpty start

}

It returns the list of elements referred to by start and also sets exported to true if that list is nonempty. So toList is very efficient, because it does not copy the list which is stored in a ListBuffer. But what happens if the list is further extended after the toList operation? Of course, once a list

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

is returned from toList, it must be immutable. However, appending to the last0 element will modify the list which is referred to by start.

To maintain the correctness of the list buffer operations, you need to work on a fresh list instead. This is achieved by the first line in the implementation of the += operation:

override def += (x: T) { if (exported) copy() if (start.isEmpty) {

last0 = new scala.::(x, Nil) start = last0

}else {

val last1 = last0

last0 = new scala.::(x, Nil)

last1.tl = last0

}

}

You see that += copies the list pointed to by start if exported is true. So, in the end, there is no free lunch. If you want to go from lists which can be extended at the end to immutable lists, there needs to be some copying. However, the implementation of ListBuffer is such that copying is necessary only for list buffers that are further extended after they have been turned into lists. This case is quite rare in practice. Most use cases of list buffers add elements incrementally and then do one toList operation at the end. In such cases, no copying is necessary.

22.4 Functional on the outside

The previous section showed key elements of the implementation of Scala’s List and ListBuffer classes. You saw that lists are purely functional on the “outside” but have an imperative implementation using list buffers on the “inside.” This is a typical strategy in Scala programming: trying to combine purity with efficiency by carefully delimiting the effects of impure operations. You might ask, why insist on purity? Why not just open up the definition of lists, making the tail field, and maybe also the head field, mutable? The disadvantage of such an approach is that it would make programs

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

much more fragile. Note that constructing lists with :: re-uses the tail of the constructed list. So when you write:

val ys = 1 :: xs val zs = 2 :: xs

the tails of lists ys and zs are shared; they point to the same data structure. This is essential for efficiency; if the list xs was copied every time you added a new element onto it, this would be much slower. Because sharing is pervasive, changing list elements, if it were possible, would be quite dangerous. For instance, taking the code above, if you wanted to truncate list ys to its first two elements by writing:

ys.drop(2).tail = Nil // can’t do this in Scala!

you would also truncate lists zs and xs as a side effect. Clearly, it would be quite difficult to keep track of what gets changed. That’s why Scala opts for pervasive sharing and no mutation for lists. The ListBuffer class still allows you to build up lists imperatively and incrementally, if you wish to. But since list buffers are not lists, the types keep mutable buffers and immutable lists separate.

The design of Scala’s List and ListBuffer is quite similar to what’s done in Java’s pair of classes String and StringBuffer. This is no coincidence. In both situations the designers wanted to maintain a pure immutable data structure but also wanted to provide an efficient way to construct this structure incrementally. For Java and Scala strings, StringBuffers (or, in Java 5, StringBuilders) provide a way to construct a string incrementally. For Scala’s lists, you have a choice: You can either construct lists incrementally by adding elements to the beginning of a list using ::, or you use a list buffer for adding elements to the end. Which one is preferable depends on the situation. Usually, :: lends itself well to recursive algorithms in the divide-and-conquer style. List buffers are often used in a more traditional loop-based style.

22.5 Conclusion

In this chapter, you saw how lists are implemented in Scala. List is one of the most heavily used data structures in Scala, and it has a refined implementation. List’s two subclasses, Nil and ::, are both case classes. Instead of

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

recursing through this structure, however, many core list methods are implemented using a ListBuffer. ListBuffer, in turn, is carefully implemented so that it can efficiently build lists without allocating extraneous memory. It is functional on the outside, but uses mutation internally to speed up the common case where a buffer is discarded after toList is been called. After studying all of this, you now know the list classes inside and out, and you might have learned an implementation trick or two.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Chapter 23

For Expressions Revisited

Chapter 16 demonstrated that higher-order functions such as map, flatMap, and filter provide powerful constructions for dealing with lists. But sometimes the level of abstraction required by these functions makes a program a bit hard to understand. Here’s an example. Say you are given a list of persons, each defined as an instance of a class Person. Class Person has fields indicating the person’s name, whether (s)he is male, and his/her children. Here’s the class definition:

scala> case class Person(name: String, isMale: Boolean, children: Person*)

Here’s a list of some sample persons:

val lara = Person("Lara", false) val bob = Person("Bob", true)

val julie = Person("Julie", false, lara, bob) val persons = List(lara, bob, julie)

Now, say you want to find out the names of all pairs of mothers and their children in that list. Using map, flatMap and filter, you can formulate the following query:

scala> persons filter (p => !p.isMale) flatMap (p => (p.children map (c => (p.name, c.name))))

res0: List[(String, String)] = List((Julie,Lara), (Julie,Bob))

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

You could optimize this example bit by using a withFilter call instead of filter. This would avoid the creation of an intermediate data structure for male persons:

scala> persons withFilter (p => !p.isMale) flatMap (p => (p.children map (c => (p.name, c.name))))

res1: List[(String, String)] = List((Julie,Lara), (Julie,Bob))

These queries do their job, but they are not exactly trivial to write or understand. Is there a simpler way? In fact, there is. Remember the for expressions in Section 7.3? Using a for expression, the same example can be written as follows:

scala> for (p <- persons; if !p.isMale; c <- p.children) yield (p.name, c.name)

res2: List[(String, String)] = List((Julie,Lara), (Julie,Bob))

The result of this expression is exactly the same as the result of the previous expression. What’s more, most readers of the code would likely find the for expression much clearer than the previous query, which used the higherorder functions, map, flatMap, and withFilter.

However, the last two queries are not as dissimilar as it might seem. In fact, it turns out that the Scala compiler will translate the second query into the first one. More generally, all for expressions that yield a result are translated by the compiler into combinations of invocations of the higher-order methods map, flatMap, and withFilter. All for loops without yield are translated into a smaller set of higher-order functions: just withFilter and foreach.

In this chapter, you’ll find out first about the precise rules of writing for expressions. After that, you’ll see how they can make combinatorial problems easier to solve. Finally, you’ll learn how for expressions are translated, and how as a result, for expressions can help you “grow” the Scala language into new application domains.

23.1 For expressions

Generally, a for expression is of the form:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index