Odersky M. Programming in Scala
Подождите немного. Документ загружается.
Section 21.6 Chapter 21 · Implicit Conversions and Parameters 481
A style rule for implicit parameters As a style rule, it is best to use a
custom named type in the types of implicit parameters. For example, the
types of prompt and drink in the previous example was not String, but
PreferredPrompt and PreferredDrink, respectively. As a counterexam-
ple, consider that the maxListImpParm function could just as well have been
written with the following type signature:
def maxListPoorStyle[T](elments: List[T])
(implicit orderer: (T, T) => Boolean): T
To use this version of the function, though, the caller would have to supply an
orderer parameter of type (T, T) => Boolean. This is a fairly generic type
that includes any function from two Ts to a Boolean. It does not indicate
anything at all about what the type is for; it could be an equality test, a less-
than test, a greater-than test, or something else entirely.
The actual code for maxListImpParm, given in Listing 21.3, shows bet-
ters style. It uses an orderer parameter of type T => Ordered[T]. The
word Ordered in this type indicates exactly what the implicit parameter is
used for: it is for ordering elements of T. Because this orderer type is more
explicit, it becomes no trouble to add implicit conversions for this type in
the standard library. To contrast, imagine the chaos that would ensue if you
added an implicit of type (T, T) => Boolean in the standard library, and the
compiler started sprinkling it around in people’s code. You would end up
with code that compiles and runs, but that does fairly arbitrary tests against
pairs of items!
Thus the style rule: use at least one role-determining name within the
type of an implicit parameter.
21.6 View bounds
The previous example had an opportunity to use an implicit but did not. Note
that when you use implicit on a parameter, then not only will the compiler
try to supply that parameter with an implicit value, but the compiler will also
use that parameter as an available implicit in the body of the method! Thus,
both uses of orderer within the body of the method can be left out.
When the compiler examines the code in Listing 21.4, it will see that the
types do not match up. For example, x of type T does not have a > method,
and so x > maxRest does not work. The compiler will not immediately stop,
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 21.6 Chapter 21 · Implicit Conversions and Parameters 482
def maxList[T](elements: List[T])
(implicit orderer: T => Ordered[T]): T =
elements match {
case List() =>
throw new IllegalArgumentException("empty list!")
case List(x) => x
case x :: rest =>
val maxRest = maxList(rest) // (orderer) is implicit
if (x > maxRest) x // orderer(x) is implicit
else maxRest
}
Listing 21.4 · A function that uses an implicit parameter internally.
however. It will first look for implicit conversions to repair the code. In
this case, it will notice that orderer is available, so it can convert the code
to orderer(x) > maxRest. Likewise for the expression maxList(rest),
which can be converted to maxList(rest)(ordered). After these two in-
sertions of implicits, the method fully type checks.
Look closely at maxList. There is not a single mention of the ordered
parameter in the text of the method. All uses of ordered are implicit. Sur-
prisingly, this coding pattern is actually fairly common. The implicit param-
eter is used only for conversions, and so it can itself be used implicitly.
Now, because the parameter name is never used explicitly, the name
could have been anything. For example, maxList would behave identically
if you left its body alone but changed the parameter name:
def maxList[T](elements: List[T])
(implicit converter: T => Ordered[T]): T =
// same body...
For that matter, it could just as well be:
def maxList[T](elements: List[T])
(implicit iceCream: T => Ordered[T]): T =
// same body...
Because this pattern is common, Scala lets you leave out the name of this pa-
rameter and shorten the method header by using a view bound. Using a view
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 21.6 Chapter 21 · Implicit Conversions and Parameters 483
def maxList[T <% Ordered[T]](elements: List[T]): T =
elements match {
case List() =>
throw new IllegalArgumentException("empty list!")
case List(x) => x
case x :: rest =>
val maxRest = maxList(rest) // (orderer) is implicit
if (x > maxRest) x // orderer(x) is implicit
else maxRest
}
Listing 21.5 · A function with a view bound.
bound, you would write the signature of maxList as shown in Listing 21.5.
You can think of “T <% Ordered[T]” as saying, “I can use any T, so long
as T can be treated as an Ordered[T].” This is different from saying that T is
an Ordered[T], which is what an upper bound, “T <: Ordered[T]”, would
say. For example, even though class Int is not a subtype of Ordered[Int],
you could still pass a List[Int] to maxList so long as an implicit conver-
sion from Int to Ordered[Int] is available. Moreover, if type T happens
to already be an Ordered[T], you can still pass a List[T] to maxList. The
compiler will use an implicit identity function, declared in Predef:
implicit def identity[A](x: A): A = x
In this case, the conversion is a no-op; it simply returns the object it is given.
View bounds and upper bounds
The maxListUpBound function, of Listing 21.2, specifies that T is an
Ordered[T] with its upper bound, T <: Ordered[T]. By contrast, the
maxList function, of Listing 21.5, specifies that T can be treated as an
Ordered[T] with its view bound, T <% Ordered[T]. If you compare
the code of maxListUpBound with that of maxList, you’ll find that the
only non-cosmetic difference between the two is that the upper bound
symbol, <:, is changed to a view bound symbol, <%. But maxList of
Listing 21.5 can work with many more types.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 21.6 Chapter 21 · Implicit Conversions and Parameters 484
object Mocha extends Application {
class PreferredDrink(val preference: String)
implicit val pref = new PreferredDrink("mocha")
def enjoy(name: String)(implicit drink: PreferredDrink) {
print("Welcome, "+ name)
print(". Enjoy a ")
print(drink.preference)
println("!")
}
enjoy("reader")
}
Listing 21.6 · Sample code that uses an implicit parameter.
$ scalac -Xprint:typer mocha.scala
[[syntax trees at end of typer]]// Scala source: mocha.scala
package <empty> {
final object Mocha extends java.lang.Object with Application
with ScalaObject {
// ...
private[this] val pref: Mocha.PreferredDrink =
new Mocha.this.PreferredDrink("mocha");
implicit <stable> <accessor>
def pref: Mocha.PreferredDrink = Mocha.this.pref;
def enjoy(name: String)
(implicit drink: Mocha.PreferredDrink): Unit = {
scala.this.Predef.print("Welcome, ".+(name));
scala.this.Predef.print(". Enjoy a ");
scala.this.Predef.print(drink.preference);
scala.this.Predef.println("!")
};
Mocha.this.enjoy("reader")(Mocha.this.pref)
}
}
Listing 21.7 · Sample code after type checking and insertion of implicits.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 21.7 Chapter 21 · Implicit Conversions and Parameters 485
21.7 Debugging implicits
Implicits are an extremely powerful feature in Scala, but one which is some-
times difficult to get right and to debug. This section contains a few tips for
debugging implicits.
Sometimes you might wonder why the compiler did not find an implicit
conversion that you think should apply. In that case it helps to write the
conversion out explicitly. If that also gives an error message, you then know
why the compiler could not apply your implicit. For instance, assume that
you mistakenly took stringWrapper to be a conversion from Strings to
Lists, instead of RandomAccessSeqs. You would wonder why the following
does not work:
scala> val chars: List[Char] = "xyz"
<console>:12: error: type mismatch;
found : java.lang.String("xyz")
required: List[Char]
val chars: List[Char] = "xyz"
ˆ
In that case it helps to write the stringWrapper conversion explicitly, to
find out what went wrong:
scala> val chars: List[Char] = stringWrapper("xyz")
<console>:12: error: type mismatch;
found : java.lang.Object with RandomAccessSeq[Char]
required: List[Char]
val chars: List[Char] = stringWrapper("xyz")
ˆ
With this, you have found the cause of the error: stringWrapper has the
wrong return type. On the other hand, it’s also possible that inserting the
conversion explicitly will make the error go away. In that case you know that
one of the other rules (such as the Scope Rule) was preventing the implicit
from being applied.
When you are debugging a program, it can sometimes help to see what
implicit conversions the compiler is inserting. The -Xprint:typer option
to the compiler is useful for this. If you run scalac with this option, then
the compiler will show you what your code looks like after all implicit con-
versions have been added by the type checker. An example is shown in
Listing 21.6 and Listing 21.7. If you look at the last statement in each of
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 21.8 Chapter 21 · Implicit Conversions and Parameters 486
these listings, you’ll see that the second parameter list to enjoy, which was
left off in the code in Listing 21.6:
enjoy("reader")
was inserted by the compiler, as shown in Listing 21.7:
Mocha.this.enjoy("reader")(Mocha.this.pref)
If you are brave, try scala -Xprint:typer to get an interactive shell
that prints out the post-typing source code it uses internally. If you do so, be
prepared to see an enormous amount of boilerplate surrounding the meat of
your code.
21.8 Conclusion
Implicits are a powerful, code-condensing feature of Scala. This chapter
has shown you Scala’s rules about implicits, and it has shown you several
common programming situations where you can profit from using implicits.
As a word of warning, implicits can make code confusing if they are
used too frequently. Thus, before adding a new implicit conversion, first
ask whether you can achieve a similar effect through other means, such as
inheritance, mixin composition, or method overloading. If all of these fail,
however, and you feel like a lot of your code is still tedious and redundant,
then implicits might just be able to help you out.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Chapter 22
Implementing Lists
Lists have been ubiquitous in this book. Class List is probably the most
commonly used structured data type in Scala. Chapter 16 showed you how
to use lists. This chapter “opens up the covers” and explains a bit how lists
are implemented in Scala.
Knowing the internals of the List class is useful for several reasons. You
gain a better idea of the relative efficiency of list operations, which will help
you in writing fast and compact code using lists. You also learn a toolbox of
techniques that you can apply in the design of your own libraries. Finally,
the List class is a sophisticated application of Scala’s type system in general
and its genericity concepts in particular. So studying class List will deepen
your knowledge in these areas.
22.1 The List class in principle
Lists are not “built-in” as a language construct in Scala; they are defined by
an abstract class List in the scala package, which comes with two sub-
classes for :: and Nil. In the following we present a quick tour through
class List. This section presents a somewhat simplified account of the class,
compared to its real implementation in the Scala standard library, which is
covered in Section 22.3.
package scala
abstract class List[+T] {
List is an abstract class, so you cannot define elements by calling the empty
List constructor. For instance the expression “new List” would be ille-
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 22.1 Chapter 22 · Implementing Lists 488
scala
::[T]
«final case»
scala
Nil
«case object»
scala
List[+T]
«sealed abstract»
Figure 22.1 · Class hierarchy for Scala lists.
gal. The class has a type parameter T. The + in front of this type parameter
specifies that lists are covariant, as discussed in Chapter 19. Because of this
property, you can assign a value of type List[Int], say, to a variable of type
List[Any]:
scala> val xs = List(1, 2, 3)
xs: List[Int] = List(1, 2, 3)
scala> var ys: List[Any] = xs
ys: List[Any] = List(1, 2, 3)
All list operations can be defined in terms of three basic methods:
def isEmpty: Boolean
def head: T
def tail: List[T]
These three methods are all abstract in class List. They are defined in the
subobject Nil and the subclass ::. The hierarchy for List is shown in Fig-
ure 22.1.
The Nil object
The Nil object defines an empty list. Its definition is shown in Listing 22.1.
The Nil object inherits from type List[Nothing]. Because of covariance,
this means that Nil is compatible with every instance of the List type.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 22.1 Chapter 22 · Implementing Lists 489
case object Nil extends List[Nothing] {
override def isEmpty = true
def head: Nothing =
throw new NoSuchElementException("head of empty list")
def tail: List[Nothing] =
throw new NoSuchElementException("tail of empty list")
}
Listing 22.1 · The definition of the Nil singleton object.
The three abstract methods of class List are implemented in the Nil
object in a straightforward way: the isEmpty method returns true and the
head and tail methods both throw an exception. Note that throwing an
exception is not only reasonable, but practically the only possible thing to do
for head: Because Nil is a List of Nothing, the result type of head must
be Nothing. Since there is no value of this type, this means that head cannot
return a normal value. It has to return abnormally by throwing an exception.
1
The :: class
Class ::, pronounced “cons” for “construct,” represents non-empty lists. It’s
named that way in order to support pattern matching with the infix ::. You
have seen in Section 16.5 that every infix operation in a pattern is treated
as a constructor application of the infix operator to its arguments. So the
pattern x :: xs is treated as ::(x, xs) where :: is a case class. Here is the
definition of the :: class:
final case class ::[T](hd: T, tl: List[T]) extends List[T] {
def head = hd
def tail = tl
override def isEmpty: Boolean = false
}
The implementation of the :: class is straightforward. It takes two parame-
ters hd and tl, representing the head and the tail of the list to be constructed.
1
To be precise, the types would also permit for head to always go into an infinite loop
instead of throwing an exception, but this is clearly not what’s wanted.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 22.1 Chapter 22 · Implementing Lists 490
The definitions of the head and tail method simply return the correspond-
ing parameter. In fact, this pattern can be abbreviated by letting the parame-
ters directly implement the head and tail methods of the superclass List,
as in the following equivalent but shorter definition of the :: class:
final case class ::[T](head: T, tail: List[T])
extends List[T] {
override def isEmpty: Boolean = false
}
This works because every case class parameter is implicitly also a field of the
class (it’s like the parameter declaration was prefixed with val). Recall from
Section 20.3 that Scala allows you to implement an abstract parameterless
method such as head or tail with a field. So the code above directly uses
the parameters head and tail as implementations of the abstract methods
head and tail that were inherited from class List.
Some more methods
All other List methods can be written using the basic three. For instance:
def length: Int =
if (isEmpty) 0 else 1 + tail.length
or:
def drop(n: Int): List[T] =
if (isEmpty) Nil
else if (n <= 0) this
else tail.drop(n - 1)
or:
def map[U](f: T => U): List[U] =
if (isEmpty) Nil
else f(head) :: tail.map(f)
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index