Файл: Programming_in_Scala,_2nd_edition.pdf

The ArrayOps example above was quite artificial, intended only to show the difference to WrappedArray. Normally, you’d never define a value of class ArrayOps. You’d just call a Seq method on an array:

scala> a1.reverse

res4: Array[Int] = Array(3, 2, 1)

The ArrayOps object gets inserted automatically by the implicit conversion. So the line above is equivalent to the following line, where intArrayOps was the conversion that was implicitly inserted previously:

scala> intArrayOps(a1).reverse res5: Array[Int] = Array(3, 2, 1)

This raises the question how the compiler picked intArrayOps over the other implicit conversion to WrappedArray in the line above. After all, both conversions map an array to a type that supports a reverse method, which is what the input specified. The answer to that question is that the two implicit conversions are prioritized. The ArrayOps conversion has a higher priority than the WrappedArray conversion. The first is defined in the Predef object whereas the second is defined in a class scala.LowPriorityImplicits, which is a superclass of Predef. Implicits in subclasses and subobjects take precedence over implicits in base classes. So if both conversions are applicable, the one in Predef is chosen. A very similar scheme, which was described in Section 21.7, works for strings.

So now you know how arrays can be compatible with sequences and how they can support all sequence operations. What about genericity? In Java you cannot write a T[] where T is a type parameter. How then is Scala’s Array[T] represented? In fact a generic array like Array[T] could be at run-time any of Java’s eight primitive array types byte[], short[], char[], int[], long[], float[], double[], boolean[], or it could be an array of objects. The only common run-time type encompassing all of these types is AnyRef (or, equivalently java.lang.Object), so that’s the type to which the Scala compiler maps Array[T]. At run-time, when an element of an array of type Array[T] is accessed or updated there is a sequence of type tests that determine the actual array type, followed by the correct array operation on the Java array. These type tests slow down array operations somewhat. You can expect accesses to generic arrays to be three to four times slower than accesses to primitive or object arrays. This means that if you need maximal performance, you should prefer concrete over generic arrays.

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

Representing the generic array type is not enough, however, There must also be a way to create generic arrays. This is an even harder problem, which requires a little bit of help from you. To illustrate the problem, consider the following attempt to write a generic method that creates an array:

// This is wrong!

def evenElems[T](xs: Vector[T]): Array[T] = { val arr = new Array[T]((xs.length + 1) / 2) for (i <- 0 until xs.length by 2)

arr(i / 2) = xs(i) arr

}

The evenElems method returns a new array that consists of all elements of the argument vector xs that are at even positions in the vector. The first line of the body of evenElems creates the result array, which has the same element type as the argument. So depending on the actual type parameter for T, this could be an Array[Int], or an Array[Boolean], or an array of some of the other primitive types in Java, or an array of some reference type. But these types all have different runtime representations, so how is the Scala runtime going to pick the correct one? In fact, it can’t do that based on the information it is given, because the actual type that corresponds to the type parameter T is erased at runtime. That’s why you will get the following error message if you attempt to compile the code above:

error: cannot find class manifest for element type T val arr = new Array[T]((arr.length + 1) / 2)

ˆ

What’s required here is that you help the compiler by providing a runtime hint of what the actual type parameter of evenElems is. This runtime hint takes the form of a class manifest of type scala.reflect.ClassManifest. A class manifest is a type descriptor object that describes what the top-level class of a type is. Alternatively to class manifests there are also full manifests of type scala.reflect.Manifest, which describe all aspects of a type. But for array creation, only class manifests are needed.

The Scala compiler will generate code to construct and pass class manifests automatically if you instruct it to do so. “Instructing” means that you demand a class manifest as an implicit parameter, like this:

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

def evenElems[T](xs: Vector[T])

(implicit m: ClassManifest[T]): Array[T] = ...

Using an alternative and shorter syntax, you can also demand that the type comes with a class manifest by using a context bound. This means following the type with a colon and the class name ClassManifest, like this:

// This works

def evenElems[T: ClassManifest](xs: Vector[T]): Array[T] = { val arr = new Array[T]((xs.length + 1) / 2)

for (i <- 0 until xs.length by 2) arr(i / 2) = xs(i)

arr

}

The two revised versions of evenElems mean exactly the same. What happens in either case is that when the Array[T] is constructed, the compiler will look for a class manifest for the type parameter T, that is, it will look for an implicit value of type ClassManifest[T]. If such a value is found, the manifest is used to construct the right kind of array. Otherwise, you’ll see an error message like the one shown previously.

Here is an interpreter interaction that uses the evenElems method:

scala> evenElems(Vector(1, 2, 3, 4, 5)) res6: Array[Int] = Array(1, 3, 5)

scala> evenElems(Vector("this", "is", "a", "test", "run")) res7: Array[java.lang.String] = Array(this, a, run)

In both cases, the Scala compiler automatically constructed a class manifest for the element type (first Int, then String) and passed it to the implicit parameter of the evenElems method. The compiler can do that for all concrete types, but not if the argument is itself another type parameter without its class manifest. For instance, the following fails:

scala> def wrap[U](xs: Vector[U]) = evenElems(xs) <console>:6: error: could not find implicit value for

evidence parameter of type ClassManifest[U] def wrap[U](xs: Vector[U]) = evenElems(xs)

ˆ

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

What happened here is that the evenElems demands a class manifest for the type parameter U, but none was found. The solution in this case is, of course, to demand another implicit class manifest for U. So the following works:

scala> def wrap[U: ClassManifest](xs: Vector[U]) = evenElems(xs)

wrap: [U](xs: Vector[U])(implicit evidence$1: ClassManifest[U])Array[U]

This example also shows that the context bound in the definition of U is just a shorthand for an implicit parameter named here evidence$1 of type

ClassManifest[U].

In summary, generic array creation demands class manifests. Whenever you create an array of a type parameter T, you also need to provide an implicit class manifest for T. The easiest way to do this is to declare the type parameter with a ClassManifest context bound, as in [T: ClassManifest].

24.12 Strings

Like arrays, strings are not directly sequences, but they can be converted to them, and they also support all sequence operations. Here are some examples of operations you can invoke on strings:

scala> val str = "hello"

str: java.lang.String = hello

scala> str.reverse res6: String = olleh

scala> str.map(_.toUpper) res7: String = HELLO

scala> str drop 3 res8: String = lo

scala> str slice (1, 4) res9: String = ell

scala> val s: Seq[Char] = str

s: Seq[Char] = WrappedString(h, e, l, l, o)

These operations are supported by two implicit conversions, which were explained in Section 21.7. The first, low-priority conversion maps a String

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

to a WrappedString, which is a subclass of immutable.IndexedSeq. This conversion was applied in the last line of the previous example in which a string was converted into a Seq. The other, high-priority conversion maps a string to a StringOps object, which adds all methods on immutable sequences to strings. This conversion was implicitly inserted in the method calls of reverse, map, drop, and slice in the previous example.

24.13Performance characteristics

As the previous explanations have shown, different collection types have different performance characteristics. That’s often the primary reason for picking one collection type over another. You can see the performance characteristics of some common operations on collections summarized in two tables, Table 24.10 and Table 24.11.

The entries in these two tables are explained as follows:

CThe operation takes (fast) constant time.

LThe operation is linear, that is it takes time proportional to the collection size.

-The operation is not supported.

Table 24.10 treats sequence types—both immutable and mutable—with the following operations:

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