*** empty log message ***

1 files changed, 1695 insertions, 583 deletions

diff --git a/doc/reference/ScalaByExample.tex b/doc/reference/ScalaByExample.tex
index a5eaf71c41..2e69f6e6f2 100644
--- a/doc/reference/ScalaByExample.tex
+++ b/doc/reference/ScalaByExample.tex
@@ -18,7 +18,7 @@
     }
 \fi
 
-\newcommand{\exercise}{\paragraph{Exercise:}}
+\newcommand{\exercise}{\paragraph{Exercise}}
 \newcommand{\rewriteby}[1]{\mbox{\tab\tab\rm(#1)}}
 
 \renewcommand{\doctitle}{Scala By Example\\[33mm]\ }
@@ -273,20 +273,17 @@ messages matching some pattern.
 
 \begin{lstlisting}[style=floating,label=fig:simple-auction-msgs,caption=Implementation of an Auction Service]
 trait AuctionMessage;
-
-/** make a bid */
 case class Offer(bid: int, client: Actor)  extends AuctionMessage;
-
-/** inquire status */
-case class Inquire(client: Actor) extends AuctionMessage;       
+case class Inquire(client: Actor)          extends AuctionMessage;       
 
 trait AuctionReply;
-case class  Status(asked: int, expiration: Date) extends AuctionReply;
-case object BestOffer extends AuctionReply;
-case class  BeatenOffer(maxBid: int) extends AuctionReply;
-case class  AuctionConcluded(seller: Actor, client: Actor) extends AuctionReply;
-case object AuctionFailed extends AuctionReply;
-case object AuctionOver extends AuctionReply;               
+case class  Status(asked: int, expire: Date) extends AuctionReply;
+case object BestOffer                        extends AuctionReply;
+case class  BeatenOffer(maxBid: int)         extends AuctionReply;
+case class  AuctionConcluded(seller: Actor, client: Actor) 
+                                             extends AuctionReply;
+case object AuctionFailed                    extends AuctionReply;
+case object AuctionOver                      extends AuctionReply;
 \end{lstlisting}
 
 For every traded item there is an auctioneer process that publishes
@@ -306,35 +303,35 @@ are defined in Figure~\ref{fig:simple-auction-msgs}.
 class Auction(seller: Actor, minBid: int, closing: Date) extends Actor {
   val timeToShutdown = 36000000; // msec
   val bidIncrement = 10;
-  def execute {
+  def run() = {
     var maxBid = minBid - bidIncrement;
     var maxBidder: Actor = _;
     var running = true;
     while (running) {
       receiveWithin ((closing.getTime() - new Date().getTime())) {
-	  case Offer(bid, client) =>
-	    if (bid >= maxBid + bidIncrement) { 
-          if (maxBid >= minBid) maxBidder send BeatenOffer(bid);
-          maxBid = bid; maxBidder = client; client send BestOffer;
-        } else {
-          client send BeatenOffer(maxBid);
-        }
-	  case Inquire(client) =>
-	    client send Status(maxBid, closing);
-	  case TIMEOUT =>
-	    if (maxBid >= minBid) {
-	      val reply = AuctionConcluded(seller, maxBidder);
-	      maxBidder send reply; seller send reply;
-	    } else {
-	      seller send AuctionFailed;
-        }
-        receiveWithin(timeToShutdown) {
-          case Offer(_, client) => client send AuctionOver
-          case TIMEOUT => running = false;
-        }
+        case Offer(bid, client) =>
+          if (bid >= maxBid + bidIncrement) { 
+            if (maxBid >= minBid) maxBidder send BeatenOffer(bid);
+            maxBid = bid; maxBidder = client; client send BestOffer;
+          } else {
+            client send BeatenOffer(maxBid);
+          }
+        case Inquire(client) =>
+          client send Status(maxBid, closing);
+        case TIMEOUT =>
+          if (maxBid >= minBid) {
+            val reply = AuctionConcluded(seller, maxBidder);
+            maxBidder send reply; seller send reply;
+          } else {
+            seller send AuctionFailed;
+          }
+          receiveWithin(timeToShutdown) {
+            case Offer(_, client) => client send AuctionOver
+            case TIMEOUT => running = false;
+          }
       }
     }
-  }
+  } 
 }
 \end{lstlisting}
 
@@ -396,16 +393,16 @@ thread model of the host language (e.g. Java, or .NET).
 The implementation of all features of class \code{Actor} used here is
 given in Section~\ref{sec:actors}.
 
-The advantages of this approach are relative simplicity of the core
-language and flexibility for library designers. Because the core
-language need not specify details of high-level process communication,
-it can be kept simpler and more general. Because the particular model
-of messages in a mailbox is a library module, it can be freely
-modified if a different model is needed in some applications.  The
-approach requires however that the core language is expressive enough
-to provide the necessary language abstractions in a convenient
-way. Scala has been designed with this in mind; one of its major
-design goals was that it should be flexible enough to act as a
+The advantages of the library-based approach are relative simplicity
+of the core language and flexibility for library designers. Because
+the core language need not specify details of high-level process
+communication, it can be kept simpler and more general. Because the
+particular model of messages in a mailbox is a library module, it can
+be freely modified if a different model is needed in some
+applications.  The approach requires however that the core language is
+expressive enough to provide the necessary language abstractions in a
+convenient way. Scala has been designed with this in mind; one of its
+major design goals was that it should be flexible enough to act as a
 convenient host language for domain specific languages implemented by
 library modules. For instance, the actor communication constructs
 presented above can be regarded as one such domain specific language,
@@ -617,7 +614,7 @@ Scala's boolean expressions are similar to Java's; they are formed
 from the constants
 \code{true} and
 \code{false}, comparison operators, boolean negation \code{!} and the
-boolean operators \code{&&} and \code{||}.
+boolean operators $\,$\code{&&}$\,$ and $\,$\code{||}.
 
 \section{\label{sec:sqrt}Example: Square Roots by Newton's Method}
 
@@ -762,9 +759,6 @@ def gcd(a: int, b: int): int = if (b == 0) a else gcd(b, a % b)
 Using our substitution model of function evaluation, 
 \code{gcd(14, 21)} evaluates as follows:
 
-$\,\,\,$   sumOfSquares(3, 2+2)
-$\rightarrow$  square(3) + square(2+2)
-
 \begin{lstlisting}
 $\,\,$      gcd(14, 21)  
 $\rightarrow\!$     if (21 == 0) 14 else gcd(21, 14 % 21)
@@ -931,7 +925,7 @@ def sumCubes(a: int, b: int): double = sum(x: int => x * x * x, a, b);
 def sumReciprocals(a: int, b: int): double = sum(x: int => 1.0/x, a, b);
 \end{lstlisting}
 Often, the Scala compiler can deduce the parameter type(s) from the
-context of the anonymous function. In this case, they can be omitted.
+context of the anonymous function in which case they can be omitted.
 For instance, in the case of \code{sumInts}, \code{sumCubes} and
 \code{sumReciprocals}, one knows from the type of
 \code{sum} that the first parameter must be a function of type
@@ -998,12 +992,12 @@ val sumReciprocals = sum(x => 1.0/x);
 \end{lstlisting}
 These functions can be applied like other functions. For instance,
 \begin{lstlisting}
-? sumCubes(1, 10) + sumReciprocals (10, 20)
+? sumCubes(1, 10) + sumReciprocals(10, 20)
 3025.7687714031754
 \end{lstlisting}
 How are function-returning functions applied? As an example, in the expression
 \begin{lstlisting}
-sum (x => x * x * x) (1, 10) ,
+sum(x => x * x * x)(1, 10) ,
 \end{lstlisting}
 the function \code{sum} is applied to the cubing function 
 \code{(x => x * x * x)}. The resulting function is then 
@@ -1339,7 +1333,7 @@ Parameter    =  ['def'] ident ':' Type
 Definitions can be:
 \begin{itemize}
 \item
-function definitions such as \code{def square(x: int) = x * x}, 
+function definitions such as \code{def square(x: int): int = x * x}, 
 \item
 value definitions such as \code{val y = square(2)}.
 \end{itemize}
@@ -1402,17 +1396,20 @@ while (i <= 10) {
   x = x + new Rational(1,i);
   i = i + 1;
 }
-System.out.println(x.numer + "/" + x.denom);
+System.out.println("" + x.numer + "/" + x.denom);
 \end{lstlisting}
-The \code{+} operation converts both its operands to strings and returns the
-concatenation of the result strings. It thus corresponds to \code{+} in Java. 
+The \code{+} takes as left operand a string and as right operand a
+value of arbitrary type. It returns the result of converting its right
+operand to a string and appending it to its left operand. 
   
 \paragraph{Inheritance and Overriding}
-Every class in Scala has a superclass which it extends.
-Excepted is only the root class \code{Object}, which does not have a
-superclass, and which is indirectly extended by every other class.
-If a class does not mention a superclass in its definition, the root
-class \code{Object} is implicitly assumed. For instance, class
+Every class in Scala has a superclass which it extends.  
+\comment{Excepted is
+only the root class \code{Object}, which does not have a superclass,
+and which is indirectly extended by every other class.  }
+If a class
+does not mention a superclass in its definition, the root class
+\code{scala.Object} is implicitly assumed. For instance, class
 \code{Rational} could equivalently be defined as
 \begin{lstlisting}
 class Rational(n: int, d: int) extends Object {
@@ -1437,7 +1434,7 @@ numbers:
 \begin{lstlisting}
 class Rational(n: int, d: int) extends Object {
   ... // as before
-  override def toString() = numer + "/" + denom;
+  override def toString() = "" + numer + "/" + denom;
 }
 \end{lstlisting}
 Note that, unlike in Java, redefining definitions need to be preceded
@@ -1460,7 +1457,7 @@ var x: Object = new Rational(1,2);
 %val r = new Rational(1,2);
 %System.out.println(r.toString());	// prints``1/2''
 %\end{lstlisting}
-Also unlike in Java, methods in Scala do not necessarily take a
+Unlike in Java, methods in Scala do not necessarily take a
 parameter list. An example is the \code{square} method below. This
 method is invoked by simply mentioning its name. 
 \begin{lstlisting}
@@ -1530,27 +1527,27 @@ consisting of an integer and two subtrees. Here are their
 implementations.
 
 \begin{lstlisting}
-class Empty extends IntSet {
+class EmptySet extends IntSet {
   def contains(x: int): boolean = false;
-  def incl(x: int): IntSet = new NonEmpty(x, new Empty, new Empty);
+  def incl(x: int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet);
 }
 \end{lstlisting}
 
 \begin{lstlisting}
-class NonEmpty(elem:int, left:IntSet, right:IntSet) extends IntSet {
+class NonEmptySet(elem:int, left:IntSet, right:IntSet) extends IntSet {
   def contains(x: int): boolean = 
     if (x < elem) left contains x
     else if (x > elem) right contains x
     else true;
   def incl(x: int): IntSet = 
-    if (x < elem) new NonEmpty(elem, left incl x, right)
-    else if (x > elem) new NonEmpty(elem, left, right incl x)
+    if (x < elem) new NonEmptySet(elem, left incl x, right)
+    else if (x > elem) new NonEmptySet(elem, left, right incl x)
     else this;
 }
 \end{lstlisting}
-Both \code{Empty} and \code{NonEmpty} extend class
-\code{IntSet}.  This implies that types \code{Empty} and
-\code{NonEmpty} conform to type \code{IntSet} -- a value of type \code{Empty} or \code{NonEmpty} may be used wherever a value of type \code{IntSet} is required.
+Both \code{EmptySet} and \code{NonEmptySet} extend class
+\code{IntSet}.  This implies that types \code{EmptySet} and
+\code{NonEmptySet} conform to type \code{IntSet} -- a value of type \code{EmptySet} or \code{NonEmptySet} may be used wherever a value of type \code{IntSet} is required.
 
 \exercise Write methods \code{union} and \code{intersection} to form
 the union and intersection between two sets.
@@ -1574,31 +1571,31 @@ depends on the run-time type of the object which contains the method.
 For example, consider the expression \code{s contains 7} where
 \code{s} is a value of declared type \code{s: IntSet}. Which code for
 \code{contains} is executed depends on the type of value of \code{s} at run-time.
-If it is an \code{Empty} value, it is the implementation of \code{contains} in class \code{Empty} that is executed, and analogously for \code{NonEmpty} values. 
+If it is an \code{EmptySet} value, it is the implementation of \code{contains} in class \code{EmptySet} that is executed, and analogously for \code{NonEmptySet} values. 
 This behavior is a direct consequence of our substitution model of evaluation.
 For instance,
 \begin{lstlisting}
-    (new Empty).contains(7) 
+    (new EmptySet).contains(7) 
 
-->  $\rewriteby{by replacing {\sl contains} by its body in class {\sl Empty}}$
+->  $\rewriteby{by replacing {\sl contains} by its body in class {\sl EmptySet}}$
 
     false
 \end{lstlisting}
 Or,
 \begin{lstlisting}
-    new NonEmpty(7, new Empty, new Empty).contains(1)
+    new NonEmptySet(7, new EmptySet, new EmptySet).contains(1)
 
-->  $\rewriteby{by replacing {\sl contains} by its body in class {\sl NonEmpty}}$
+->  $\rewriteby{by replacing {\sl contains} by its body in class {\sl NonEmptySet}}$
 
-    if (1 < 7) new Empty contains 1
-    else if (1 > 7) new Empty contains 1
+    if (1 < 7) new EmptySet contains 1
+    else if (1 > 7) new EmptySet contains 1
     else true
 
 ->  $\rewriteby{by rewriting the conditional}$
 
-    new Empty contains 1
+    new EmptySet contains 1
 
-->  $\rewriteby{by replacing {\sl contains} by its body in class {\sl Empty}}$
+->  $\rewriteby{by replacing {\sl contains} by its body in class {\sl EmptySet}}$
 
     false .
 \end{lstlisting}
@@ -1613,25 +1610,24 @@ Section~\ref{sec:funs-are-objects}).
 \paragraph{Objects}
 
 In the previous implementation of integer sets, empty sets were
-expressed with \code{new Empty}; so a new object was created every time
+expressed with \code{new EmptySet}; so a new object was created every time
 an empty set value was required. We could have avoided unnecessary
 object creations by defining a value \code{empty} once and then using
-this value instead of every occurrence of \code{new Empty}. E.g.
+this value instead of every occurrence of \code{new EmptySet}. E.g.
 \begin{lstlisting}
-val empty = new Empty;
+val EmptySetVal = new EmptySet;
 \end{lstlisting}
 One problem with this approach is that a value definition such as the
 one above is not a legal top-level definition in Scala; it has to be
 part of another class or object. Also, the definition of class
-\code{Empty} now seems a bit of an overkill -- why define a class of objects, 
+\code{EmptySet} now seems a bit of an overkill -- why define a class of objects, 
 if we are only interested in a single object of this class? A more
 direct approach is to use an {\em object definition}. Here is
 a more streamlined alternative definition of the empty set:
 \begin{lstlisting}
-object empty extends IntSet {
+object EmptySet extends IntSet {
   def contains(x: int): boolean = false;
-
-  def incl(x: int): IntSet = new NonEmpty(x, empty, empty);
+  def incl(x: int): IntSet = new NonEmptySet(x, empty, empty);
 }
 \end{lstlisting}
 The syntax of an object definition follows the syntax of a class
@@ -1652,6 +1648,8 @@ strategy is called {\em lazy evaluation}.
 
 \paragraph{Standard Classes}
 
+\todo{include picture}
+
 Scala is a pure object-oriented language. This means that every value
 in Scala can be regarded as an object.  In fact, even primitive types
 such as \code{int} or \code{boolean} are not treated specially. They
@@ -1691,7 +1689,7 @@ Booleans can be defined using only classes and objects, without
 reference to a built-in type of booleans or numbers. A possible
 implementation of class \code{Boolean} is given below.  This is not
 the actual implementation in the standard Scala library. For
-efficiency reasons the standard implementation is built from built-in
+efficiency reasons the standard implementation uses built-in
 booleans.
 \begin{lstlisting}
 package scala;
@@ -1720,7 +1718,11 @@ Here is a partial specification of class \code{Int}.
 
 \begin{lstlisting}
 package scala;
-trait Int extends Long { 
+trait Int extends AnyVal { 
+  def coerce: Long;
+  def coerce: Float;
+  def coerce: Double;
+
   def + (that: Double): Double;
   def + (that: Float): Float;
   def + (that: Long): Long;
@@ -1762,17 +1764,17 @@ The implementation of the \code{Zero} object is straightforward:
 \begin{lstlisting}
 object Zero extends Nat {
   def isZero: Boolean = true;
-  def predecessor: Nat = error("negative number");
+  def predecessor: Nat = throw new Error("negative number");
   def successor: Nat = new Succ(Zero);
   def + (that: Nat): Nat = that;
-  def - (that: Nat): Nat = if (that.isZero) Zero else error("negative number")
+  def - (that: Nat): Nat = if (that.isZero) Zero 
+                           else throw new Error("negative number")
 }
 \end{lstlisting}
 
 The implementation of the predecessor and subtraction functions on
-\code{Zero} contains a call to the predefined \code{error}
-function. This function aborts the program with the given error
-message.
+\code{Zero} throws an \code{Error} exception, which aborts the program
+with the given error message.
 
 Here is the implementation of the successor class:
 \begin{lstlisting}
@@ -1780,8 +1782,8 @@ class Succ(x: Nat) extends Nat  {
   def isZero: Boolean = false;
   def predecessor: Nat = x;
   def successor: Nat = new Succ(this);
-  def + (that: Nat): Nat = x.+(that.successor);
-  def - (that: Nat): Nat = x.-(that.predecessor)
+  def + (that: Nat): Nat = x + that.successor;
+  def - (that: Nat): Nat = x - that.predecessor;
 }
 \end{lstlisting}
 Note the implementation of method \code{successor}. To create the
@@ -1792,7 +1794,7 @@ referenced by the reserved name \code{this}.
 The implementations of \code{+} and \code{-} each contain a recursive
 call with the constructor argument as receiver. The recursion will
 terminate once the receiver is the \code{Zero} object (which is
-guaranteed to happen eventually from the way numbers are formed).
+guaranteed to happen eventually because of the way numbers are formed).
 
 \exercise Write an implementation \code{Integer} of integer numbers
 The implementation should support all operations of class \code{Nat}
@@ -1812,7 +1814,7 @@ Or one can generalize the given implementation of \code{Nat} to
 
 
 
-\paragraph{Language Elements Introduced In This Chapter}
+\subsection*{Language Elements Introduced In This Chapter}
 
 \textbf{Types:}
 \begin{lstlisting}
@@ -1873,7 +1875,7 @@ form it is (either \code{Sum} or \code{Number}) and also needs to
 access the components of the expression.  The following
 implementation provides all necessary methods.
 \begin{lstlisting}
-abstract class Expr {
+trait Expr {
   def isNumber: boolean;
   def isSum: boolean;
   def numValue: int;
@@ -1884,13 +1886,13 @@ class Number(n: int) extends Expr {
   def isNumber: boolean = true;
   def isSum: boolean = false;
   def numValue: int = n;
-  def leftOp: Expr = error("Number.leftOp");
-  def rightOp: Expr = error("Number.rightOp");
+  def leftOp: Expr = throw new Error("Number.leftOp");
+  def rightOp: Expr = throw new Error("Number.rightOp");
 }
 class Sum(e1: Expr, e2: Expr) extends Expr {
   def isNumber: boolean = false;
   def isSum: boolean = true;
-  def numValue: int = error("Sum.numValue");
+  def numValue: int = throw new Error("Sum.numValue");
   def leftOp: Expr = e1;
   def rightOp: Expr = e2;
 }
@@ -1900,7 +1902,7 @@ With these classification and access methods, writing an evaluator function is s
 def eval(e: Expr): int = {
   if (e.isNumber) e.numValue
   else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
-  else error("unrecognized expression kind")
+  else throw new Error("unrecognized expression kind")
 }
 \end{lstlisting}
 However, defining all these methods in classes \code{Sum} and
@@ -1922,7 +1924,7 @@ outside the expression class hierarchy, as we have done
 before. Because \code{eval} is now a member of all expression nodes,
 all classification and access methods become superfluous, and the implementation is simplified considerably:
 \begin{lstlisting}
-abstract class Expr {
+trait Expr {
   def eval: int;
 }
 class Number(n: int) extends Expr {
@@ -1958,13 +1960,13 @@ def print(e: Expr): unit =
     System.out.print("+");
     print(e.rightOp);
     System.out.print(")");
-  } else error("unrecognized expression kind");
+  } else throw new Error("unrecognized expression kind");
 \end{lstlisting}
 However, if we had opted for an object-oriented decomposition of
 expressions, we would need to add a new \code{print} method
 to each class:
 \begin{lstlisting}
-abstract class Expr {
+trait Expr {
   def eval: int;
   def print: unit;
 }
@@ -2003,16 +2005,18 @@ of an abstract base class was used and, second, what were the
 constructor arguments. Since this situation is quite common, Scala has
 a way to automate it with case classes. 
 
-\paragraph{Case Classes}
-A {\em case class} is defined like a normal class, except that the definition
-is prefixed with the modifier \code{case}.  For instance, the definitions
+\paragraph{Case Classes and Case Objects}
+{\em Case classes} and {\em case objects} are defined like a normal
+classes or objects, except that the definition is prefixed with the modifier
+\code{case}.  For instance, the definitions
 \begin{lstlisting}
-abstract class Expr;
+trait Expr;
 case class Number(n: int) extends Expr;
 case class Sum(e1: Expr, e2: Expr) extends Expr;
 \end{lstlisting}
 introduce \code{Number} and \code{Sum} as case classes.
-The \code{case} modifier in front of a class definition has the following effects.
+The \code{case} modifier in front of a class or object 
+definition has the following effects.
 \begin{enumerate}
 \item Case classes implicitly come with a constructor function, with the same name as the class. In our example, the two functions
 \begin{lstlisting}
@@ -2023,7 +2027,8 @@ would be added. Hence, one can now construct expression trees a bit more concise
 \begin{lstlisting}
 Sum(Sum(Number(1), Number(2)), Number(3))
 \end{lstlisting} 
-\item Case classes implicity come with implementations of methods
+\item Case classes and case objects 
+implicity come with implementations of methods
 \code{toString}, \code{equals} and \code{hashCode}, which override the
 methods with the same name in class \code{Object}. The implementation
 of these methods takes in each case the structure of a member of a
@@ -2107,15 +2112,14 @@ In general, patterns are built from
       are again patterns,
 \item pattern variables, e.g. \code{n}, \code{e1}, \code{e2},
 \item the ``wildcard'' pattern \code{_},
-\item constants, e.g. \code{1}, \code{true}, "abc", \code{MAXINT}.
+\item literals, e.g. \code{1}, \code{true}, "abc", 
+\item constant identifiers, e.g. \code{MAXINT}, \code{EmptySet}.
 \end{itemize}
 Pattern variables always start with a lower-case letter, so that they
 can be distinguished from constant identifiers, which start with an
-upper case letter. The only exceptions to that rule are the reserved
-words \code{null}, \code{true}, \code{false}, which are treated as constants.
-Each variable name may occur only once in a pattern. For instance,
-\code{Sum(x, x)} would be illegal as a pattern, since \code{x} occurs
-twice in it.
+upper case letter.  Each variable name may occur only once in a
+pattern. For instance, \code{Sum(x, x)} would be illegal as a pattern,
+since the pattern variable \code{x} occurs twice in it.
 
 \paragraph{Meaning of Pattern Matching}
 A pattern matching expression 
@@ -2180,7 +2184,7 @@ pattern matching function in that class hierarchy itself. For
 instance, we could have defined
 \code{eval} is a method of the base class \code{Expr}, and still have used pattern matching in its implementation:
 \begin{lstlisting}
-abstract class Expr { 
+trait Expr { 
   def eval: int = this match { 
     case Number(n) => n
     case Sum(e1, e2) => e1.eval + e2.eval 
@@ -2188,13 +2192,13 @@ abstract class Expr {
 }
 \end{lstlisting}
 
-\exercise
-Consider the following three classes representing trees of integers. 
-These classes can be seen as an alternative representation of \code{IntSet}:
+\exercise Consider the following definitions representing trees
+of integers.  These definitions can be seen as an alternative
+representation of \code{IntSet}:
 \begin{lstlisting}
 trait IntTree;
-case class Empty extends IntTree;
-case class Node(elem: int, left: IntTree, right: IntTree) extends IntTree;
+case object EmptyTree extends IntTree;
+case class  Node(elem: int, left: IntTree, right: IntTree) extends IntTree;
 \end{lstlisting}
 Complete the following implementations of function \code{contains} and \code{insert} for 
 \code{IntTree}'s.
@@ -2207,73 +2211,535 @@ def insert(t: IntTree, v: int): IntTree = t match { ...
 }
 \end{lstlisting}
 
-\subsection*{Tuples}
+\chapter{Generic Types and Methods}
+
+Classes in Scala can have type parameters. We demonstrate the use of
+type parameters with functional stacks as an example. Say, we want to
+write a data type of stacks of integers, with methods \code{push},
+\code{top}, \code{pop}, and \code{isEmpty}. This is achieved by the
+following class hierarchy:
+\begin{lstlisting}
+trait IntStack {
+  def push(x: int): IntStack = new IntNonEmptyStack(x, this);
+  def isEmpty: boolean
+  def top: int;
+  def pop: IntStack;
+}
+class IntEmptyStack extends IntStack {
+  def isEmpty = true;
+  def top = throw new Error("EmptyStack.top");
+  def pop = throw new Error("EmptyStack.pop");
+}
+class IntNonEmptyStack(elem: int, rest: IntStack) {
+  def isEmpty = false;
+  def top = elem;
+  def pop = rest;
+}
+\end{lstlisting}
+Of course, it would also make sense to define an abstraction for a
+stack of Strings. To do that, one could take the existing abstraction
+for \code{IntStack}, rename it to \code{StringStack} and at the same
+time rename all occurrences of type \code{int} to \code{String}.
+
+A better way, which does not entail code duplication, is to
+parameterize the stack definitions with the element type.
+Parameterization lets us generalize from a specific instance of a
+problem to a more general one. So far, we have used parameterization
+only for values, but it is available also for types. To arrive at a
+{\em generic} version of \code{Stack}, we equip it with a type
+parameter.
+\begin{lstlisting}
+trait Stack[a] {
+  def push(x: a): Stack[a] = new NonEmptyStack[a](x, this);
+  def isEmpty: boolean
+  def top: a;
+  def pop: Stack[a];
+}
+class EmptyStack[a] extends Stack[a] {
+  def isEmpty = true;
+  def top = throw new Error("EmptyStack.top");
+  def pop = throw new Error("EmptyStack.pop");
+}
+class NonEmptyStack[a](elem: a, rest: Stack[a]) extends Stack[a] {
+  def isEmpty = false;
+  def top = elem;
+  def pop = rest;
+}
+\end{lstlisting}
+In the definitions above, `\code{a}' is a {\em type parameter} of
+class \code{Stack} and its subclasses.  Type parameters are arbitrary
+names; they are enclosed in brackets instead of parentheses, so that
+they can be easily distinguished from value parameters.  Here is an
+example how the generic classes are used:
+\begin{lstlisting}
+val x = new EmptyStack[int];
+val y = x.push(1).push(2);
+System.out.println(y.pop.top);
+\end{lstlisting}
+The first line creates a new empty stack of \code{int}'s. Note the
+actual type argument \code{[int]} which replaces the formal type
+parameter \code{a}.
+
+It is also possible to parameterize methods with types. As an example,
+here is a generic method which determines whether one stack is a
+prefix of another.
+\begin{lstlisting}
+def isPrefix[a](p: Stack[a], s: Stack[a]): boolean = {
+  p.isEmpty ||
+  p.top == s.top && isPrefix[a](p.pop, s.pop);
+}
+\end{lstlisting}  
+parameters are called {\em polymorphic}.  Generic methods are also
+called {\em polymorphic}.  The term comes from the Greek, where it
+means ``having many forms''.  To apply a polymorphic method such as
+\code{isPrefix}, we pass type parameters as well as value parameters
+to it. For instance,
+\begin{lstlisting}
+val s1 = new EmptyStack[String].push("abc");
+val s2 = new EmptyStack[String].push("abx").push(s.pop)
+System.out.println(isPrefix[String](s1, s2));
+\end{lstlisting}
+
+\paragraph{Local Type Inference}
+Passing type parameters such as \code{[int]} or \code{[String]} all
+the time can become tedious in applications where generic functions
+are used a lot. Quite often, the information in a type parameter is
+redundant, because the correct parameter type can also be determined
+by inspecting the function's value parameters or expected result type.
+Taking the expression \code{isPrefix[String](s1, s2)} as an
+example, we know that its value parameters are both of type
+\code{Stack[String]}, so we can deduce that the type parameter must
+be \code{String}. Scala has a fairly powerful type inferencer which
+allows one to omit type parameters to polymorphic functions and
+constructors in situations like these.  In the example above, one
+could have written \code{isPrefix(s1, s2)} and the missing type argument
+\code{[String]} would have been inserted by the type inferencer. 
+
+\section{Type Parameter Bounds}
+
+Now that we know how to make classes generic it is natural to
+generalize some of the earlier classes we have written. For instance
+class \code{IntSet} could be generalized to sets with arbitrary
+element types. Let's try. The trait for generic sets is easily
+written.
+\begin{lstlisting}
+trait Set[a] { 
+  def incl(x: a): Set[a]; 
+  def contains(x: a): boolean; 
+}
+\end{lstlisting}
+However, if we still want to implement sets as binary search trees, we
+encounter a problem. The \code{contains} and \code{incl} methods both
+compare elements using methods \code{<} and \code{>}. For
+\code{IntSet} this was OK, since type \code{int} has these two
+methods. But for an arbitrary type parameter \code{a}, we cannot
+guarantee this. Therefore, the previous implementation of, say,
+\code{contains} would generate a compiler error.
+\begin{lstlisting}
+  def contains(x: int): boolean = 
+    if (x < elem) left contains x
+          ^ < $\mbox{\sl not a member of type}$ a.
+\end{lstlisting}
+One way to solve the problem is to restrict the legal types that can
+be substituted for type \code{a} to only those types that contain methods
+\code{<} and \code{>} of the correct types. There is a trait
+\code{Ord[a]} in the standard class library Scala which represents
+values which are comparable (via \code{<} and \code{>}) to values of
+type \code{a}. We can enforce the comparability of a type by demanding
+that the type is a subtype of \code{Ord}. This is done by giving an
+upper bound to the type parameter of \code{Set}:
+\begin{lstlisting}
+trait Set[a <: Ord[a]] { 
+  def incl(x: a): Set[a]; 
+  def contains(x: a): boolean; 
+}
+\end{lstlisting}
+The parameter declaration \code{a <: Ord[a]} introduces \code{a} as a
+type parameter which must be a subtype of \code{Ord[a]}, i.e.\ its values
+must be comparable to values of the same type.
+
+With this restriction, we can now implement the rest of the generic
+set abstraction as we did in the case of \code{IntSet}s before.
+
+\begin{lstlisting}
+class EmptySet[a <: Ord[a]] extends Set[a] {
+  def contains(x: a): boolean = false;
+  def incl(x: a): Set[a] = new NonEmptySet(x, new EmptySet[a], new EmptySet[a]);
+}
+\end{lstlisting}
+
+\begin{lstlisting}
+class NonEmptySet[a <: Ord[a]]
+        (elem:int, left: Set[a], right: Set[a]) extends Set[a] {
+  def contains(x: a): boolean = 
+    if (x < elem) left contains x
+    else if (x > elem) right contains x
+    else true;
+  def incl(x: a): Set[a] = 
+    if (x < elem) new NonEmptySet(elem, left incl x, right)
+    else if (x > elem) new NonEmptySet(elem, left, right incl x)
+    else this;
+}
+\end{lstlisting}
+Note that we have left out the type argument in the object creations
+\code{new NonEmptySet(...)}. In the same way as for polymorphic methods,
+missing type arguments in constructor calls are inferred from value
+arguments and/or the expected result type.
+
+Here is an example that uses the generic set abstraction.
+\begin{lstlisting}
+val s = new EmptySet[double].incl(1.0).incl(2.0);
+s.contains(1.5)
+\end{lstlisting}
+This is OK, as type \code{double} implements trait \code{Ord[double]}.
+However, the following example is in error.
+\begin{lstlisting}
+val s = new EmptySet[java.io.File]
+                    ^ java.io.File $\mbox{\sl does not conform to type}$
+                      $\mbox{\sl parameter bound}$ Ord[java.io.File].
+\end{lstlisting}
+To conclude the discussion of type parameter
+bounds, here is the defintion of trait \code{Ord} in scala.
+\begin{lstlisting}
+package scala;
+trait Ord[t <: Ord[t]]: t {
+  def < (that: t): Boolean;
+  def <=(that: t): Boolean = this < that || this == that;
+  def > (that: t): Boolean = that < this;
+  def >=(that: t): Boolean = that <= this;
+}
+\end{lstlisting}
+
+\section{Variance Annotations}\label{sec:first-arrays}
+
+The combination of type parameters and subtyping poses some
+interesting questions. For instance, should \code{Stack[String]} be a
+subtype of \code{Stack[Object]}? Intuitively, this seems OK, since a
+stack of \code{String}s is a special case of a stack of
+\code{Object}s.  More generally, if \code{T} is a subtype of type \code{S}
+then \code{Stack[T]} should be a subtype of \code{Stack[S]}. 
+This property is called {\em co-variant} subtyping.
+
+In Scala, generic types have by default non-variant subtyping. That
+is, with \code{Stack} defined as above, stacks with different element
+types would never be in a subtype relation. However, we can enforce
+co-variant subtyping of stacks by changing the first line of the
+definition of class \code{Stack} as follows.
+\begin{lstlisting}
+class Stack[+a] {
+\end{lstlisting}
+Prefixing a formal type parameter with a \code{+} indicates that
+subtyping is covariant in that parameter. 
+Besides \code{+}, there is also a prefix \code{-} which indicates
+contra-variant subtyping. If \code{Stack} was defined \code{class
+Stack[-a] ...}, then \code{T} a subtype of type \code{S} would imply
+that \code{Stack[S]} is a subtype of \code{Stack[T]} (which in the
+case of stacks would be rather surprising!).
+
+In a purely functional world, all types could be co-variant. However,
+the situation changes once we introduce mutable data. Consider the
+case of arrays in Java or .NET. Such arrays are represented in Scala
+by a generic class \code{Array}. Here is a partial definition of this
+class.
+\begin{lstlisting}
+class Array[a] {
+  def apply(index: int): a
+  def update(index: int, elem: a): unit;
+}
+\end{lstlisting}
+The class above defines the way Scala arrays are seen from Scala user
+programs. The Scala compiler will map this abstraction to the
+underlying arrays of the host system in most cases where this
+possible.
+
+In Java, arrays are indeed covariant; that is, for reference types
+\code{T} and \code{S}, if \code{T} is a subtype of \code{S}, then also
+\code{Array[T]} is a subtype of \code{Array[S]}. This might seem
+natural but leads to safety problems that require special runtime
+checks. Here is an example:
+\begin{lstlisting}
+val x = new Array[String](1);
+val y: Array[Any] = x;
+y(0) = new Rational(1, 2); // this is syntactic sugar for 
+                           // y.update(0, new Rational(1, 2));
+\end{lstlisting}
+In the first line, a new array of strings is created. In the second
+line, this array is bound to a variable \code{y}, of type
+\code{Array[Any]}.  Assuming arrays are covariant, this is OK, since
+\code{Array[String]} is a subtype of \code{Array[Any]}. Finally, in
+the last line a rational number is stored in the array. This is also
+OK, since type \code{Rational} is a subtype of the element type
+\code{Any} of the array \code{y}. We thus end up storing a rational
+number in an array of strings, which clearly violates type soundness. 
+
+Java solves this problem by introducing a run-time check in the third
+line which tests whether the stored element is compatible with the
+element type with which the array was created. We have seen in the
+example that this element type is not necessarily the static element
+type of the array being updated. If the test fails, an
+\code{ArrayStoreException} is raised.
+
+Scala solves this problem instead statically, by disallowing the
+second line at compile-time, because arrays in Scala have non-variant
+subtyping. This raises the question how a Scala compiler verifies that
+variance annotations are correct. If we had simply declared arrays
+co-variant, how would the potential problem have been detected?
+
+Scala uses a conservative approximation to verify soundness of
+variance annotations.  A covariant type parameter of a class may only
+appear in co-variant positions inside the class.  Among the co-variant
+positions are the types of values in the class, the result types of
+methods in the class, and type arguments to other covariant types. Not
+co-variant are types of formal method parameters. Hence, the following
+class definition would have been rejected
+\begin{lstlisting}
+class Array[+a] {
+  def apply(index: int): a;
+  def update(index: int, elem: a): unit;
+                               ^ $\mbox{\sl covariant type parameter}$ a
+                                 $\mbox{\sl appears in contravariant position.}$
+}
+\end{lstlisting}
+So far, so good. Intuitively, the compiler was correect in rejecting
+the \code{update} method in a co-variant class because \code{update}
+potentially changes state, and therefore undermines the soundness of
+co-variant subtyping. 
+
+However, there are also methods which do not mutate state, but where a
+type parameter still appears contra-variantly. An example is
+\code{push} in type \code{Stack}. Again the Scala compiler will reject
+the definition of this method for co-variant stacks.
+\begin{lstlisting}
+class Stack[+a] {
+  def push(x: a): Stack[a] = 
+              ^ $\mbox{\sl covariant type parameter}$ a
+                $\mbox{\sl appears in contravariant position.}$
+\end{lstlisting}
+This is a pity, because, unlike arrays, stacks are purely functional data
+structures and therefore should enable co-variant subtyping. However,
+there is a a way to solve the problem by using a polymorphic method
+with a lower type parameter bound.
+
+\section{Lower Bounds}
+
+We have seen upper bounds for type parameters. In a type parameter
+declaration such as \code{t <: U}, the type parameter \code{t} is
+restricted to range only over subtypes of type \code{U}. Symmetrical
+to this are lower bounds in Scala. In a type parameter declaration
+\code{t >: L}, the type parameter \code{t} is restricted to range only
+over {\em supertypes} of type \code{L}. (One can also combine lower and
+upper bounds, as in \code{t >: L <: U}.)
+
+Using lower bounds, we can generalize the \code{push} method in
+\code{Stack} as follows.
+\begin{lstlisting}
+class Stack[+a] {
+  def push[b >: a](x: b): Stack[b] = new NonEmptyStack(x, this);
+\end{lstlisting}
+Technically, this solves our variance problem since now the type
+parameter \code{a} appears no longer as a parameter type of method
+\code{push}. Instead, it appears as lower bound for another type
+parameter of a method, which is classified as a co-variant position.
+Hence, the Scala compiler accepts the new definition of \code{push}.
+
+In fact, we have not only solved the technical variance problem but
+also have generalized the definition of \code{push}.  Before, we were
+required to push only elements with types that conform to the declared
+element type of the stack. Now, we can push also elements of a
+supertype of this type, but the type of the returned stack will change
+accordingly. For instance, we can now push an \code{Object} onto a
+stack of \code{String}s, but the resulting stack will be a stack of
+\code{Object}s instead of a stack of \code{String}s!
+
+In summary, one should not hesitate to add variance annotations to
+your data structures, as this yields rich natural subtyping
+relationships. The compiler will detect potential soundness
+problems. Even if the compiler's approximation is too conservative, as
+in the case of method \code{push} of class \code{Stack}, this will
+often suggest a useful generalization of the contested method.
+
+\section{Least Types}
+
+Scala does not allow one to parameterize objects with types. That's
+why we orginally defined a generic class \code{EmptyStack[a]}, even
+though a single value denoting empty stacks of arbitrary type would
+do. For co-variant stacks, however, one can use the following idiom:
+\begin{lstlisting}
+object EmptyStack extends Stack[All] { ... }
+\end{lstlisting}
+The identifier \code{All} refers to the bottom type \code{scala.All},
+which is a subtype of all other types. Hence, for co-variant stacks,
+\code{Stack[All]} is a subtype of \code{Stack[T]}, for any other type
+\code{T}. This makes it possible to use a single empty stack object
+in user code. For instance:
+\begin{lstlisting}
+val s = EmptyStack.push("abc").push(new Object());
+\end{lstlisting}
+Let's analyze the type assignment for this expression in detail.  The
+\code{EmptyStack} object is of type \code{Stack[All]}, which has a
+method
+\begin{lstlisting}
+push[b >: All](elem: b): Stack[b] .
+\end{lstlisting}
+Local type inference will determine that the type parameter \code{b}
+should be instantiated to \code{String} in the application 
+\code{EmptyStack.push("abc")}. The result type of that application is hence
+\code{Stack[String]}, which in turn has a method
+\begin{lstlisting}
+push[b >: String](elem: b): Stack[b] .
+\end{lstlisting}
+The final part of the value definition above is the application of
+this method to \code{new Object()}. Local type inference will
+determine that the type parameter \code{b} should this time be
+instantiated to \code{Object}, with result type \code{Stack[Object]}.
+Hence, the type assigned to value \code{s} is \code{Stack[Object]}.
+
+Besides \code{scala.All}, which is a subtype of every other type,
+there is also the type \code{scala.AllRef}, which is a subtype of
+\code{scala.AnyRef}, and every type derived from it. The \code{null}
+literal in Scala is of that type. This makes \code{null} compatible
+with every reference type, but not with a value type such as
+\code{int}.
+
+We conclude this section with the complete improved definition of
+stacks. Stacks have now co-variant subtyping, the \code{push} method
+has been generalized, and the empty stack is represented by a single
+object.
+\begin{lstlisting}
+trait Stack[+a] {
+  def push[b >: a](x: b): Stack[b] = new NonEmptyStack(x, this);
+  def isEmpty: boolean
+  def top: a;
+  def pop: Stack[a];
+}
+object EmptyStack extends Stack[All] {
+  def isEmpty = true;
+  def top = throw new Error("EmptyStack.top");
+  def pop = throw new Error("EmptyStack.pop");
+}
+class NonEmptyStack[{a](elem: a, rest: Stack[a]) extends Stack[a] {
+  def isEmpty = false;
+  def top = elem;
+  def pop = rest;
+}
+\end{lstlisting}
+Many classes in the Scala library are generic. We now present two
+commonly used families of generic classes, tuples and functions. The
+discussion of another common class, lists, is deferred to the next
+chapter.
+
+\section{Tuples}
 
 Sometimes, a function needs to return more than one result. For
-instance, take the function \code{divmod} which returns the quotient
-and rest of two given integer arguments.  Of course, one can
-define a class to hold the two results of \code{divmod}, as in:
+instance, take the function \code{divmod} which returns the integer quotient
+and rest of two given integer arguments.  Of course, one can define a
+class to hold the two results of \code{divmod}, as in:
 \begin{lstlisting}
 case class TwoInts(first: int, second: int);
-
 def divmod(x: int, y: int): TwoInts = new TwoInts(x / y, x % y)
 \end{lstlisting}
 However, having to define a new class for every possible pair of
-result types is very tedious. It should also be unneccessary because
-all such classes have exactly the same structure. In Scala, the
-repetition can be avoided by defining a {\em generic class}:
+result types is very tedious. In Scala one can use instead a
+the generic classes \lstinline@Tuple$n$@, for each $n$ between
+2 and 9.  As an example, here is the definition of Tuple2.
 \begin{lstlisting}
-case class Pair[+a, +b](first: a, second: b);
-
-def divmod(x: int, y: int): Pair[int, int] = new Pair[Int, Int](x / y, x % y)
+package scala;
+case class Tuple2[a, b](_1: a, _2: b);
 \end{lstlisting}
-In this example, \code{[a, b]} are {\em type parameters} of class
-\code{Pair}. In a \code{Pair} type, these parameters are replaced by
-concrete types. For instance, \code{Pair[int, String]} represents the
-type of pairs with \code{int} and \code{String} elements.
-
-Type arguments can be omitted in constructors, if the correct type can
-be inferred from the other constructor arguments or the constructor's
-expected result type. In our example, we could have omitted the type
-arguments in the body of \code{divmod}, because they can be deduced
-from the two value parameters of type \code{int}:
+With \code{Tuple2}, the \code{divmod} method can be written as follows.
+\begin{lstlisting}
+def divmod(x: int, y: int) = new Tuple2[int, int](x / y, x % y)
+\end{lstlisting}
+As usual, type parameters to constructors can be omitted if they are
+deducible from value arguments. Also, Scala defines an alias
+\code{Pair} for \code{Tuple2} (as well as \code{Triple} for \code{Tuple3}).
+With these conventions, \code{divmod} can equivalently be written as
+follows.
+\begin{lstlisting}
+def divmod(x: int, y: int) = Pair(x / y, x % y)
+\end{lstlisting}
+How are elements of tuples acessed? Since tuples are case classes,
+there are two possibilities. One can either access a tuple's fields
+using the names of the constructor parameters \lstinline@_$i$@, as in the following example:
 \begin{lstlisting}
-def divmod(x: int, y: int): Pair[int, int] = new Pair(x / y, x % y)
+val xy = divmod(x, y);
+System.out.println("quotient: " + x._1 + ", rest: " + x._2);
 \end{lstlisting}
-Type parameters are never used in patterns. For instance, here is an
-expression in which \code{divmod}'s result is decomposed:
+Or one uses pattern matching on tuples, as in the following erample:
 \begin{lstlisting}
 divmod(x, y) match {
-  case Pair(n, d) => System.out.println("quotient: " + n + ", rest: " + d);
-}
-\end{lstlisting}
-The type parameters in class \code{Pair} are each prefixed by a
-\code{+} sign.  This indicates that \code{Pair}s are {\em
-covariant}. That is, if types \code{T}$_1$ and \code{T}$_2$ are
-subtypes of types \code{S}$_1$ and \code{S}$_2$, then
-\code{Pair[T}$_1$\code{, T}$_2$\code{]} is a subtype of
-\code{Pair[S}$_1$\code{, S}$_2$\code{]}. For instance,
-\code{Pair[String, int]} is a
-subtype of \code{Pair[Object, long]}. If the \code{+}-annotation was
-missing, the type constructor would be treated as being
-non-variant. That is, pairs with different element types would never
-be in a subtype relation. 
-Besides, \code{+}, there is also a prefix
-\code{-} for contra-variant type constructors. 
-The precise rules that
-for variance annotations are given in Chapter~\ref{sec:variance}.
-
-The idea of pairs is generalized in Scala to tuples of greater arity.
-There is a predefined case class \code{Tuple}$_n$ for every \code{n}
-from \code{2} to \code{9} in Scala's standard library. The
-definitions all follow the template
-\begin{lstlisting}
-case class Tuple$_n$[+a$_1$, ..., +a$_n$](_1: a$_1$, ..., _n: a$_n$);
-\end{lstlisting}
-Class \code{Pair} (as well as class \code{Triple}) are also
-predefined, but not as classes of their own. Instead 
-\code{Pair} is an alias of \code{Tuple2} and \code{Triple} is an
-alias of \code{Tuple3}. 
+  case Pair(n, d) => 
+    System.out.println("quotient: " + n + ", rest: " + d);
+}
+\end{lstlisting}
+Note that type parameters are never used in patterns; it would have
+been illegal to write case \code{Pair[int, int](n, d)}.
+
+\section{Functions}
+
+Scala is a functional language in that functions are first-class
+values.  Scala is also an object-oriented language in that every value
+is an object.  It follows that functions are objects in Scala.  For
+instance, a function from type \code{String} to type \code{int} is
+represented as an instance of the trait \code{Function1[String, int]}.
+The \code{Function1} trait is defined as follows.
+\begin{lstlisting}
+package scala;
+trait Function1[-a, +b] {
+  def apply(x: a): b
+}
+\end{lstlisting}
+Besides \code{Function1}, there are also definitions of
+\code{Function0} and \code{Function2} up to \code{Function9} in the
+standard Scala library. That is, there is one definition for each
+possible number of function parameters between 0 and 9.  Scala's
+function type syntax ~\lstinline@$T_1 \commadots T_n$ => $S$@~ is
+simply an abbreviation for the parameterized type
+~\lstinline@Function$n$[$T_1 \commadots T_n, S$]@~.
+
+Scala uses the same syntax $f(x)$ for function application, no matter
+whether $f$ is a method or a function object. This is made possible by
+the following convention: A function application $f(x)$ where $f$ is
+an object (as opposed to a method) is taken to be a shorthand for
+\lstinline@$f$.apply($x$)@. Hence, the \code{apply} method of a
+function type is inserted automatically where this is necessary.
+
+That's also why we defined array subscripting in
+Section~\ref{sec:first-arrays} by an \code{apply} method.  For any
+array \code{a}, the subscript operation \code{a(i)} is taken to be a
+shorthand for \code{a.apply(i)}.
+
+Functions are an example where a contra-variant type parameter
+declaration is useful. For example, consider the following code:
+\begin{lstlisting} 
+val f: (Object => int)  =  x => x.hashCode();
+val g: (String => int)  =  f
+g("abc")
+\end{lstlisting}
+It's sound to bind the value \code{g} of type \code{String => int} to
+\code{f}, which is of type \code{Object => int}. Indeed, all one can
+do with function of type \code{String => int} is pass it a string in
+order to obtain an integer. Clearly, the same works for function
+\code{f}: If we pass it a string (or any other object), we obtain an
+integer.  This demonstrates that function subtyping is contra-variant
+in its argument type whereas it is covariant in its result type.
+In short, $S \Rightarrow T$ is a subtype of $S' \Rightarrow T'$, provided
+$S'$ is a subtype of $S$ and $T$ is a subtype of $T'$.
+
+\example Consider the Scala code
+\begin{lstlisting}
+val plus1: (int => int)  =  (x: int) => x + 1;
+plus1(2)
+\end{lstlisting}
+This is expanded into the following object code.
+\begin{verbatim}
+val plus1: Function1[int, int] = new Function1[int, int] {
+  def apply(x: int): int = x + 1
+}
+plus1.apply(2)
+\end{lstlisting}
+Here, the object creation \lstinline@new Function1[int, int]{ ... }@
+represents an instance of an {\em anonymous class}. 
 
 \chapter{Lists}
 
@@ -2288,17 +2754,16 @@ val empty = List();
 \end{lstlisting}
 Lists are similar to arrays in languages such as C or Java, but there
 are also three important differences. First, lists are immutable. That
-is, elements of a list can not be changed by assignment. Second, 
+is, elements of a list cannot be changed by assignment. Second, 
 lists have a recursive structure, whereas arrays are flat. Third,
 lists support a much richer set of operations than arrays usually do.
 
+\section{Using Lists}
+
 \paragraph{The List type}
 Like arrays, lists are {\em homogeneous}. That is, the elements of a
 list all have the same type.  The type of a list with elements of type
-\code{T} is written \code{List[T]}. (Compare to \code{T[]} for the
-type of arrays of type \code{T} in C or Java.). Therefore, the 
-definitions of list values above can be annotated with types as
-follows.
+\code{T} is written \code{List[T]} (compare to \code{T[]} in Java).
 \begin{lstlisting}
 val fruit: List[String]    = List("apples", "oranges", "pears");
 val nums : List[int]       = List(1, 2, 3, 4);
@@ -2336,7 +2801,7 @@ All operations on lists can be expressed in terms of the following three:
 \begin{tabular}{ll}
 \code{head}  &  returns the first element of a list,\\
 \code{tail}  &  returns the list consisting of all elements except the\\
-first element,
+& first element,\\
 \code{isEmpty} & returns \code{true} iff the list is empty
 \end{tabular}
 
@@ -2349,15 +2814,15 @@ fruit.head      = "apples"
 fruit.tail.head = "oranges"
 diag3.head      = List(1, 0, 0)
 \end{lstlisting}
-Both \code{head} and \code{tail} are only defined for non-empty lists.
-When selected from an empty list, they cause an error instead.
+The \code{head} and \code{tail} methods are defined only for non-empty
+lists.  When selected from an empty list, they throw an exception.
 
 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 {\em insertion sort}, which works as follows: To sort a
 non-empty list with first element \code{x} and rest \code{xs}, sort
 the remainder \code{xs} and insert the element \code{x} at the right
-position in the result. Sorting an empty list will of course yield the
+position in the result. Sorting an empty list will yield the
 empty list. Expressed as Scala code:
 \begin{lstlisting}
 def isort(xs: List[int]): List[int] =
@@ -2387,64 +2852,8 @@ def insert(x: int, xs: List[int]): List[int] = xs match {
 }
 \end{lstlisting}
 
-\paragraph{Polymorphic functions} Consider the problem of writing a
-  function \code{concat}, which takes a list of element lists as
-  arguments. The result of \code{concat} should be the concatenation of all
-  element lists into a single list. 
-
-When trying to define such a function, we observe that we need to give
-a type for the list elements:
-\begin{lstlisting}
-def concat(xss: List[List[ ?? ]]): List[ ?? ] = ...
-\end{lstlisting}
-Clearly, one could replace \code{??} by \code{int}, say, to obtain a
-function \code{concat} that works on lists of lists of integers. But then the
-same function could not be applied to other kinds of lists. This is a
-pity, since clearly the same algorithm of list concatenation can work
-for lists of any element type. Parameterization lets us generalize
-from a specific instance of a problem to a more general one. So far,
-we have used parameterization only for values, but it is available
-also for types. To arrive at a general version of \code{concat}, we 
-equip it with a type parameter.
-\begin{lstlisting}
-def concat[a](xs: List[List[a]]): List[a] = xs match {
-  case List() => xs
-  case List() :: yss => concat[a](yss)
-  case (x :: xs) :: yss => x :: concat[a](xs :: yss)
-}
-\end{lstlisting}
-Type parameters are arbitrary names; they are enclosed in brackets
-instead of parentheses, so that they can be easily distinguished from
-value parameters. Functions like \code{concat} that take type
-parameters are called {\em polymorphic}. The term comes from the
-Greek, where it means ``having many forms''.
-
-To apply \code{concat}, we pass type parameters as well as value
-parameters to it. For instance,
-\begin{lstlisting}
-val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1));
-concat[int](diag3)
-\end{lstlisting}
-yields \code{List(1, 0, 0, 0, 1, 0, 0, 0, 1)}.
-
-\paragraph{Local Type Inference}
-Passing type parameters such as \code{[int]} all the time can become
-tedious in applications where polymorphic functions are used a
-lot. Quite often, the information in a type parameter is redundant,
-because the correct parameter type can also be determined by
-inspecting the function's value parameters or expected result type.
-Taking \code{concat[int](diag3)} function as an example, we know that
-its value parameter is of type \code{List[List[int]]}, so we can
-deduce that the type parameter must be \code{int}. Scala has a
-fairly powerful type inferencer which allows one to omit type
-parameters to polymorphic functions and constructors in situations
-like these.  In the example above, the \code{int} type parameter would
-have been inferred if it was not given explicitly. In fact, the same
-principle applies in the definition of the value \code{diag3}. 
-Here, type parameters have been inferred for the four calls of
-\code{List}. 
-
-\paragraph{Definition of class List}
+\section{Definition of class List I: First Order Methods}
+\label{sec:list-first-order}
 
 Lists are not built in in Scala; they are defined by an abstract class
 \code{List}, which comes with two subclasses for \code{::} and \code{Nil}.
@@ -2460,10 +2869,12 @@ co-variant in this parameter, which means that
 \code{List[S] <: List[T]} for all types \code{S} and \code{T} such that
 \code{S <: T}.  The class is situated in the package
 \code{scala}. This is a package containing the most important standard
-classes of Scala. \code{List} defines a number of methods, which are
+classes of Scala.
+ \code{List} defines a number of methods, which are
 explained in the following.
 
-First, there are the three basic functions \code{isEmpty}, 
+\paragraph{Decomposing lists}
+First, there are the three basic methods \code{isEmpty},
 \code{head}, \code{tail}. Their implementation in terms of pattern
 matching is straightforward:
 \begin{lstlisting}
@@ -2472,11 +2883,11 @@ def isEmpty: boolean = match {
   case x :: xs => false 
 }   
 def head: a = match { 
-  case Nil => error("Nil.head") 
+  case Nil => throw new Error("Nil.head") 
   case x :: xs => x 
 }
 def tail: List[a] = match { 
-  case Nil => error("Nil.tail") 
+  case Nil => throw new Error("Nil.tail") 
   case x :: xs => x 
 }
 \end{lstlisting}
@@ -2488,7 +2899,6 @@ def length = match {
   case x :: xs => 1 + xs.length
 }
 \end{lstlisting}
-
 \exercise Design a tail-recursive version of \code{length}.
 
 The next two functions are the complements of \code{head} and
@@ -2504,7 +2914,7 @@ efficient than their \code{head} and \code{tail} analogues.
 Here is the implementation of \code{last}.
 \begin{lstlisting}
 def last: a = match {
-  case Nil      => error("Nil.last")
+  case Nil      => throw new Error("Nil.last")
   case x :: Nil => x
   case x :: xs  => xs.last
 }
@@ -2520,17 +2930,14 @@ def take(n: int): List[a] =
 def drop(n: int): List[a] = 
   if (n == 0 || isEmpty) this else tail.drop(n-1);
 
-def split(n: int): Pair[List[a], List[a]] = 
-  if (n == 0 || isEmpty) Pair(Nil, this)
-  else tail.split(n - 1) match { case Pair(xs, ys) => (head :: xs, ys) }
+def split(n: int): Pair[List[a], List[a]] = Pair(take(n), drop(n))
 \end{lstlisting}
 \code{(xs take n)} returns the first \code{n} elements of list
 \code{xs}, or the whole list, if its length is smaller than \code{n}.
 \code{(xs drop n)} returns all elements of \code{xs} except the
 \code{n} first ones. Finally, \code{(xs split n)} returns a pair
 consisting of the lists resulting from \code{xs take n} and
-\code{xs drop n}, but the call is more efficient than performing the
-two calls separately. 
+\code{xs drop n}.
 
 The next function returns an element at a given index in a list.
 It is thus analogous to array subscripting. Indices start at 0.
@@ -2546,14 +2953,14 @@ $xs_m \commadots xs_{n-1}$ of a list \code{xs}, use:
 xs.drop(m).take(n - m)
 \end{lstlisting}
 
-The next function combines two lists into a list of pairs.
-Given two lists 
+\paragraph{Zipping lists} The next function combines two lists into a list of pairs.
+Given two lists
 \begin{lstlisting}
 xs = List(x$_1$, ..., x$_n$)   $\mbox{\rm, and}$
 ys = List(y$_1$, ..., y$_n$)   ,
 \end{lstlisting}
 \code{xs zip ys} constructs the list
-\code{Pair(x}$_1$\code{, y}$_1$\code{), ..., Pair(x}$_n$\code{, y}$_n$\code{)}.
+\code{List(Pair(x}$_1$\code{, y}$_1$\code{), ..., Pair(x}$_n$\code{, y}$_n$\code{))}.
 If the two lists have different lengths, the longer one of the two is
 truncated. Here is the definition of \code{zip} -- note that it is a
 polymorphic method.
@@ -2563,6 +2970,7 @@ def zip[b](that: List[b]): List[Pair[a,b]] =
   else Pair(this.head, that.head) :: (this.tail zip that.tail);
 \end{lstlisting}
 
+\paragraph{Consing lists.}
 Like any infix operator, \code{::}
 is also implemented as a method of an object. In this case, the object
 is the list that is extended. This is possible, because operators
@@ -2582,7 +2990,7 @@ operators concerns their associativity.  Operators ending in
 `\code{:}' are right-associative, whereas other operators are
 left-associative.  E.g.,
 \begin{lstlisting}
-    x :: y :: z = x :: (y :: z)      $\mbox{\rm whereas}$       x + y + z = (x + y) + z
+    x :: y :: z = x :: (y :: z)   $\mbox{\rm whereas}$    x + y + z = (x + y) + z
 \end{lstlisting}
 The definition of \code{::} as a method in
 class \code{List} is as follows:
@@ -2596,6 +3004,7 @@ is in this case a list of \code{B}'s. This
 is expressed by the type parameter \code{b} with lower bound \code{a}
 in the signature of \code{::}. 
 
+\paragraph{Concatenating lists}
 An operation similar to \code{::} is list concatenation, written
 `\code{:::}'. The result of \code{(xs ::: ys)} is a list consisting of
 all elements of \code{xs}, followed by all elements of \code{ys}.
@@ -2613,21 +3022,20 @@ Here is the implementation of the \code{:::} method:
   }
 \end{lstlisting}
 
-\paragraph{Example: Reverse} As another example of how to program with
-lists consider a list reversal. There is a method \code{reverse} in
-\code{List} to that effect, but let's implement it as a function
-outside the class. Here is a possible implementation of
-\code{reverse}:
+\paragraph{Reversing lists} Another useful operation
+is list reversal. There is a method \code{reverse} in \code{List} to
+that effect. Let's try to give its implementation:
 \begin{lstlisting}
 def reverse[a](xs: List[a]): List[a] = xs match {
-  case List() => List()
+  case Nil => Nil
   case x :: xs => reverse(xs) ::: List(x)
 }
 \end{lstlisting}
-The implementation is quite simple. However, it is not very efficient.
-Indeed, one concatenation is executed for every element in the
-list. List concatenation takes time proportional to the length
-of its first operand. Therefore, the complexity of \code{reverse(xs)} is 
+This implementation has the advantage of being simple, but it is not
+very efficient.  Indeed, one concatenation is executed for every
+element in the list. List concatenation takes time proportional to the
+length of its first operand. Therefore, the complexity of
+\code{reverse(xs)} is
 \[
 n + (n - 1) + ... + 1 = n(n+1)/2
 \]
@@ -2635,7 +3043,8 @@ where $n$ is the length of \code{xs}. Can \code{reverse} be
 implemented more efficiently? We will see later that there exists
 another implementation which has only linear complexity.
 
-\paragraph{Example: Merge sort}
+\section{Example: Merge sort}
+
 The insertion sort presented earlier in this chapter is simple to
 formulate, but also not very efficient. It's average complexity is
 proportional to the square of the length of the input list. We now
@@ -2657,17 +3066,14 @@ generality by passing these two items as parameters. This leads to the
 following implementation.
 \begin{lstlisting}
 def msort[a](less: (a, a) => boolean)(xs: List[a]): List[a] = {
+  def merge(xs1: List[a], xs2: List[a]): List[a] = 
+    if (xs1.isEmpty) xs2
+    else if (xs2.isEmpty) xs1
+    else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
+    else xs2.head :: merge(xs1, xs2.tail);
   val n = xs.length/2;
   if (n == 0) xs
-  else {
-    def merge(xs1: List[a], xs2: List[a]): List[a] = 
-      if (xs1.isEmpty) xs2
-      else if (xs2.isEmpty) xs1
-      else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
-      else xs2.head :: merge(xs1, xs2.tail);
-
-    merge(msort(less)(xs take n), msort(less)(xs drop n))
-  }
+  else merge(msort(less)(xs take n), msort(less)(xs drop n))
 }
 \end{lstlisting}
 The complexity of \code{msort} is $O(N;log(N))$, where $N$ is the
@@ -2689,19 +3095,751 @@ sorting lists.
 
 Here is an example how \code{msort} is used.
 \begin{lstlisting}
-def iless(x: int, y: int) = x < y
-msort(iless)(List(5, 7, 1, 3))
+msort(x: int, y: int => x < y)(List(5, 7, 1, 3))
 \end{lstlisting}
 The definition of \code{msort} is curried, to make it easy to specialize it with particular
 comparison functions. For instance,
 \begin{lstlisting}
 
-val intSort = msort(iless)
+val intSort = msort(x: int, y: int => x < y)
 val reverseSort = msort(x: int, y: int => x > y)
 \end{lstlisting}
 
-\section*{Higher-Order Methods}
+\section{Definition of class List II: Higher-Order Methods}
+
+The examples encountered so far show that functions over lists often
+have similar structures. We can identify several patterns of
+computation over lists, like:
+\begin{itemize}
+      \item transforming every element of a list in some way.
+      \item extracting from a list all elements satisfying a criterion.
+      \item combine the elements of a list using some operator.
+\end{itemize}
+Functional programming languages enable programmers to write eneral
+functions which implement patterns like this by means of higher order
+functions. We now discuss a set of commonly used higher-order
+functions, which are implemented as methods in class \code{List}.
+
+\paragraph{Mapping over lists}
+A common operation is to transform each element of a list and then
+return the lists of results.  For instance, to scale each element of a
+list by a given factor.
+\begin{lstlisting}
+def scaleList(xs: List[double], factor: double): List[double] = xs match {
+  case Nil => xs
+  case x :: xs1 => x * factor :: scaleList(xs1, factor)
+}
+\end{lstlisting}
+This pattern can be generalized to the \code{map} method of class \code{List}:
+\begin{lstlisting}
+abstract class List[a] { ...
+  def map[b](f: a => b): List[b] = this match {
+    case Nil => this
+    case x :: xs => f(x) :: xs.map(f)
+  }
+\end{lstlisting}
+Using \code{map}, \code{scaleList} can be more consisely written as follows.
+\begin{lstlisting}
+def scaleList(xs: List[double], factor: double) = 
+  xs map (x => x * factor)
+\end{lstlisting}
+
+\exercise Consider a function which squares all elements of a list and
+returns a list with the results. Complete the following two equivalent
+definitions of \code{squareList}.
+
+\begin{lstlisting}
+def squareList(xs: List[int]): List[int] = xs match {
+  case List() => ??
+  case y :: ys => ??
+}
+def squareList(xs: List[int]): List[int] = 
+  xs map ??
+\end{lstlisting}
+
+\paragraph{Filtering Lists}
+Another common operation selects from a list all elements fulfilling a
+given criterion. For instance, to return a list of all positive
+elements in some given lists of integers:
+\begin{lstlisting}
+def posElems(xs: List[int]): List[int] = xs match {
+  case Nil => xs
+  case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1)
+}
+\end{lstlisting}
+This pattern is generalized to the \code{filter} method of class \code{List}:
+\begin{lstlisting}
+  def filter(p: a => boolean): List[a] = this match {
+    case Nil => this
+    case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
+  }
+\end{lstlisting}
+Using \code{filter}, \code{posElems} can be more consisely written as
+follows.
+\begin{lstlisting}
+def posElems(xs: List[int]): List[int] = 
+  xs filter (x => x > 0)
+\end{lstlisting}
+
+An operation related to filtering is testing whether all elements of a
+list satisfy a certain condition. Dually, one might also be interested
+in the question whether there exists an element in a list that
+satisfies a certain condition. These operations are embodied in the
+higher-order functions \code{forall} and \code{exists} of class
+\code{List}.
+\begin{lstlisting}
+def forall(p: a => Boolean): Boolean =
+  isEmpty || (p(head) && (tail forall p));
+def exists(p: a => Boolean): Boolean =
+  !isEmpty && (p(head) || (tail exists p));
+\end{lstlisting}
+To illustrate the use of \code{forall}, consider the question whether
+a number if prime. Remember that a number $n$ is prime of it can be
+divided without remainder only by one and itself. The most direct
+translation of this definition would test that $n$ divided by all
+numbers from 2 upto and excluding itself gives a non-zero
+remainder. This list of numbers can be generated using a function
+\code{List.range} which is defined in object \code{List} as follows.
+\begin{lstlisting}
+package scala;
+object List { ... 
+  def range(from: int, end: int): List[int] = 
+    if (from >= end) Nil else from :: range(from + 1, end);
+\end{lstlisting}
+For example, \code{List.range(2, n)}
+generates the list of all integers from 2 upto and excluding $n$.
+The function \code{isPrime} can now simply be defined as follows.
+\begin{lstlisting}
+def isPrime(n: int) = 
+  List.range(2, n) forall (x => n % x != 0)
+\end{lstlisting}
+We see that the mathematical definition of prime-ness has been
+translated directly into Scala code. 
+
+Exercise: Define \code{forall} and \code{exists} in terms of \code{filter}.
+
+
+\paragraph{Folding and Reducing Lists}
+Another common operation is to combine the elements of a list with
+some operator.  For instance:
+\begin{lstlisting}
+sum(List(x$_1$, ..., x$_n$))       =  0 + x$_1$ + ... + x$_n$
+product(List(x$_1$, ..., x$_n$))   =  1 * x$_1$ * ... * x$_n$
+\end{lstlisting}
+Of course, we can implement both functions with a
+recursive scheme:
+\begin{lstlisting}
+def sum(xs: List[int]): int = xs match {
+  case Nil => 0
+  case y :: ys => y + sum(ys)
+}
+def product(xs: List[int]): int = xs match {
+  case Nil => 1
+  case y :: ys => y * product(ys)
+}
+\end{lstlisting}
+But we can also use the generaliztion of this program scheme embodied
+in the \code{reduceLeft} method of class \code{List}.  This method
+inserts a given binary operator between adjacent elements of a given list.
+E.g.\ 
+\begin{lstlisting}
+List(x$_1$, ..., x$_n$).reduceLeft(op) = (...(x$_1$ op x$_2$) op ... ) op x$_n$
+\end{lstlisting}
+Using \code{reduceLeft}, we can make the common pattern
+in \code{sum} and \code{product} apparent:
+\begin{lstlisting}
+def sum(xs: List[int])      =  (0 :: xs) reduceLeft {(x, y) => x + y}
+def product(xs: List[int])  =  (1 :: xs) reduceLeft {(x, y) => x * y}
+\end{lstlisting}
+Here is the implementation of \code{reduceLeft}.
+\begin{lstlisting}
+  def reduceLeft(op: (a, a) => a): a = this match {
+    case Nil     => error("Nil.reduceLeft")
+    case x :: xs => (xs foldLeft x)(op)
+  }
+  def foldLeft[b](z: b)(op: (b, a) => b): b = this match {
+    case Nil => z
+    case x :: xs => (xs foldLeft op(z, x))(op)
+  }
+}
+\end{lstlisting}
+We see that the \code{reduceLeft} method is defined in terms of
+another generally useful method, \code{foldLeft}.  The latter takes as
+additional parameter an {\em accumulator} \code{z}, which is returned
+when \code{foldLeft} is applied on an empty list. That is,
+\begin{lstlisting}
+(List(x$_1$, ..., x$_n$) foldLeft z)(op)   =  (...(z op x$_1$) op ... ) op x$_n$
+\end{lstlisting}
+The \code{sum} and \code{product} methods can be defined alternatively
+using \code{foldLeft}:
+\begin{lstlisting}
+def sum(xs: List[int])      =  (xs foldLeft 0) {(x, y) => x + y}
+def product(xs: List[int])  =  (xs foldLeft 1) {(x, y) => x * y}
+\end{lstlisting}
+
+\paragraph{FoldRight and ReduceRight}
+Applications of \code{foldLeft} and \code{reduceLeft} expand to
+left-leaning trees. \todo{insert pictures}.  They have duals
+\code{foldRight} and \code{reduceRight}, which produce right-leaning
+trees.
+\begin{lstlisting}
+List(x$_1$, ..., x$_n$).reduceRight(op)     =  x$_1$ op ( ... (x$_{n-1}$ op x$_n$)...)
+(List(x$_1$, ..., x$_n$) foldRight acc)(op) =  x$_1$ op ( ... (x$_n$ op acc)...)
+\end{lstlisting}
+These are defined as follows.
+\begin{lstlisting}
+  def reduceRight(op: (a, a) => a): a = match 
+    case Nil => error("Nil.reduceRight")
+    case x :: Nil => x
+    case x :: xs => op(x, xs.reduceRight(op))
+  }
+  def foldRight[b](z: b)(op: (a, b) => b): b = match {
+    case Nil => z
+    case x :: xs => op(x, (xs foldRight z)(op))
+  }
+\end{lstlisting}
+
+Class \code{List} defines also two symbolic abbreviations for
+\code{foldLeft} and \code{foldRight}:
+\begin{lstlisting}
+  def /:[b](z: b)(f: (b, a) => b): b = foldLeft(z)(f);
+  def :/[b](z: b)(f: (a, b) => b): b = foldRight(z)(f);
+\end{lstlisting}
+The \code{:} part of the method name points in each case to the list
+argument whereas the slash points to the accumulator (or: zero)
+argument \code{z}.  That is,
+\begin{lstlisting}
+(z /: List(x$_1$, ..., x$_n$))(op) = (...(z op x$_1$) op ... ) op x$_n$ 
+(List(x$_1$, ..., x$_n$) :/ z)(op) = x$_1$ op ( ... (x$_n$ op acc)...)
+\end{lstlisting}
+For associative and commutative operators, \code{/:} and
+\code{:/} are equivalent (even though there may be a difference
+in efficiency).  But sometimes, only one of the two operators is
+appropriate or has the right type:
+
+\exercise Consider the problem of writing a function \code{flatten},
+which takes a list of element lists as arguments. The result of
+\code{flatten} should be the concatenation of all element lists into a
+single list. Here is the an implementation of this method in terms of 
+\code{:/}.
+\begin{lstlisting}
+def flatten[a](xs: List[List[a]]): List[a] = 
+  (xs :/ Nil) {(x, xs) => x ::: xs}
+\end{lstlisting} 
+In this case it is not possible to replace the application of
+\code{:/} with \code{/:}. Explain why.
+
+In fact \code{flatten} is predefined together with a set of other
+userful function in an object called \code{List} in the standatd Scala
+library. It can be accessed from user program by calling
+\code{List.flatten}. Note that \code{flatten} is not a method of class
+\code{List} -- it would not make sense there, since it applies only
+to lists of lists, not to all lists in general.
+
+\paragraph{List Reversal Again} We have seen in 
+Section~\ref{sec:list-first-order} an implementation of method
+\code{reverse} whose run-time was quadratic in the length of the list
+to be reversed. We now develop a new implementation of \code{reverse},
+which has linear cost.  The idea is to use a \code{foldLeft}
+operation based on the following program scheme.
+\begin{lstlisting}
+class List[+a] { ...
+  def reverse: List[a] = (z? /: this)(op?)
+\end{lstlisting}
+It only remains to fill in the \code{z?} and \code{op?} parts.  Let's
+try to deduce them from examples.
+\begin{lstlisting}
+  Nil
+= Nil.reverse                 // by specification
+= (z /: Nil)(op)              // by the template for reverse
+= (Nil foldLeft z)(op)        // by the definition of /:
+= z                           // by definition of foldLeft
+\end{lstlisting}
+Hence, \code{z?} must be \code{Nil}. To deduce the second operand,
+let's study reversal of a list of length one.
+\begin{lstlisting}
+  List(x)
+= List(x).reverse             // by specification
+= (Nil /: List(x))(op)        // by the template for reverse, with z = Nil
+= (List(x) foldLeft Nil)(op)  // by the definition of /:
+= op(Nil, x)                  // by definition of foldLeft
+\end{lstlisting}
+Hence, \code{op(Nil, x)} equals \code{List(x)}, which is the same
+as \code{x :: Nil}. This suggests to take as \code{op} the
+\code{::} operator with its operands exchanged.  Hence, we arrive at
+the following implementation for \code{reverse}, which has linear complexity.
+\begin{lstlisting}
+def reverse: List[a] =
+  ((Nil: List[a]) /: this) {(xs, x) => x :: xs}
+\end{lstlisting}
+(Remark: The type annotation of \code{Nil} is necessary 
+to make the type inferencer work.)
+
+\exercise Fill in the missing expressions to complete the following
+definitions of some basic list-manipulation operations as fold
+operations.
+\begin{lstlisting}
+def mapFun[a, b](xs: List[a], f: a => b): List[b] = 
+  (xs :/ List[b]()){ ?? }
+
+def lengthFun[a](xs: List[a]): int =
+  (0 /: xs){ ?? }
+\end{lstlisting}
+
+\paragraph{Nested Mappings}
+
+We can employ higher-order list processing functions to express many
+computations that are normally expressed as nested loops in imperative
+languages. 
+
+As an example, consider the following problem: Given a positive
+integer $n$, find all pairs of positive integers $i$ and $j$, where 
+$1 \leq j < i < n$ such that $i + j$ is prime. For instance, if $n = 7$,
+the pairs are
+\bda{c|lllllll}
+i     & 2 & 3 & 4 & 4 & 5 & 6 & 6\\
+j     & 1 & 2 & 1 & 3 & 2 & 1 & 5\\ \hline
+i + j & 3 & 5 & 5 & 7 & 7 & 7 & 11
+\eda
+
+A natural way to solve this problem consists of two steps. In a first step,
+one generates the sequence of all pairs $(i, j)$ of integers such that
+$1 \leq j < i < n$. In a second step one then filters from this sequence
+all pairs $(i, j)$ such that $i + j$ is prime.
+
+Looking at the first step in more detail, a natural way to generate
+the sequence of pairs consists of three sub-steps.  First, generate
+all integers between $1$ and $n$ for $i$.  
+\item
+Second, for each integer $i$ between $1$ and $n$, generate the list of
+pairs $(i, 1)$ up to $(i, i-1)$. This can be achieved by a
+combination of \code{range} and \code{map}:
+\begin{lstlisting}
+  List.range(1, i) map (x => Pair(i, x))
+\end{lstlisting}
+Finally, combine all sublists using \code{foldRight} with \code{:::}.
+Putting everything together gives the following expression:
+\begin{lstlisting}
+List.range(1, n)
+  .map(i => List.range(1, i).map(x => Pair(i, x)))
+  .foldRight(List[Pair[int, int]]()) {(xs, ys) => xs ::: ys}
+  .filter(pair => isPrime(pair._1 + pair._2))
+\end{lstlisting}
+
+\paragraph{Flattening Maps}
+The combination of mapping and then concatenating sublists 
+resulting from the map
+is so common that we there is a special method 
+for it in class \code{List}:
+\begin{lstlisting}
+abstract class List[+a] { ...
+  def flatMap[b](f: a => List[b]): List[b] = match {
+    case Nil => Nil
+    case x :: xs => f(x) ::: (xs flatMap f)
+  }
+}
+\end{lstlisting}
+With \code{flatMap}, the pairs-whose-sum-is-prime expression 
+could have been written more concisely as follows.
+\begin{lstlisting}
+List.range(1, n)
+  .flatMap(i => List.range(1, i).map(x => Pair(i, x)))
+  .filter(pair => isPrime(pair._1 + pair._2))
+\end{lstlisting}
+
+\section{Summary}
+
+This chapter has ingtroduced lists as a fundamental data structure in
+programming. Since lists are immutable, they are a common data type in
+functional programming languages. They play there a role comparable to
+arrays in imperative languages. However, the access patterns between
+arrays and lists are quite different. Where array accessing is always
+done by indexing, this is much less common for lists.  We have seen
+that \code{scala.List} defines method called \code{at} for indexing;
+however this operation is much more costly than in the case of arrays
+(linear as opposed to constant time). Instead of indexing, lists are
+usually traversed recursively, where recursion steps are usually based
+on a pattern match over the traversed list. There is also a rich set of
+higher-order combinators which allow one to instantiate a set of
+predefined patterns of computations over lists.
+
+\comment{
+\bsh{Reasoning About Lists}
+
+Recall the concatenation operation for lists:
+
+\begin{lstlisting}
+class List[+a] {
+  ...
+  def ::: (that: List[a]): List[a] = 
+    if (isEmpty) that
+    else head :: (tail ::: that)
+}
+\end{lstlisting}
+
+We would like to verify that concatenation is associative, with the
+empty list \code{List()} as left and right identity:
+\bda{lcl}
+   (xs ::: ys) ::: zs &=& xs ::: (ys ::: zs) \\
+   xs ::: List()          &=& xs \gap =\ List() ::: xs
+\eda
+\redtext{Q}: How can we prove statements like the one above?
+
+\redtext{A}: By \redtext{structural induction} over lists.
+\es
+\bsh{Reminder: Natural Induction}
+
+Recall the proof principle of \redtext{natural induction}:
+
+To show a property \mathtext{P(n)} for all numbers \mathtext{n \geq b}:
+\be
+\item Show that \mathtext{P(b)} holds (\redtext{base case}).
+\item For arbitrary \mathtext{n \geq b} show:
+\begin{quote}
+     if \mathtext{P(n)} holds, then \mathtext{P(n+1)} holds as well
+\end{quote}
+(\redtext{induction step}).
+\ee
+%\es\bs
+\redtext{Example}: Given
+\begin{lstlisting}
+def factorial(n: int): int = 
+  if (n == 0) 1
+  else n * factorial(n-1)
+\end{lstlisting}
+show that, for all \code{n >= 4},
+\begin{lstlisting}
+   factorial(n) >= 2$^n$
+\end{lstlisting}
+\es\bs
+\Case{\code{4}}
+is established by simple calculation of \code{factorial(4) = 24} and \code{2$^4$ = 16}.
+
+\Case{\code{n+1}} 
+We have for \code{n >= 4}:
+\begin{lstlisting}
+    \= factorial(n + 1)
+ =     \> $\expl{by the second clause of factorial(*)}$
+       \> (n + 1) * factorial(n)
+ >=    \> $\expl{by calculation}$
+       \> 2 * factorial(n)
+ >=    \> $\expl{by the induction hypothesis}$
+       \> 2 * 2$^n$.
+\end{lstlisting}
+Note that in our proof we can freely apply reduction steps such as in (*)
+anywhere in a term.
+
+
+This works because purely functional programs do not have side
+effects; so a term is equivalent to the term it reduces to.
+
+The principle is called {\em\redtext{referential transparency}}.
+\es
+\bsh{Structural Induction}
+
+The principle of structural induction is analogous to natural induction:
+
+In the case of lists, it is as follows:
+
+To prove a property \mathtext{P(xs)} for all lists \mathtext{xs},
+\be
+\item Show that \code{P(List())} holds (\redtext{base case}).
+\item For arbitrary lists \mathtext{xs} and elements \mathtext{x} 
+      show:
+\begin{quote}
+     if \mathtext{P(xs)} holds, then \mathtext{P(x :: xs)} holds as well
+\end{quote}
+(\redtext{induction step}).
+\ee
+
+\es
+\bsh{Example}
+
+We show \code{(xs ::: ys) ::: zs  =  xs ::: (ys ::: zs)} by structural induction
+on \code{xs}.
+
+\Case{\code{List()}}
+For the left-hand side, we have:
+\begin{lstlisting}
+    \= (List() ::: ys) ::: zs
+ =     \> $\expl{by first clause of \prog{:::}}$
+       \> ys ::: zs
+\end{lstlisting}
+For the right-hand side, we have:
+\begin{lstlisting}
+    \= List() ::: (ys ::: zs)
+ =     \> $\expl{by first clause of \prog{:::}}$
+       \> ys ::: zs
+\end{lstlisting}
+So the case is established.
+
+\es
+\bs
+\Case{\code{x :: xs}} 
+
+For the left-hand side, we have:
+\begin{lstlisting}
+    \= ((x :: xs) ::: ys) ::: zs
+ =     \> $\expl{by second clause of \prog{:::}}$
+       \> (x :: (xs ::: ys)) ::: zs
+ =     \> $\expl{by second clause of \prog{:::}}$
+       \> x :: ((xs ::: ys) ::: zs)
+ =     \> $\expl{by the induction hypothesis}$
+       \> x :: (xs ::: (ys ::: zs))
+\end{lstlisting}
+
+For the right-hand side, we have:
+\begin{lstlisting}
+    \= (x :: xs) ::: (ys ::: zs)
+ =     \> $\expl{by second clause of \prog{:::}}$
+       \> x :: (xs ::: (ys ::: zs))
+\end{lstlisting}
+So the case (and with it the property) is established.
+
+\exercise
+Show by induction on \code{xs} that \code{xs ::: List()  =  xs}.
+\es
+\bsh{Example (2)}
+
+As a more difficult example, consider function
+\begin{lstlisting}
+abstract class List[a] { ...
+  def reverse: List[a] = match {
+    case List() => List()
+    case x :: xs => xs.reverse ::: List(x)
+  }
+}
+\end{lstlisting}
+We would like to prove the proposition that
+\begin{lstlisting}
+   xs.reverse.reverse  =  xs  .
+\end{lstlisting}
+We proceed by induction over \code{xs}. The base case is easy to establish:
+\begin{lstlisting}
+    \= List().reverse.reverse
+ =     \> $\expl{by first clause of \prog{reverse}}$
+       \> List().reverse
+ =     \> $\expl{by first clause of \prog{reverse}}$
+       \> List()
+\end{lstlisting}
+\es\bs
+For the induction step, we try:
+\begin{lstlisting}
+    \= (x :: xs).reverse.reverse
+ =     \> $\expl{by second clause of \prog{reverse}}$
+       \> (xs.reverse ::: List(x)).reverse
+\end{lstlisting}
+There's nothing more we can do to this expression, so we turn to the right side:
+\begin{lstlisting}
+    \= x :: xs
+ =     \> $\expl{by induction hypothesis}$
+       \> x :: xs.reverse.reverse
+\end{lstlisting}
+The two sides have simplified to different expressions.
+
+So we still have to show that
+\begin{lstlisting}
+  (xs.reverse ::: List(x)).reverse  =  x :: xs.reverse.reverse
+\end{lstlisting}
+Trying to prove this directly by induction does not work.
+
+Instead we have to {\em generalize} the equation to:
+\begin{lstlisting}
+  (ys ::: List(x)).reverse  =  x :: ys.reverse
+\end{lstlisting}
+\es\bs
+This equation can be proved by a second induction argument over \code{ys}.
+(See blackboard).
+
+\exercise
+Is it the case that \code{(xs drop m) at n  =  xs at (m + n)} for all 
+natural numbers \code{m}, \code{n} and all lists \code{xs}?
+
+\es
+\bsh{Structural Induction on Trees}
+
+Structural induction is not restricted to lists; it works for arbitrary
+trees.
+
+The general induction principle is as follows.
+
+To show that property \code{P(t)} holds for all trees of a certain type,
+\bi
+\item Show \code{P(l)} for all leaf trees \code{$l$}.
+\item For every interior node \code{t} with subtrees \code{s$_1$, ..., s$_n$}, 
+      show that \code{P(s$_1$) $\wedge$ ... $\wedge$ P(s$_n$) => P(t)}.
+\ei 
+
+\example Recall our definition of \code{IntSet} with 
+operations \code{contains} and \code{incl}:
+
+\begin{lstlisting}
+abstract class IntSet {
+  abstract def incl(x: int): IntSet
+  abstract def contains(x: int): boolean
+}
+\end{lstlisting}
+\es\bs
+\begin{lstlisting}
+case class Empty extends IntSet {
+  def contains(x: int): boolean = false
+  def incl(x: int): IntSet = NonEmpty(x, Empty, Empty)
+}
+case class NonEmpty(elem: int, left: Set, right: Set) extends IntSet {
+  def contains(x: int): boolean = 
+    if (x < elem) left contains x
+    else if (x > elem) right contains x
+    else true
+  def incl(x: int): IntSet = 
+    if (x < elem) NonEmpty(elem, left incl x, right)
+    else if (x > elem) NonEmpty(elem, left, right incl x)
+    else this
+}
+\end{lstlisting}
+(With \code{case} added, so that we can use factory methods instead of \code{new}).
+
+What does it mean to prove the correctness of this implementation?
+\es
+\bsh{Laws of IntSet}
+
+One way to state and prove the correctness of an implementation is
+to prove laws that hold for it.
+
+In the case of \code{IntSet}, three such laws would be:
+
+For all sets \code{s}, elements \code{x}, \code{y}:
+
+\begin{lstlisting}
+Empty contains x          \= =  false
+(s incl x) contains x     \> =  true
+(s incl x) contains y     \> =  s contains y         if x $\neq$ y
+\end{lstlisting}
+
+(In fact, one can show that these laws characterize the desired data
+type completely).
+
+How can we establish that these laws hold?
+
+\redtext{Proposition 1}: \code{Empty contains x =  false}.
+
+\redtext{Proof}: By the definition of \code{contains} in \code{Empty}.
+\es\bs
+\redtext{Proposition 2}: \code{(xs incl x) contains x = true}
+
+\redtext{Proof:}
+
+\Case{\code{Empty}}
+\begin{lstlisting}
+    \= (Empty incl x) contains x
+ =     \> $\expl{by definition of \prog{incl} in \prog{Empty}}$
+       \> NonEmpty(x, Empty, Empty) contains x
+ =     \> $\expl{by definition of \prog{contains} in \prog{NonEmpty}}$
+       \> true
+\end{lstlisting}
+
+\Case{\code{NonEmpty(x, l, r)}}
+\begin{lstlisting}
+    \= (NonEmpty(x, l, r) incl x) contains x
+ =     \> $\expl{by definition of \prog{incl} in \prog{NonEmpty}}$
+       \> NonEmpty(x, l, r) contains x
+ =     \> $\expl{by definition of \prog{contains} in \prog{Empty}}$
+       \> true
+\end{lstlisting}
+\es\bs
+\Case{\code{NonEmpty(y, l, r)} where \code{y < x}}
+\begin{lstlisting}
+    \= (NonEmpty(y, l, r) incl x) contains x
+ =     \> $\expl{by definition of \prog{incl} in \prog{NonEmpty}}$
+       \> NonEmpty(y, l, r incl x) contains x
+ =     \> $\expl{by definition of \prog{contains} in \prog{NonEmpty}}$
+       \> (r incl x) contains x
+ =     \> $\expl{by the induction hypothesis}$
+       \> true
+\end{lstlisting}
+
+\Case{\code{NonEmpty(y, l, r)} where \code{y > x}} is analogous.
+
+\bigskip
+
+\redtext{Proposition 3}: If \code{x $\neq$ y} then
+\code{xs incl y contains x  =  xs contains x}.
+
+\redtext{Proof:} See blackboard.
+\es
+\bsh{Exercise}
+
+Say we add a \code{union} function to \code{IntSet}:
+
+\begin{lstlisting}
+class IntSet { ...
+  def union(other: IntSet): IntSet
+}
+class Expty extends IntSet { ...
+  def union(other: IntSet) = other
+}
+class NonEmpty(x: int, l: IntSet, r: IntSet) extends IntSet { ...
+  def union(other: IntSet): IntSet = l union r union other incl x
+}
+\end{lstlisting}
+
+The correctness of \code{union} can be subsumed with the following
+law:
+
+\redtext{Proposition 4}: 
+\code{(xs union ys) contains x  =  xs contains x || ys contains x}.
+Is that true ? What hypothesis is missing ? Show a counterexample.
+
+Show Proposition 4 using structural induction on \code{xs}.
+\es
+\comment{
+
+\redtext{Proof:} By induction on \code{xs}.
+
+\Case{\code{Empty}}
+
+\Case{\code{NonEmpty(x, l, r)}}
+
+\Case{\code{NonEmpty(y, l, r)} where \code{y < x}}
+
+\begin{lstlisting}
+    \= (Empty union ys) contains x 
+ =      \> $\expl{by definition of \prog{union} in \prog{Empty}}$
+        \> ys contains x
+ =      \> $\expl{Boolean algebra}$
+        \> false || ys contains x
+ =      \> $\expl{by definition of \prog{contains} in \prog{Empty} (reverse)}$
+        \> (Empty contains x) || (ys contains x)
+\end{lstlisting}
+
+\begin{lstlisting}
+    \= (NonEmpty(x, l, r) union ys) contains x
+ =      \> $\expl{by definition of \prog{union} in \prog{NonEmpty}}$
+        \> (l union r union ys incl x) contains x
+ =      \> $\expl{by Proposition 2}$
+        \> true
+ =      \> $\expl{Boolean algebra}$
+        \> true || (ys contains x)
+ =      \> $\expl{by definition of \prog{contains} in \prog{NonEmpty} (reverse)}$
+        \> (NonEmpty(x, l, r) contains x) || (ys contains x)
+\end{lstlisting}
 
+\begin{lstlisting}
+    \= (NonEmpty(y, l, r) union ys) contains x
+ =      \> $\expl{by definition of \prog{union} in \prog{NonEmpty}}$
+        \> (l union r union ys incl y) contains x
+ =      \> $\expl{by Proposition 3}$
+        \> (l union r union ys) contains x
+ =      \> $\expl{by the induction hypothesis}$
+        \> ((l union r) contains x) || (ys contains x)
+ =      \> $\expl{by Proposition 3}$
+        \> ((l union r incl y) contains x) || (ys contains x)
+\end{lstlisting}
+
+\Case{\code{NonEmpty(y, l, r)} where \code{y < x}}
+ ... is analogous.
+
+\es
+}}
 \chapter{Computing with Streams}
 
 The previous chapters have introduced variables, assignment and
@@ -2742,7 +3880,7 @@ def sumPrimes(start: int, end: int): int = {
 \end{lstlisting}
 Note that the variable \code{i} ``steps through'' all values of the interval
 \code{[start .. end-1]}.
-%\es\bs
+
 A more functional way is to represent the list of values of variable \code{i} directly as \code{range(start, end)}. Then the function can be rewritten as follows.
 \begin{lstlisting}
 def sumPrimes(start: int, end: int) =
@@ -2830,39 +3968,220 @@ rest \code{xs}.  Instead of \code{xs ::: ys}, one uses the operation
 %\redtext
 {Is there another way?}
 
-\bibliographystyle{alpha}
-\bibliography{Scala}
+\chapter{\label{sec:for-notation}For-Comprehensions}
 
-\end{document}
+The last chapter has demonstrated that the use of higher-order
+functions over lists can lead to very concise programs. But sometimes
+the level of abstraction required by these functions makes a program
+hard to understand.
 
+To help understandbility, Scala has a special notation which
+simplifies common patterns of applications of higher-order functions.
+This notation is builds a bridge between set comprehensions in
+mathematics and \code{for} loops in imperative languages such as C or
+Java. It also closely resembles the query notation of relational
+databases.
 
- 
-\paragrph{Higher Order Functions
-\bsh{Patterns of Computation over Lists}
+As a first example, say we are given a list \code{persons} of persons
+with \code{name} and \code{age} fields.  To print the names of all
+persons in the sequence which are aged over 20, one can write:
+\begin{lstlisting}
+for { val p <- persons; p.age > 20 } yield p.name
+\end{lstlisting}
+This is equivalent to the following expression , which uses
+higher-order functions \code{filter} and \code{map}:
+\begin{lstlisting}
+persons filter (p => p.age > 20) map (p => p.name)
+\end{lstlisting}
+The for-expression looks a bit like a for-loop in imperative languages,
+except that it constructs a list of the results of all iterations.
 
-\bi
-\item The examples show that functions over lists often have similar
-      structures
-\item We can identify several patterns of computation like
-      \bi
-      \item Transform every element of a list in some way.
-      \item Extract from a list all elements satisfying a criterion.
-      \item Combine the elements of a list using some operator.
-      \ei
-\item Functional programming languages enable programmers to write
-      general functions which implement patterns like this
-\item These functions are \redtext{\em higher-order functions} which get
-      a transformation or an operator as one argument
-\ei
-\es
+Generally, a for-comprehension is of the form
+\begin{lstlisting}
+for ( $s$ ) yield $e$
+\end{lstlisting}
+Here, $s$ is a sequence of {\em generators} and {\em filters}.  A {\em
+generator} is of the form \code{val x <- e}, where \code{e} is a
+list-valued expression. It binds \code{x} to successive values in the
+list.  A {\em filter} is an expression \code{f} of type
+\code{boolean}.  It omits from consideration all bindings for which
+\code{f} is \code{false}.  The sequence $s$ starts in each case with a
+generator.  If there are several generators in a sequence, later
+generators vary more rapidly than earlier ones.
 
-Pairs, and tuples or greater arity are useful enough to 
+Here are two examples that show how for-comprehensions are used.
+First, let's redo an example of the previous chapter: Given a positive
+integer $n$, find all pairs of positive integers $i$ and $j$, where $1
+\leq j < i < n$ such that $i + j$ is prime. Using the \code{for}
+notation, this problem is solved as follows:
+\begin{lstlisting}
+for (val i <- List.range(1, n);
+     val j <- List.range(1, i);
+     isPrime(i+j)) yield Pair(i, j)
+\end{lstlisting}
+This is arguably much clearer than the solution using \code{map},
+\code{flatMap} and \code{filter} that we have developed previously.
 
- 
+As a second example, consider computing the scalar product of two
+vectors \code{xs} and \code{ys}. using \code{for}, this can be written
+as follows.
+\begin{lstlisting}
+  sum (for { val (x, y) <- xs zip ys } yield x * y)
+\end{lstlisting}
+
+The for-notation is essentially equivalent to common operations of
+database query languages.  For instance, say we are given a book
+database \code{books}, represented as a list of books, where
+\code{Book} is defined as follows.
+\begin{lstlisting}
+case class Book(title: String, uthors: List[String]);
+\end{lstlisting}
+Here is a small example database:
+\begin{lstlisting}
+val books: List[Book] = List(
+  Book {
+    val title = "Structure and Interpretation of Computer Programs";
+    val authors = ["Abelson, Harald", "Sussman, Gerald J."];
+  },
+  Book {
+    val title = "Principles of Compiler Design";
+    val authors = ["Aho, Alfred", "Ullman, Jeffrey"];
+  },
+  Book {
+    val title = "Programming in Modula-2";
+    val authors = ["Wirth, Niklaus"];
+  }
+];
+\end{lstlisting}
+Then, to find the titles of all books whose author's last name is ``Ullman'':
+\begin{lstlisting}
+for { val b <- books; val a <- b.authors; a startsWith "Ullman"
+} yield b.title
+\end{lstlisting}
+(Here, \code{startsWith} is a method in \code{java.lang.String}).  Or,
+to find the titles of all books that have the string ``Program'' in
+their title:
+\begin{lstlisting}
+for { val b <- books; (b.title indexOf "Program") >= 0
+} yield b.title
+\end{lstlisting}
+Or, to find the names of all authors that have written at least two
+books in the database.
+\begin{lstlisting}
+for { val b1 <- books;
+      val b2 <- books;
+      b1 != b2;
+      val a1 <- b1.authors;
+      val a2 <- b2.authors;
+      a1 == a2 } yield a1
+\end{lstlisting}
+The last solution is not yet perfect, because authors will appear
+several times in the list of results.  We still need to remove
+duplicate authors from result lists.  This can be achieved with the
+following function.
+\begin{lstlisting}
+def removeDuplicates[a](xs: List[a]): List[a] =
+  if (xs.isEmpty) xs
+  else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head));
+\end{lstlisting}
+The last expression can be equivalently expressed as follows.
+\begin{lstlisting}
+xs.head :: removeDuplicates(for (val x <- xs.tail; x != xs.head) yield x)
+\end{lstlisting}
 
+\subsection*{Translation of \prog{for}}
+
+Every for-comprehensions can be expressed in terms of the three
+higher-order functions \code{map}, \code{flatMap} and \code{filter}.
+Here is the translation scheme, which is also used by the Scala compiler.
+\begin{itemize}
+\item
+A simple for-comprehension
+\begin{lstlisting}
+for (val x <- e) yield e'
+\end{lstlisting}
+is translated to
+\begin{lstlisting}
+e.map(x => e')
+\end{lstlisting}
+\item
+A for-comprehension
+\begin{lstlisting}
+for (val x <- e; f; s) yield e'
+\end{lstlisting}
+where \code{f} is a filter and \code{s} is a (possibly empty)
+sequence of generators or filters
+is translated to
+\begin{lstlisting}
+for (val x <- e.filter(x => f); s) yield e'
+\end{lstlisting}
+and then translation continues with the latter expression.
+\item
+A for-comprehension
+\begin{lstlisting}
+for (val x <- e; y <- e'; s) yield e''
+\end{lstlisting}
+where \code{s} is a (possibly empty)
+sequence of generators or filters
+is translated to
+\begin{lstlisting}
+e.flatMap(x => for (y <- e'; s) yield e'')
+\end{lstlisting}
+and then translation continues with the latter expression.
+\end{itemize}
+For instance, taking our "pairs of integers whose sum is prime" example:
+\begin{lstlisting}
+for { val i <- range(1, n);
+      val j <- range(1, i-1);
+      isPrime(i+j)
+} yield (i, j)
+\end{lstlisting}
+Here is what we get when we translate this expression:
+\begin{lstlisting}
+range(1, n)
+  .flatMap(i =>
+    range(1, i-1)
+      .filter(j => isPrime(i+j))
+      .map(j => (i, j)))
+\end{lstlisting}
 
+\exercise
+Define the following function in terms of \code{for}.
+\begin{lstlisting}
+def concat(xss: List[List[a]]): List[a] =
+  (xss foldr []) { xs, ys => xs ::: ys }
+\end{lstlisting}
+\exercise
+Translate
+\begin{lstlisting}
+for { val b <- books; val a <- b.authors; a startsWith "Bird" } yield b.title
+for { val b <- books; (b.title indexOf "Program") >= 0 } yield b.title
+\end{lstlisting}
+to higher-order functions.
 
-\chapter{Generic Types and Methods}
+We have seen that the for-translation only relies on the presence of
+methods \code{map},
+\code{flatMap}, and \code{filter}.
+This gives programmers the possibility to have for-syntax for
+other types as well -- one only needs to define \code{map},
+\code{flatMap}, and \code{filter} for these types.
+That's also why we were able to define \code{for} at the same time for
+arrays, iterators, and lists -- all these types have the required
+three methods \code{map},\code{flatMap}, and \code{filter} as members.
+Of course, it is also possible for users and library designers to
+define other types with these methods. There are many examples where
+this is useful: Databases, XML trees, optional values. We will see in
+Chapter~\ref{sec:parsers-results} how for-comprehensions can be used in the
+definition of parsers for context-free grammars that construct
+abstract syntax trees.
+
+\bibliographystyle{alpha}
+\bibliography{Scala}
+
+\end{document}
+
+ 
+\chapter{Iterators}
 
 Classes in Scala can have type parameters. We demonstrate the use of
 type parameters with iterators as an example. An iterator is an object
@@ -2889,7 +4208,7 @@ class RangeIterator(start: int, end: int) extends Iterator[int] {
   def next = {
     val r = current;
     if (current < end) current = current + 1
-    else error("end of iterator");
+    else throw new Error("end of iterator");
     r
   }
 }
@@ -2978,7 +4297,7 @@ of the original iterator that satisfy a criterion \code{p}.
       else false;
     def next: a =
       if (hasNext) { isAhead = false; head.elem }
-      else error("next on empty iterator");
+      else throw new Error("next on empty iterator");
   }
 \end{lstlisting}
 Method \code{map} constructs an iterator which returns all elements of
@@ -3007,7 +4326,7 @@ together all iterators returned from successive calls of \code{f}.
     def next: b =
       if (cur.hasNext) cur.next
       else if (outer.hasNext) { cur = f(outer.next); next }
-      else error("next on empty iterator");
+      else throw new Error("next on empty iterator");
   }
 \end{lstlisting}
 Finally, method \code{zip} takes another iterator and
@@ -3027,7 +4346,7 @@ which always returns an empty sequence:
 \begin{lstlisting}
 class EmptyIterator[a] extends Iterator[a] {
   def hasNext = false;
-  def next: a = error("next on empty iterator");
+  def next: a = throw new Error("next on empty iterator");
 }
 \end{lstlisting}
 A more interesting iterator enumerates all elements of an array.
@@ -3042,7 +4361,7 @@ def arrayIterator[a](xs: Array[a]) = new Iterator[a] {
     i < xs.length;
   def next: a =
     if (i < xs.length) { val x = xs(i) ; i = i + 1 ; x }
-    else error("next on empty iterator");
+    else throw new Error("next on empty iterator");
 }
 \end{lstlisting}
 Another iterator enumerates an integer interval:
@@ -3053,7 +4372,7 @@ def range(lo: int, hi: int) = new Iterator[int] {
     i <= hi;
   def next: int =
     if (i <= hi) { i = i + 1 ; i - 1 }
-    else error("next on empty iterator");
+    else throw new Error("next on empty iterator");
 }
 \end{lstlisting}
 %In fact, enumerating integer intervals is so common that it is
@@ -3270,7 +4589,7 @@ of the original iterator that satisfy a criterion \code{p}.
       else false;
     def next: a =
       if (hasNext) { isAhead = false; head.elem }
-      else error("next on empty iterator");
+      else throw new Error("next on empty iterator");
   }
 \end{lstlisting}
 Method \code{map} constructs an iterator which returns all elements of
@@ -3299,7 +4618,7 @@ together all iterators returned from successive calls of \code{f}.
     def next: b =
       if (cur.hasNext) cur.next
       else if (outer.hasNext) { cur = f(outer.next); next }
-      else error("next on empty iterator");
+      else throw new Error("next on empty iterator");
   }
 \end{lstlisting}
 Finally, method \code{zip} takes another iterator and
@@ -3319,7 +4638,7 @@ which always returns an empty sequence:
 \begin{lstlisting}
 class EmptyIterator[a] extends Iterator[a] {
   def hasNext = false;
-  def next: a = error("next on empty iterator");
+  def next: a = throw new Error("next on empty iterator");
 }
 \end{lstlisting}
 A more interesting iterator enumerates all elements of an array.
@@ -3334,7 +4653,7 @@ def arrayIterator[a](xs: Array[a]) = new Iterator[a] {
     i < xs.length;
   def next: a =
     if (i < xs.length) { val x = xs(i) ; i = i + 1 ; x }
-    else error("next on empty iterator");
+    else throw new Error("next on empty iterator");
 }
 \end{lstlisting}
 Another iterator enumerates an integer interval:
@@ -3345,7 +4664,7 @@ def range(lo: int, hi: int) = new Iterator[int] {
     i <= hi;
   def next: int =
     if (i <= hi) { i = i + 1 ; i - 1 }
-    else error("next on empty iterator");
+    else throw new Error("next on empty iterator");
 }
 \end{lstlisting}
 %In fact, enumerating integer intervals is so common that it is
@@ -3409,213 +4728,6 @@ inferred, so that one can abbreviate to:
 %\code{arrayIterator}, \code{zip} and \code{map}. These are all
 %implicitly inserted by the type inferencer.
 
-\chapter{\label{sec:for-notation}For-Comprehensions}
-
-The last chapter has demonstrated that the use of higher-order
-functions over sequences can lead to very concise programs. But
-sometimes the level of abstraction required by these functions makes a
-program hard to understand.
-
-Here, Scala's \code{for} notation can help. For instance, say we are
-given a sequence \code{persons} of persons with \code{name} and
-\code{age} fields.  That sequence could be an array, or a list, or an
-iterator, or some other type implementing the sequence abstraction
-(this will be made more precise below). To print the names of all
-persons in the sequence which are aged over 20, one writes:
-\begin{lstlisting}
-for { val p <- persons; p.age > 20 } yield p.name
-\end{lstlisting}
-This is equivalent to the following expression , which uses
-higher-order functions \code{filter} and \code{map}:
-\begin{lstlisting}
-persons filter (p => p.age > 20) map (p => p.name)
-\end{lstlisting}
-The for-expression looks a bit like a for-loop in imperative languages,
-except that it constructs a list of the results of all iterations.
-
-Generally, a for-comprehension is of the form
-\begin{lstlisting}
-for ( s ) yield e
-\end{lstlisting}
-(Instead of parentheses, braces may also be used.)
-Here, \code{s} is a sequence of {\em generators} and {\em filters}.
-\begin{itemize}
-\item A {\em generator} is of the form \code{val x <- e},
-where \code{e} is a list-valued expression. It binds \code{x} to
-successive values in the list.
-\item A {\em filter} is an expression \code{f} of type \code{boolean}.
-It omits from consideration all bindings for which \code{f} is \code{false}.
-\end{itemize}
-The sequence must start with a generator.
-If there are several generators in a sequence, later generators vary
-more rapidly than earlier ones.
-
-Here are two examples that show how for-comprehensions are used.
-
-First, given a positive integer \code{n}, find all pairs of positive
-integers
-\code{i}, \code{j}, where \code{1 <= j < i <= n} such that \code{i + j} is prime.
-\begin{lstlisting}
-for { val i <- range(1, n);
-      val j <- range(1, i-1);
-      isPrime(i+j)
-} yield (i, j)
-\end{lstlisting}
-
-As second example, the scalar product of two vectors \code{xs} and
-\code{ys} can now be written as
-follows.
-\begin{lstlisting}
-  sum (for { val (x, y) <- xs zip ys } yield x * y)
-\end{lstlisting}
-The for-notation is essentially equivalent to common operations of
-database query languages.  For instance, say we are given a book
-database \code{books}, represented as a list of books, where
-\code{Book} is defined as follows.
-\begin{lstlisting}
-abstract class Book {
-  val title: String;
-  val authors: List[String]
-}
-\end{lstlisting}
-\begin{lstlisting}
-val books: List[Book] = [
-  new Book {
-    val title = "Structure and Interpretation of Computer Programs";
-    val authors = ["Abelson, Harald", "Sussman, Gerald J."];
-  },
-  new Book {
-    val title = "Principles of Compiler Design";
-    val authors = ["Aho, Alfred", "Ullman, Jeffrey"];
-  },
-  new Book {
-    val title = "Programming in Modula-2";
-    val authors = ["Wirth, Niklaus"];
-  }
-];
-\end{lstlisting}
-Then, to find the titles of all books whose author's last name is ``Ullman'':
-\begin{lstlisting}
-for { val b <- books; val a <- b.authors; a startsWith "Ullman"
-} yield b.title
-\end{lstlisting}
-(Here, \code{startsWith} is a method in \code{java.lang.String}).  Or,
-to find the titles of all books that have the string ``Program'' in
-their title:
-\begin{lstlisting}
-for { val b <- books; (b.title indexOf "Program") >= 0
-} yield b.title
-\end{lstlisting}
-Or, to find the names of all authors that have written at least two
-books in the database.
-\begin{lstlisting}
-for { val b1 <- books;
-      val b2 <- books;
-      b1 != b2;
-      val a1 <- b1.authors;
-      val a2 <- b2.authors;
-      a1 == a2 } yield a1
-\end{lstlisting}
-The last solution is not yet perfect, because authors will appear
-several times in the list of results.  We still need to remove
-duplicate authors from result lists.  This can be achieved with the
-following function.
-\begin{lstlisting}
-def removeDuplicates[a](xs: List[a]): List[a] =
-  if (xs.isEmpty) xs
-  else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head));
-\end{lstlisting}
-The last expression can be equivalently expressed as follows.
-\begin{lstlisting}
-xs.head :: removeDuplicates(for (val x <- xs.tail; x != xs.head) yield x)
-\end{lstlisting}
-
-\subsection*{Translation of \prog{for}}
-
-Every for-comprehensions can be expressed in terms of the three
-higher-order functions \code{map}, \code{flatMap} and \code{filter}.
-Here is the translation scheme, which is also used by the Scala compiler.
-\begin{itemize}
-\item
-A simple for-comprehension
-\begin{lstlisting}
-for (val x <- e) yield e'
-\end{lstlisting}
-is translated to
-\begin{lstlisting}
-e.map(x => e')
-\end{lstlisting}
-\item
-A for-comprehension
-\begin{lstlisting}
-for (val x <- e; f; s) yield e'
-\end{lstlisting}
-where \code{f} is a filter and \code{s} is a (possibly empty)
-sequence of generators or filters
-is translated to
-\begin{lstlisting}
-for (val x <- e.filter(x => f); s) yield e'
-\end{lstlisting}
-and then translation continues with the latter expression.
-\item
-A for-comprehension
-\begin{lstlisting}
-for (val x <- e; y <- e'; s) yield e''
-\end{lstlisting}
-where \code{s} is a (possibly empty)
-sequence of generators or filters
-is translated to
-\begin{lstlisting}
-e.flatMap(x => for (y <- e'; s) yield e'')
-\end{lstlisting}
-and then translation continues with the latter expression.
-\end{itemize}
-For instance, taking our "pairs of integers whose sum is prime" example:
-\begin{lstlisting}
-for { val i <- range(1, n);
-      val j <- range(1, i-1);
-      isPrime(i+j)
-} yield (i, j)
-\end{lstlisting}
-Here is what we get when we translate this expression:
-\begin{lstlisting}
-range(1, n)
-  .flatMap(i =>
-    range(1, i-1)
-      .filter(j => isPrime(i+j))
-      .map(j => (i, j)))
-\end{lstlisting}
-
-\exercise
-Define the following function in terms of \code{for}.
-\begin{lstlisting}
-def concat(xss: List[List[a]]): List[a] =
-  (xss foldr []) { xs, ys => xs ::: ys }
-\end{lstlisting}
-\exercise
-Translate
-\begin{lstlisting}
-for { val b <- books; val a <- b.authors; a startsWith "Bird" } yield b.title
-for { val b <- books; (b.title indexOf "Program") >= 0 } yield b.title
-\end{lstlisting}
-to higher-order functions.
-
-We have seen that the for-translation only relies on the presence of
-methods \code{map},
-\code{flatMap}, and \code{filter}.
-This gives programmers the possibility to have for-syntax for
-other types as well -- one only needs to define \code{map},
-\code{flatMap}, and \code{filter} for these types.
-That's also why we were able to define \code{for} at the same time for
-arrays, iterators, and lists -- all these types have the required
-three methods \code{map},\code{flatMap}, and \code{filter} as members.
-Of course, it is also possible for users and library designers to
-define other types with these methods. There are many examples where
-this is useful: Databases, XML trees, optional values. We will see in
-Chapter~\ref{sec:parsers-results} how for-comprehensions can be used in the
-definition of parsers for context-free grammars that construct
-abstract syntax trees.
-
 \chapter{\label{sec:simple-examples}Pattern Matching}
 
 \todo{Complete}
@@ -3772,30 +4884,30 @@ class AlgBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] {
     def apply(key: kt): vt = this match {
       case Empty => null
       case Node(k, v, l, r) =>
-	if (key < k) l.apply(key)
-	else if (key > k) r.apply(key)
-	else v
+        if (key < k) l.apply(key)
+        else if (key > k) r.apply(key)
+        else v
     }
 
     def extend(key: kt, value: vt): Map = this match {
       case Empty => Node(k, v, Empty, Empty)
       case Node(k, v, l, r) =>
-	if (key < k) Node(k, v, l.extend(key, value), r)
-	else if (key > k) Node(k, v, l, r.extend(key, value))
-	else Node(k, value, l, r)
+        if (key < k) Node(k, v, l.extend(key, value), r)
+        else if (key > k) Node(k, v, l, r.extend(key, value))
+        else Node(k, value, l, r)
     }
 
     def remove(key: kt): Map = this match {
       case Empty => Empty
       case Node(k, v, l, r) =>
-	if (key < k) Node(k, v, l.remove(key), r)
-	else if (key > k) Node(k, v, l, r.remove(key))
-	else if (l == Empty) r
-	else if (r == Empty) l
-	else {
-	  val midKey = r.domain.head
-	  Node(midKey, r.apply(midKey), l, r.remove(midKey))
-	}
+        if (key < k) Node(k, v, l.remove(key), r)
+        else if (key > k) Node(k, v, l, r.remove(key))
+        else if (l == Empty) r
+        else if (r == Empty) l
+        else {
+          val midKey = r.domain.head
+          Node(midKey, r.apply(midKey), l, r.remove(midKey))
+        }
     }
 
     def domain: Stream[kt] = this match {
@@ -3868,8 +4980,8 @@ class OOBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] {
       else if (l == empty) r
       else if (r == empty) l
       else {
-	val midKey = r.domain.head
-	Node(midKey, r(midKey), l, r.remove(midKey))
+        val midKey = r.domain.head
+        Node(midKey, r(midKey), l, r.remove(midKey))
       }
     def domain: Stream[kt] = Stream.concat([l.domain, [k], r.domain]	)
     def range: Stream[vt] = Stream.concat([l.range, [v], r.range])
@@ -3921,10 +5033,10 @@ class MutBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] {
     def extend(key: kt, value: vt): Map =
       if (this eq empty) Map(key, value)
       else {
-	if (key < k) l = l.extend(key, value)
-	else if (key > k) r = r.extend(key, value)
-	else v = value
-	this
+        if (key < k) l = l.extend(key, value)
+        else if (key > k) r = r.extend(key, value)
+        else v = value
+        this
       }
 
     def remove(key: kt): Map =
@@ -3934,11 +5046,11 @@ class MutBinTree[kt extends Ord, vt] extends MapStruct[kt, vt] {
       else if (l eq empty) r
       else if (r eq empty) l
       else {
-	var mid = r
-	while (!(mid.l eq empty)) { mid = mid.l }
-	mid.r = r.remove(mid.k)
-	mid.l = l
-	mid
+        var mid = r
+        while (!(mid.l eq empty)) { mid = mid.l }
+        mid.r = r.remove(mid.k)
+        mid.l = l
+        mid
       }
 
     def domain: Stream[kt] = Stream.concat([l.domain, [k], r.domain])
@@ -4217,7 +5329,7 @@ def expr: Parser[Tree] =
     val es <- rep (
       for {
         val op <- chr('+') ||| chr('-');
-	val e <- expr1
+        val e <- expr1
       } yield (x => Binop(op, x, e)) : Tree => Tree
     )
   } yield applyAll(es, e1);
@@ -4282,22 +5394,22 @@ Here is the complete definition of the new \code{Parser} class.
 
     def map[b](f: a => b) = new Parser[b] {
       def apply(in: List[char]): Result[b] = outer.apply(in) match {
-	case Some((x, in1)) => Some((f(x), in1))
+        case Some((x, in1)) => Some((f(x), in1))
         case None => None
       }
     }
 
     def flatMap[b](f: a => Parser[b]) = new Parser[b] {
       def apply(in: List[char]): Result[b] = outer.apply(in) match {
-	case Some((x, in1)) => f(x)(in1)
+        case Some((x, in1)) => f(x)(in1)
         case None => None
       }
     }
 
     def ||| (def p: Parser[a]) = new Parser[a] {
       def apply(in: List[char]): Result[a] = outer.apply(in) match {
-	case None => p(in)
-	case s => s
+        case None => p(in)
+        case s => s
       }
     }
 
@@ -4617,7 +5729,7 @@ to the derivation rules of the Hindley/Milner type system \cite{hindley-milner}.
 \end{lstlisting}
 The next function, \code{typeOf} is a simplified facade for
 \code{tp}. It computes the type of a given term $e$ in a given
-environment $env$. It does so by creating a fresh type variable \verb$a$,
+environment $env$. It does so by creating a fresh type variable \code{$a$},
 computing a typing substitution that makes \code{env $\ts$ e: a} into
 a derivable type judgment, and finally by returning the result of
 applying the substitution to $a$.
@@ -5058,9 +6170,9 @@ class ComputeServer(n: int) {
     val reply = new SyncVar[a];
     openJobs.write(
       new Job {
-	type t = a;
-	def task = p;
-	def return(x: a) = reply.set(x);
+        type t = a;
+        def task = p;
+        def return(x: a) = reply.set(x);
       }
     )
     (=> reply.get)
@@ -5191,18 +6303,18 @@ Otherwise, the message is appended to the linked list of sent messages.
     val msg: Any = synchronized {
       var s = sent, s1 = s.next;
       while (s1 != null && !f.isDefined(s1.elem)) {
-	s = s1; s1 = s1.next
+        s = s1; s1 = s1.next
       }
       if (s1 != null) {
         s.next = s1.next; s1.elem
       } else {
-	val r = new LinkedList(
+        val r = new LinkedList(
           new Receiver {
             def isDefined(msg: Any) = f.isDefined(msg);
           });
-	lastReceiver.next = r; lastReceiver = r;
-	r.elem.wait;
-	r.elem.msg
+        lastReceiver.next = r; lastReceiver = r;
+        r.elem.wait;
+        r.elem.msg
       }
     }
     f(msg)
@@ -5227,20 +6339,20 @@ with the special \code{TIMEOUT} message.  The implementation of
     val msg: Any = synchronized {
       var s = sent, s1 = s.next;
       while (s1 != null && !f.isDefined(s1.elem)) {
-	s = s1; s1 = s1.next ;
+        s = s1; s1 = s1.next ;
       }
       if (s1 != null) {
         s.next = s1.next; s1.elem
       } else {
-	val r = new LinkedList(
+        val r = new LinkedList(
           new Receiver {
             def isDefined(msg: Any) = f.isDefined(msg);
           }
         )
-	lastReceiver.next = r; lastReceiver = r;
-	r.elem.wait(msec);
+        lastReceiver.next = r; lastReceiver = r;
+        r.elem.wait(msec);
         if (r.elem.msg == null) r.elem.msg = TIMEOUT;
-	r.elem.msg
+        r.elem.msg
       }
     }
     f(msg)
@@ -5299,8 +6411,8 @@ class Auction(seller: Process, minBid: int, closing: Date)
     var maxBidder: Process = null
     while (true) {
       receiveWithin ((closing - Date.currentDate).msec) {
-	case Offer(bid, client) => {
-	  if (bid >= askedBid) {
+        case Offer(bid, client) => {
+          if (bid >= askedBid) {
             if (maxBidder != null && maxBidder != client) {
               maxBidder send BeatenOffer(bid)
             }
@@ -5311,17 +6423,17 @@ class Auction(seller: Process, minBid: int, closing: Date)
         }
 \end{lstlisting}
 \begin{lstlisting}
-	case Inquire(client) => {
-	  client send Status(askedBid, closing)
+        case Inquire(client) => {
+          client send Status(askedBid, closing)
         }
 \end{lstlisting}
 \begin{lstlisting}
-	case TIMEOUT => {
-	  if (maxBidder != null) {
-	    val reply = AuctionConcluded(seller, maxBidder)
-	    maxBidder send reply
-	    seller send reply
-	  } else seller send AuctionFailed
+        case TIMEOUT => {
+          if (maxBidder != null) {
+            val reply = AuctionConcluded(seller, maxBidder)
+            maxBidder send reply
+            seller send reply
+          } else seller send AuctionFailed
           receiveWithin (timeToShutdown) {
             case Offer(_, client) => client send AuctionOver ; discardAndContinue
             case _ => discardAndContinue
@@ -5343,7 +6455,7 @@ class Auction(seller: Process, minBid: int, closing: Date)
       case _ =>
         nWaiting = nWaiting + 1
         if (nWaiting > Limit) {
-	  receiveWithin(0) {
+          receiveWithin(0) {
             case Offer(_, _) => continue
             case TIMEOUT =>
             case _ => discardAndContinue
@@ -5391,9 +6503,9 @@ class Bidder (auction: Process, minBid: int, maxBid: int)
               nextBid = bestBid + Delta
               bid
             case AuctionConcluded(seller, client) =>
-     	      transferPayment(seller, nextBid)
+                   transferPayment(seller, nextBid)
             case _ => continue
-	  }
+          }
 
         case BeatenOffer(bestBid) =>
           nextBid = nextBid + Delta