Odersky M. Programming in Scala
Подождите немного. Документ загружается.
Section 15.8 Chapter 15 · Case Classes and Pattern Matching 321
package org.stairwaybook.expr
import layout.Element.elem
sealed abstract class Expr
case class Var(name: String) extends Expr
case class Number(num: Double) extends Expr
case class UnOp(operator: String, arg: Expr) extends Expr
case class BinOp(operator: String,
left: Expr, right: Expr) extends Expr
class ExprFormatter {
// Contains operators in groups of increasing precedence
private val opGroups =
Array(
Set("|", "||"),
Set("&", "&&"),
Set("ˆ"),
Set("==", "!="),
Set("<", "<=", ">", ">="),
Set("+", "-"),
Set("
*
", "%")
)
// A mapping from operators to their precedence
private val precedence = {
val assocs =
for {
i <- 0 until opGroups.length
op <- opGroups(i)
} yield op -> i
Map() ++ assocs
}
private val unaryPrecedence = opGroups.length
private val fractionPrecedence = -1
// continued in Listing 15.21...
Listing 15.20 · The top half of the expression formatter.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 15.8 Chapter 15 · Case Classes and Pattern Matching 322
// ...continued from Listing 15.20
private def format(e: Expr, enclPrec: Int): Element =
e match {
case Var(name) =>
elem(name)
case Number(num) =>
def stripDot(s: String) =
if (s endsWith ".0") s.substring(0, s.length - 2)
else s
elem(stripDot(num.toString))
case UnOp(op, arg) =>
elem(op) beside format(arg, unaryPrecedence)
case BinOp("/", left, right) =>
val top = format(left, fractionPrecedence)
val bot = format(right, fractionPrecedence)
val line = elem('-', top.width max bot.width, 1)
val frac = top above line above bot
if (enclPrec != fractionPrecedence) frac
else elem(" ") beside frac beside elem(" ")
case BinOp(op, left, right) =>
val opPrec = precedence(op)
val l = format(left, opPrec)
val r = format(right, opPrec + 1)
val oper = l beside elem(" "+ op +" ") beside r
if (enclPrec <= opPrec) oper
else elem("(") beside oper beside elem(")")
}
def format(e: Expr): Element = format(e, 0)
}
Listing 15.21 · The bottom half of the expression formatter.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 15.8 Chapter 15 · Case Classes and Pattern Matching 323
If the expression is a variable, the result is an element formed from the vari-
able’s name.
The second case is:
case Number(num) =>
def stripDot(s: String) =
if (s endsWith ".0") s.substring(0, s.length - 2)
else s
elem(stripDot(num.toString))
If the expression is a number, the result is an element formed from the num-
ber’s value. The stripDot function cleans up the display of a floating-point
number by stripping any ".0" suffix from a string.
The third case is:
case UnOp(op, arg) =>
elem(op) beside format(arg, unaryPrecedence)
If the expression is a unary operation UnOp(op, arg) the result is formed
from the operation op and the result of formatting the argument arg with the
highest-possible environment precedence.
3
This means that if arg is a binary
operation (but not a fraction) it will always be displayed in parentheses.
The fourth case is:
case BinOp("/", left, right) =>
val top = format(left, fractionPrecedence)
val bot = format(right, fractionPrecedence)
val line = elem('-', top.width max bot.width, 1)
val frac = top above line above bot
if (enclPrec != fractionPrecedence) frac
else elem(" ") beside frac beside elem(" ")
If the expression is a fraction, an intermediate result frac is formed by plac-
ing the formatted operands left and right on top of each other, separated
by an horizontal line element. The width of the horizontal line is the max-
imum of the widths of the formatted operands. This intermediate result is
3
The value of unaryPrecedence is the highest possible precedence, because it was ini-
tialized to one more than the precedence of the
*
and % operators.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 15.8 Chapter 15 · Case Classes and Pattern Matching 324
also the final result unless the fraction appears itself as an argument of an-
other fraction. In the latter case, a space is added on each side of frac.
To see the reason why, consider the expression “(a / b) / c”. Without the
widening correction, formatting this expression would give:
a
-
b
-
c
The problem with this layout is evident—it’s not clear where the top-level
fractional bar is. The expression above could mean either “(a / b) / c” or
“a / (b / c)”. To disambiguate, a space should be added on each side to the
layout of the nested fraction “a / b”. Then the layout becomes unambiguous:
a
-
b
---
c
The fifth and last case is:
case BinOp(op, left, right) =>
val opPrec = precedence(op)
val l = format(left, opPrec)
val r = format(right, opPrec + 1)
val oper = l beside elem(" "+ op +" ") beside r
if (enclPrec <= opPrec) oper
else elem("(") beside oper beside elem(")")
This case applies for all other binary operations. Since it comes after the
case starting with:
case BinOp("/", left, right) => ...
you know that the operator op in the pattern BinOp(op, left, right) can-
not be a division. To format such a binary operation, one needs to format
first its operands left and right. The precedence parameter for formatting
the left operand is the precedence opPrec of the operator op, while for the
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 15.8 Chapter 15 · Case Classes and Pattern Matching 325
right operand it is one more than that. This scheme ensures that parentheses
also reflect the correct associativity. For instance, the operation:
BinOp("-", Var("a"), BinOp("-", Var("b"), Var("c")))
would be correctly parenthesized as “a - (b - c)”. The intermediate result
oper is then formed by placing the formatted left and right operands side-
by-side, separated by the operator. If the precedence of the current operator
is smaller than the precedence of the enclosing operator, r is placed between
parentheses, otherwise it is returned as is.
This finishes the design of the private format function. The only re-
maining method is the public format method, which allows client program-
mers to format a top-level expression without passing a precedence argu-
ment. Listing 15.22 shows a demo program that exercises ExprFormatter:
import org.stairwaybook.expr._
object Express extends Application {
val f = new ExprFormatter
val e1 = BinOp("
*
", BinOp("/", Number(1), Number(2)),
BinOp("+", Var("x"), Number(1)))
val e2 = BinOp("+", BinOp("/", Var("x"), Number(2)),
BinOp("/", Number(1.5), Var("x")))
val e3 = BinOp("/", e1, e2)
def show(e: Expr) = println(f.format(e)+ "\n\n")
for (val e <- Array(e1, e2, e3)) show(e)
}
Listing 15.22 · An application that prints formatted expressions.
Note that, even though this program does not define a main method, it is
still a runnable application because it inherits from the Application trait.
As mentioned in Section 4.5, trait Application simply defines an empty
main method that gets inherited by the Express object. The actual work in
the Express object gets done as part of the object’s initialization, before the
main method is run. That’s why you can apply this trick only if your program
does not take any command-line arguments. Once there are arguments, you
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 15.9 Chapter 15 · Case Classes and Pattern Matching 326
need to write the main method explicitly. You can run the Express program
with the command:
scala Express
This will give the following output:
1
-
*
(x + 1)
2
x 1.5
- + ---
2 x
1
-
*
(x + 1)
2
-----------
x 1.5
- + ---
2 x
15.9 Conclusion
In this chapter, you learned about Scala’s case classes and pattern matching
in detail. Using them, you can take advantage of several concise idioms not
normally available in object-oriented languages. Scala’s pattern matching
goes further than this chapter describes, however. If you want to use pattern
matching on one of your classes, but you do not want to open access to your
classes the way case classes do, then you can use the extractors described in
Chapter 24. In the next chapter, however, we’ll turn our attention to lists.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Chapter 16
Working with Lists
Lists are probably the most commonly used data structure in Scala programs.
This chapter explains lists in detail. It presents many common operations that
can be performed on lists. It also teaches some important design principles
for programs working on lists.
16.1 List literals
You saw lists already in the preceding chapters, so you know that a list con-
taining the elements 'a', 'b', and 'c' is written List('a', 'b', 'c').
Here are some other examples:
val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 =
List(
List(1, 0, 0),
List(0, 1, 0),
List(0, 0, 1)
)
val empty = List()
Lists are quite similar to arrays, but there are two important differences.
First, lists are immutable. That is, elements of a list cannot be changed
by assignment. Second, lists have a recursive structure (i.e., a linked list),
1
whereas arrays are flat.
1
For a graphical depiction of the structure of a List, see Figure 22.2 on page 492.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.2 Chapter 16 · Working with Lists 328
16.2 The List type
Like arrays, lists are homogeneous: the elements of a list all have the same
type. The type of a list that has elements of type T is written List[T]. For
instance, here are the same four lists with explicit types added:
val fruit: List[String] = List("apples", "oranges", "pears")
val nums: List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] =
List(
List(1, 0, 0),
List(0, 1, 0),
List(0, 0, 1)
)
val empty: List[Nothing] = List()
The list type in Scala is covariant. This means that for each pair of
types S and T, if S is a subtype of T, then List[S] is a subtype of List[T].
For instance, List[String] is a subtype of List[Object]. This is natural
because every list of strings can also be seen as a list of objects.
2
Note that the empty list has type List[Nothing]. You saw in Sec-
tion 11.3 that Nothing is the bottom type in Scala’s class hierarchy. It is
a subtype of every other Scala type. Because lists are covariant, it follows
that List[Nothing] is a subtype of List[T], for any type T. So the empty
list object, which has type List[Nothing], can also be seen as an object
of every other list type of the form List[T]. That’s why it is permissible to
write code like:
// List() is also of type List[String]!
val xs: List[String] = List()
16.3 Constructing lists
All lists are built from two fundamental building blocks, Nil and :: (pro-
nounced “cons”). Nil represents the empty list. The infix operator, ::,
expresses list extension at the front. That is, x :: xs represents a list whose
2
Chapter 19 gives more details on covariance and other kinds of variance.
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.4 Chapter 16 · Working with Lists 329
first element is x, followed by (the elements of) list xs. Hence, the previous
list values could also have been defined as follows:
val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
val diag3 = (1 :: (0 :: (0 :: Nil))) ::
(0 :: (1 :: (0 :: Nil))) ::
(0 :: (0 :: (1 :: Nil))) :: Nil
val empty = Nil
In fact the previous definitions of fruit, nums, diag3, and empty in terms of
List(...) are just wrappers that expand to these definitions. For instance,
List(1, 2, 3) creates the list 1 :: (2 :: (3 :: Nil)).
Because it ends in a colon, the :: operation associates to the right:
A :: B :: C is interpreted as A :: (B :: C). Therefore, you can drop the
parentheses in the previous definitions. For instance:
val nums = 1 :: 2 :: 3 :: 4 :: Nil
is equivalent to the previous definition of nums.
16.4 Basic operations on lists
All operations on lists can be expressed in terms of the following three:
head returns the first element of a list
tail returns a list consisting of all elements except the first
isEmpty returns true if the list is empty
These operations are defined as methods of class List. Some examples are
shown in Table 16.1.
The head and tail methods are defined only for non-empty lists. When
selected from an empty list, they throw an exception. For instance:
scala> Nil.head
java.util.NoSuchElementException: head of empty list
As an example of how lists can be processed, consider sorting the elements of
a list of numbers into ascending order. One simple way to do so is insertion
sort, which works as follows: To sort a non-empty list x :: xs, sort the
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index
Section 16.5 Chapter 16 · Working with Lists 330
Table 16.1 · Basic list operations
What it is What it does
empty.isEmpty returns true
fruit.isEmpty returns false
fruit.head returns "apples"
fruit.tail.head returns "oranges"
diag3.head returns List(1, 0, 0)
remainder xs and insert the first element x at the right position in the result.
Sorting an empty list yields the empty list. Expressed as Scala code, the
insertion sort algorithm looks like:
def isort(xs: List[Int]): List[Int] =
if (xs.isEmpty) Nil
else insert(xs.head, isort(xs.tail))
def insert(x: Int, xs: List[Int]): List[Int] =
if (xs.isEmpty || x <= xs.head) x :: xs
else xs.head :: insert(x, xs.tail)
16.5 List patterns
Lists can also be taken apart using pattern matching. List patterns correspond
one-by-one to list expressions. You can either match on all elements of a list
using a pattern of the form List(...), or you take lists apart bit by bit using
patterns composed from the :: operator and the Nil constant.
Here’s an example of the first kind of pattern:
scala> val List(a, b, c) = fruit
a: String = apples
b: String = oranges
c: String = pears
The pattern List(a, b, c) matches lists of length 3, and binds the three ele-
ments to the pattern variables a, b, andc. If you don’t know the number of
list elements beforehand, it’s better to match with :: instead. For instance,
the pattern a :: b :: rest matches lists of length 2 or greater:
Cover · Overview · Contents · Discuss · Suggest · Glossary · Index