第四章：函数数据结构

¶主要内容：

1. 类型参数化的协变和逆变(Covariance and contravariance)
2. 高阶函数(high-order function)
3. 自定义函数对象(function objects)
4. 容器层次和并行容器(collection hierachy and parallel collection)

本章将介绍Scala中有趣的部分: Scala集合完全支持两种类型的数据结构——可变和不可变。
在理解Scala集合优越性之前，你需要知道两个概念: 类型参数化(type parameterization)和高阶函数(higher-order functions)。类型参数化允许你创建的类型是其他参数的类型（类似于Java的泛型(generics)）。高阶函数则是你创建 的函数可以将其他函数作为参数。这两个概念使得你可以创意通用的、可重用的组件，如Scala集合。
Scala集合是所有Scala特征中最强大的一部分。Scala库中实现了所有你需要的通用数据结构，他对于所有Scala开发者来说都是必不可少的。最新添加的集合库是并行集合。并行集合使得处理数据并行性问题变得容易。你将会看到并行集 合在大数据集中如何处理，这部分将踏进有趣的路程。

¶4~1〖Introducing type parameterization〗P94

在编程语言中，类型参数化即是指允许你根据类型来定义方法和类，并且该类型在使用时才具体声明。它就像为类型创建了一个占位符一样。类型参数化这个概念和Java、C#的泛型相似，Scala提供了对这类泛型的附加扩展。
在第三章MongoDB的例子中介绍了方法只接收一个文档对象的findOne方法，问题是如果MongoDB的collection为空则返回一个null数据类型，但是并没有具体的null数据类型。一个处理办法就是添加注释，但是添加注释显然不是解决该问题的手段。
相似地，我们可以调用一个Option。Option是Scala的集合类型，和其他集合类型不一样，一个Option包含一个最大的元素。他代表着两种可能的值:None和Some。None表示“没有值”Some表示“某些值”。通过返回Option类型的方法，就可以解决某一个方法没有返回值的情况。
在这个小节中，抛弃所谓的Option类型实现自定义的数据类型。例如，你要创建一个函数用于返回列表中某一值对应的下标，这时你需要考虑各种不同类型的List列表，它会可能是整数，长整数或字符串。那么如何为所有类型建立一个函数呢？那就是 使用参数化类型 ，如我们定义一个参数化类型的函数:

def position[A](xs:List[A],value:A):Int = {
  xs.indexOf(value)
}

这里的A表示只有当这个函数被调用时类型才最终被确定。其中List和alue必须是相同的类型。不同于Java和C#，Scala使用方括号([])声明类型参数。当这个函数被调用并且list是整形时，A就表示是Int。相似地，如果改list是字符型，那么A就表示是String。现在用两个不同的参数测试一下这个方法:

scala> val xs = List("one","two","three")
xs: List[String] = List(one, two, three)

scala> position(xs,"two")
res0: Int = 1

scala> val ys = List(20,30,40)
ys: List[Int] = List(20, 30, 40)

scala> position(ys,40)
res1: Int = 2

scala> position[Int](ys,300)
res2: Int = -1

在最后一个例子中尽管你明确指定了参数化类型的具体值，实际上它是可选的。Scala类型参数化取决于具体传递参数的类型。
现在例子中当没有匹配到元素时，position会返回-1表示。现在，为了取代Int返回结果，希望返回一个新的类型，则可以创建一个容器来封装这个结果，把原来的position 方法修改为：

/** 参数化的方法 */
def position[A](xs:List[A],value:A):Maybe[Int] = {
  val index = xs.indexOf(value)
  if(index != -1) Just(index) else Nil
}

现在，如果返回结果不是-1，方法position将返回Just；否则返回Nil。Just和Nil是两个参数实现自Maybe容器，因此我们需要添加相应的实现。

/**
 * @author Barudisshu
 * @tparam A 替换的数据类型
 */
sealed abstract class Maybe[+A] {
  def isEmpty: Boolean
  def get: A
}

final case class Just[A](value: A) extends Maybe[A] {
  def isEmpty = false
  def get = value
}

case object Nil extends Maybe[Nothing] {
  def isEmpty = true
  def get = throw new NoSuchElementException("Nil.get")
}

在这部分代码中，除了类型参数部分外大部分我们都已经熟悉了。Maybe抽象类实际上就是类型A的 协变 ，下小节将探索类型协变的细节。

¶4~2〖Type variance with covariance and contravariance〗P95

类型参数化(type parameterization)由类型协变性(Type variance)补充构成，类型协变性的机制则是在类型系统中通过指定诸如协变性(convariant)和逆协变性(contravariant)进行约束。子类型的关系给协变带来了问题——在类型参数化中，子类型之间是什么关系？在Scala中，你可以通过class和trait实现参数化，如前面例子。当在class和trait中使用类型参数时，你可以使用 + 号实现协变(如Maybe)。类型协变(Convriance)允许对其父类的协变位置中(如返回值)进行重载和使用狭义类型。如Nil对象作为类型参数是Maybe的子类和scala.Nothing的组合，你使用scala.Nothing的原因是Nil的get方法会抛出异常，因为A是Maybe的协变，你可以返回它子类的狭义类型。因为Nothing是Scala类结构中的最低层，它没有子类，所以使用Nothing实现参数化协变。

¶Usefulness of Nothing in Scala

在Scala中，所有方法和函数都需要有返回类型，在Scala中没有void方法。当你的方法不返回任何东西时，Scala提供scala.Unit类型进行代替方法的返回类型；当你的方法返回类型不确定时，则可以使用scala.Nothing表示，使用比较多的情况就是当抛出一个异常时:

scala> def throwException = throw new RuntimeException("Always throws exception")
throwException: Nothing

所以，当你看到一个方法返回Nothing时，这意味着该方法没有成功返回。如下面在运行时中调用exit(System.exit):

scala> def kill = sys.exit(1)
kill: Nothing

在Scala中，一个不可变的List通过它的参数实现协变，因此List[String]是List[Any]的子类，你可以通过List[Any]声明任意的子类型实例:

scala> val everything: List[Any] = List("one", "two", "three")
everything: List[Any] = List(one, two, three)

协变有许多有用的优点，看下面这个方法:
def ++(that: GenTraversableOnce [A]): List[A]
这个方法接收一个迭代类型并返回一个级联集合。相似地，集合collection.Seq，collection.Iterable和collection.Traversable都提供了同样的方法:

def ++(that: GenTraversableOnce[A]): Traversable[A]
def ++(that: GenTraversableOnce[A]): Iterable[A]
def ++(that: GenTraversableOnce [A]: Seq[A]

Traversable是所有集合类型的父类，方法++在这个trait内仅仅是声明而没有实现。其它子类Seq，Iterable和List等继承该方法。因此，截至目前为止，你所操作的所有集合都是返回同样的类型，而Traversable正好被用作一个协变参数。在本章末尾将展示所有集合的层次结构。

协变(convariance)的相对就是逆协变(contravariance)。在协变的例子中，子类型可以下行，如List。相反地，逆协变的反向就是——子类型上行。逆协变的出现是用于处理可变数据结构的。

¶Mutable objects need to invariant

一个类型参数应该是不变(invariant)，不论它是协变的还是逆协变的。所有Scala可变集合类都是不变的。我们用一个例子来说明为什么可变对象应该是不变的。现在，你可以舒适地使用collection.immutable.List以及对应的可变collection.mutable.ListBuffer。因为ListBuffer是可变的，它被声明是不变的:

final class ListBuffer[A] ...{ ... }

注意，如果声明了一个不可变类型(invarint type)，你需要去掉-和+标记符号，因为你不能再为ListBuffer指定其它类型。因此下面会发生编译错误:

scala> val mxs: ListBuffer[String] = ListBuffer("pants")
mxs: scala.collection.mutable.ListBuffer[String] =
ListBuffer(pants)
scala> val everything: ListBuffer[Any] = mxs
<console>:6: error: type mismatch;
found : scala.collection.mutable.ListBuffer[String]
required: scala.collection.mutable.ListBuffer[Any]
val everything: ListBuffer[Any] = mxs

尽管String是scala.Any的子类型，Scala不会将mxs指向到everything，为了理解为什么，我们假设ListBuffer是可变的，并且下列代码不会发生任何编译错误:

scala> val mxs: ListBuffer[String] = ListBuffer("pants")
mxs: scala.collection.mutable.ListBuffer[String] =
ListBuffer(pants)
scala> val everything: ListBuffer[Any] = mxs
scala> everything += 1
res4: everything.type = ListBuffer(1, pants)

你发现到问题了没有？因为everything是Any类型的，你不能存储任何整型值到一个字符型的集合，这简直在等待灾难的发生。为了避免这类型问题的发生，把一个可变对象(mutable objects)保持不变(invariant)是最好不过的办法。如果是集合中不可变对象的话会发生什么？置于不可变对象的协变不会发生任何问题。如果你把ListBuffer改为List，你会直接获得一个指向List[Any]的List[String]实例而不发生任何问题。

scala> val xs: List[String] = List("pants")
xs: List[String] = List(pants)
scala> val everything: List[Any] = xs
everything: List[Any] = List(pants)

这样指向安全的原因是List是不可变的，你可以添加1 到 xs列表中，并且他会返回一个新的Any类型的List:

scala> 1 :: xs
res5: List[Any] = List(1, pants)

再说一次，上述方法是正确的，因为con(::)方法总是返回一个新的List，而它的类型取决于List元素的类型。这里唯一可以同时存储一个整形值类型和一个引用值类型的类型是scala.Any。请记住，这是可变/不可变对象协变一项重要属性。

要理解逆协变的最好办法就是直接讨论现成的问题，如看看下面Java代码:

Object[] arr = new int[1];
arr[0] = "Hello, there!";

你最后将一个整形数组指向了字符型，幸运的是Java会捕获在运行时抛出的ArrayStoreException异常，Scala会在编译期阻止这类错误并强制将参数类型转为逆协变的(contravarint)或不变的(invariant)。不论是协变的还是逆协变的，类型参数都是不变的。对逆协变最好的解析就是Scala中定义的Function1特性:

trait Function1[-P, +R] { ... }

Scala使用减号(-)表示逆协变，加号(+)表示协变。在Function1中，P是逆协变的，R是协变的。在Scala中，函数包含值和类型。例如，Function1表示任何接收一个参数的函数，问题是为什么Function1对参数逆协变而对返回类型协变。
在回答问题之前，我们用反证法进行论证——对参数协变、对返回类型逆协变会发生什么？假如有这样一个协变参数:

val addOne: Function1[Any, Int] = { x: Int => x + 1 }

因为Int是scala.Any的子类，协变参数应该允许上面的代码编译。这段代码的漏洞是你可以使用任意的类型参数来调用addOne，只要参数是Any的子类。这样做会引起一系列问题，因为该函数只接收Int。Scala作为一门类型安全的(type-safe)语言，不允许你这样做。另外一个唯一可能就是你需要将参数类型声明是不可变的(invariant)，但是这样会使得Function1不易扩展。创建一个类型安全的函数的唯一可行方案就是逆协变参数类型。
你不能使用一个逆协变的返回类型，考虑如下代码:

val asString: Int => Int = { x: Int => (x.toString: Any) }

这段代码是无效的，因为Any是Int的超类，逆协变就是允许你从狭义类型到达广义类型。那下面这个是否正确:

asString(10) + 20

代码最后把20加进一个字符串值，这明显有问题。在处理参数类型和返回类型时，Scala的强类型系统会中止这类错误的发生。要实现一个灵活的、类型安全的Function1特性，唯一可能实现的的方法就是参数类型的逆协变和返回类型的协变。下一小节将介绍类型参数的另一个重要概念——类型参数边界(bounds)。

¶4~3〖Lower and upper type bounds〗P99

在Scala中，类型参数受限于类型边界。类型边界限制类型变量的具体值。下面例子更清晰说明这个概念。下列代码中，函数position在Nil对象中调用get方法时会抛出异常:

scala> val xs = List("one", "two", "three")
xs: List[java.lang.String] = List(one, two, three)
scala> position(xs, "two").get
res3: Int = 1
scala> position(List(), "two").get
java.util.NoSuchElementException: Nil.get
  at Nil$.get(<console>:7)
  at Nil$.get(<console>:5)
  at .<init>(<console>:10)

这是不是说在没有找到元素的时候不应该传递默认值？这种输出结果错误的情况可以控制的。你可以在Maybe抽象类中添加默认回调方法:

sealed abstract class Maybe[+A] {
  def isEmpty: Boolean
  def get: A
  // 添加类型参数的边界
  def getOrElse(default:A):A = {
    if(isEmpty) default else get
  }
}

这里，方法getOrElse会返回在遇到isEmpty为true的时候会返回默认值，若是一个Nil实例时，isEmpty总是true的，则总会有一个默认值返回，但是在编译时会有下列错误:

covariant type A occurs in contravariant position in type => A of value default

因为A是协变类型，Scala不允许协变类型作为输入参数。所以如果A是逆协变类型，你会在编译期获得一下错误:

contravariant type A occurs in covariant position in type => A of method get

有两个方案解决这个问题：一是，Maybe是不可变的(invariant)并用释放掉所有子类型的Just和Nil；二是，使用类型边界。我不愿意放弃这么好的子类型，所以我们就在本地使用类型边界吧。
Scala提供两种类型参数边界：上界和下界。一个参数上界就是声明 T <: A，那么T就是A的子类，A就是参数的上界。要创建一个只允许Maybe子类类型的函数，你可以这样写:

def defaultToNull[A <: Maybe[_]](p: A) = {
  p.getOrElse(null)
}

函数defaultToNull接收参数A，并且它是Maybe的子类型。因为Maybe接收一个类型参数，在定义参数上界时，你必须声明类型参数。如果你不关心类型参数，你可以使用占位符(_)表示。
下界就是指类型参数的下限，T >: A，则限制了T是A的超类。所以你可以使用参数下界来实现getOrElse方法。下面列出完整的Maybe类:

sealed abstract class Maybe[+A] {
  def isEmpty: Boolean
  def get: A
  // 添加类型参数的边界，类型参数下界就是A
  def getOrElse[B >: A](default:B):B = {
    if(isEmpty) default else get
  }
  // 类型参数的上界就是Maybe[_]
  def defaultToNull[B <: Maybe[_]](p: B) = {
    p.getOrElse(null)
  }
}

final case class Just[A](value: A) extends Maybe[A] {
  def isEmpty = false
  def get = value
}

case object Nil extends Maybe[Nothing] {
  def isEmpty = true
  def get = throw new NoSuchElementException("Nil.get")
}

Maybe类定义了协变参数A使得它的子类可以返回更多特殊类型。方法getOrElse则可返回Just的接收类型或者空值时的默认类型。由于默认值被作为一个参数，你必须设置参数下界为A来满足逆协变规则。
Just和Nil两个子类分别代表成功和失败的情况。sealed修改器限制了其它对象创建Maybe的子类。
得到下标后，你就可以调用getOrElse方法而避免任何不需要的异常:

scala> position(List(), "something").getOrElse(-1)
res6: Int = -1
scala> position(List("one", "two", "three"), "three").getOrElse(-1)
res8: Int = 2

Scala的类型系统会非常轻易地在编译期间解析到错误。你已经学习了协变和逆协变的重要规则并创建优秀的类型安全的应用程序，并掌握了Scala类型系统的一些表面知识，并以足够理解本章节的数据结构，后面章节将更多地介绍Scala类型系统并通篇全书。

¶4~4〖Higher-order functions, including map, flatMap, and friends〗P101

函数作为参数或作为返回值的函数称为 高阶函数。在Scala的immutable.List.的方法中存在大量的高阶函数，我们看看其中一个map方法:

class List[+A] ... {
  def map[B](f: A => B) : List[B]
}

这里map中的A表示List类型，B则是新List的类型。要定义一个函数参数，需要使用 => 表示。这里，f是一个函数接收一个A类型的参数并返回一个B类型的结果值。如下，你创建了一个新的List并添加1到每一个元素中:

scala> List(1, 2, 3) map { (x: Int) => x + 1 }
res12: List[Int] = List(2, 3, 4)
scala> List(1, 2, 3) map { _ + 1 }
res13: List[Int] = List(2, 3, 4)
scala> def addOne(num:Int) = num + 1
addOne: (num: Int)Int
scala> List(1, 2, 3) map addOne
res11: List[Int] = List(2, 3, 4)

第一段代码传递了一个匿名函数，该函数中x作为参数并加1；第二段代码使用一个函数字面量，其中占位符表示参数；最后一段则直接传递一个定义好的addOne方法。这是点自由风格编程(pointfree-style propgramming，参考http://www.haskell.org/haskellwiki/Pointfree 中的pointwise和pointfree部分)和函数组合的一个很好的例子，像这样也称之为 名传递(call-by-name)，即函数的参数被内部另外一个函数包装(wrap)。这里的addOne将被map能到达的所有函数所访问。
那一个函数是如何返回另外一个函数的？下面看看对addOne进行重构的之后的返回:

def addOne(num:Int) = {
  // 包含匿名函数的方法
  def ++ = (x:Int) => x + 1
  ++(num)
}
// 中置表示法(没有点号)
scala> List(1,2,3) map addOne
res2: List[Int] = List(2, 3, 4)

¶Call-by-value, call-by-reference, and call-by-name method invocation

Java支持两种方法调用方式: 引用传递和值传递。引用传递就是函数通过引用传递到一个对象。在Scala中，它表示AnyRef的任何子类型。值传递就是函数调用通过值传递。在Scala中值类就是Int、Float等。记住，Scala的拆箱和封箱值类型取决于它在代码中如何使用。除此之外，Scala还提供了名传递(call-by-name)和需求传递(call-by-need)。名传递，就是将函数作为参数进行传递。看下面代码，定义一个log函数:

def log(m: String) = if(logEnabled) println(m)

但为了检索一条日志消息，你需要从错误队列中进行查找——一个耗时操作:

def popErrorMessage = { popMessageFromASlowQueue() }
log("The error message is " + popErrorMessage).

不管log是否可用，这个的参数每次都会被执行，但我们实际上不需要这样做。因此你就可以通过名传递来避免这些不必要的计算操作:

def log(m: => String) = if(logEnabled) println(m)

现在，使用`=>`操作符，函数的参数就是名传递的，在函数没有真正被调用时它不会生效。Scala会将该参数作为函数并在该参数被访问时执行参数内容。所以，如果log是不可用的，参数就永远不会被执行。之后会介绍到lazy集合的名传递调用模式，如Stream。

这里的嵌套函数++返回另外一个函数，该返回函数接收一个Int参数并返回一个Int。在REPL环境中调用++方法，可以看到返回类型Int=>Int:

scala> def ++ = (x:Int) => x + 1
$plus$plus: Int => Int

如何实现一个像map那样可以接收任意list类型的函数？有两个方法可以实现map函数——递归和for-comprehension循环。如下代码是基于递归的、模式匹配的实现方式:

def map[A,B](xs:List[A],f:A=>B):List[B] = {
  xs match{
    case List() => Nil
    case head::tail=>f(head)::map(tail,f)
  }
}

如果List为空，则返回Nil，如果不为空，你将使用模式匹配将List分成head和tail两部分，其中head表示List的第一个元素，tail则表示List中剩余的元素。这里使用::实现了f函数的递归。
现在我们来用map函数处理List(1,2,3)并以addOne作为参数，它们的执行步骤如下:

case 1 :: List(2, 3) => addOne(1) :: map(List(2, 3), addOne)
case 2 :: List(3) => 2 :: addOne(2) :: map(List(3), addOne)
case 3 :: List() => 2 :: 3 :: addOne(3) :: map(List(), addOne)

当所有递归流程走完之后，实际上得到的结果是:

2 :: 3 :: 4 :: Nil

现在，函数f的每一个结果将对空List进行预处理，并组装返回一个新的List:

scala> map(List(1, 2, 3), addOne)
res0: List[Int] = List(2, 3, 4)

¶How does head :: tail work?

大家一定会觉得很奇怪，为什么2 :: 3 :: 4 :: Nil运行后会得到一个List。像这种head::tail模式称为 中缀操作模式 ，实际上head :: tail是构造模式:: (head,tail)的一种速记法。不可变List在Scala中被定义为抽象的密封类(abstract sealed class)，它只有两个子类Nil和::，两个子类都是样本类(case class)。我们知道，样本类最大的好处在于参与到模式匹配中。因此，::(head,tail)将匹配到::样本类中的构造器，并将head作为第一个元素，List作为第二个元素，即tail。

cons(::)的结合性是右对左的。即在表达式2 :: 3 :: 4 :: Nil中，你最先调用的是Nil的::，并返回该操作结果，依此类推。即是Nil.::(2).::(3).::(4)。在Scala中，操作符的结合性取决于操作符最后一个字符。如果操作符以:结尾，则它是 右结合的(right-associative) ，反之，其它操作符则是 左结合的(left-associative) 。操作符的结合性会迷惑许多Scala新手。只要记住，结合性取决于操作符最后一个字符 即可。

下面介绍另一种通过for-comprehension表达式实现的map函数方法:

def map1[A, B](f: A => B, xs: List[A]): List[B] = for(x <- xs) yield f(x)

List中另一个有趣的方法是flatMap，该方法通过一个函数作用List中的所有元素并串联所有结果，最后得到一个新的集合。在List中flatMap方法定义如下:

class List[+A] { ...
  def flatMap[B](f: A => GenTraversableOnce[B]): List[B]
}

GenTraversableOnce表示所有可以实现串行(sequentially)或并行(parallel)迭代的集合类型。在集合库中，所有以Gen开头的特性(trait)都是用于为串行、并行集合提供操作的。现在先看看串行集合。
flatMap方法和map方法相似，具有将集合中的一个集合平面化(flatten)为一个单集合(single collection)的能力。如下例子，你从字符串list中创建一个字符list:

scala> List("one","two", "three", "") flatMap { _.toList }
res5: List[Char] = List(o, n, e, t, w, o, t, h, r, e, e)

前面提到过，String被看作是一个类序列集合(Seq-like collection)，它暴露一个toList方法用于转换为List。在上述代码中，每个元素调用了toList方法。如果你用map代替flatMap，你会得到如下结果:

scala> List("one","two", "three", "") map { _.toList }
res7: List[List[Char]] = List(List(o, n, e), List(t, w, o), List(t, h, r, e, e), List())

可以看到，flatMap将map的结果展平成一个单list，下面是flatMap如何在List中定义:

def flatten[B](xss: List[List[B]]): List[B] = {
  xss match {
    case List() => Nil
    case head :: tail => head ::: flatten(tail)
  }
}
def flatMap[A, B](xs: List[A])(f: A => List[B]) : List[B] = {
  flatten(map(xs, f))
}

这里的flatMap是通过flatten组合map的List来实现单List的扁平化。这里的 ::: 是List中定义的另外一个方法，它用于向List尾部追加另一个List的内容，下面试试这个方法:

scala> flatMap(List("one", "two", "three")) { _.toList }
res9: List[Char] = List(o, n, e, t, w, o, t, h, r, e, e)

这里的flatMap有点不同，它有两个参数集，一个是List，另一个是f:

def flatMap[A, B](xs: List[A])(f: A => List[B]) : List[B]

像这样的函数实现叫做柯里化(currying)。柯里化允许接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数。柯里化将在第五章介绍。这里实现闭包的好处是函数参数可以以闭包{_.toList}的形式进行传递。

¶What’s the difference between a lambda and a closure?

lambda表达式是一个匿名函数——没有函数名的函数。它源于数学中的λ演算而得名，在编程语言中多以回调、lambda关键字或 => 操作符表示整个lambda表达式。闭包(Closure)则多数是词法闭包(Lexical Closure)的简称。词法闭包，顾名思义就是关闭它所定义的语法环境，指代某些其开放绑定（自由变量）已经由其语法环境完成闭合（或者绑定）的 lambda 表达式，从而形成了 闭合的表达式。因此，闭包有两种理解：一是，闭包是在其词法上下文中引用了自由变量的函数；二是，闭包是由函数和与其相关的引用环境组合而成的实体。让我们用一个例子来探索这个事实，提供一个求百分比的例子:

scala> List(100, 200, 300) map { _ * 10/100 }
res34: List[Int] = List(10, 20, 30)

这里你传递给map函数的是一个lambda表达式，现在假设百分比的值会随时改变，把百分值存到一个变量中。

scala> var percentage = 10
percentage: Int = 10
scala> val applyPercentage = (amount:Int) => amount * percentage / 100
applyPercentage: (Int) => <function1>

这里applyPercentage就是一个闭包，因为它时刻与它所创建的环境保持联系，如一个百分数变量:

scala> percentage = 20
percentage: Int = 20
scala> List(100, 200, 300) map applyPercentage
res33: List[Int] = List(20, 40, 60)

lambda表达式和闭包虽然表示不同的概念，但是他们的关系非常接近。闭包只有在被调用时才执行，即“惰性求值”，闭包只是在形式和表现上像函数，但实际上不是函数。函数是一些可执行的代码，这些代码在函数被定义后就确定了，不会在执行时发生变化，所以一个函数只有一个实例。闭包在运行时可以有多个实例，不同的引用环境和相同的函数组合可以产生不同的实例。所以，闭包不是函数，只是行为和函数相似，不是所有被传递的函数都需要转化为闭包，只有引用环境可能发生变化的函数才需要这样做。

使用递归的缺点是在处理大数据集时会产生堆栈溢出，因为计算机需要记住调用函数的位置—返回位置，返回位置会存储在调用栈上。解决这个问题的方式就是实现尾递归，因为实现尾递归不需要记住调用函数的位置，Scala在实现尾调用时优化并转换递归为循环。在尾递归中首先会执行计算，然后执行递归调用传递的当前步骤到下一步的结果内容。下面重构flatten函数实现尾递归处理:

def flatten[B](xss:List[List[B]]):List[B] = {
  def _flatten(oldList: List[List[B]], newList: List[B]): List[B] =
    oldList match {
      case List() => newList
      case head :: tail => _flatten(tail, newList ::: head)
    }
  _flatten(xss, Nil)
}

函数flatten通过尾递归模式的嵌套函数实现。结果中的newList:::head作为一个参数传递给函数，使得Scala编译器可以对其进行优化。关于尾递归的更多内容将在下一章介绍。下一小节介绍另外一个新的概念——折叠(fold)，折叠用于处理具有某些顺序的数据结构并建立一个返回值。

¶4~5〖Using foldLeft and foldRight〗P106

List中定义的另外两个比较有趣的方法是foldLeft和foldRight。这两个操作允许你对List中的所有元素进行二进制操作。它们在List中的定义如下:

class List[+A] {
  ...
  def foldLeft[B](z: B)(f: (B, A) => B): B
  def foldRight[B](z: B)(f: (A, B) => B): B
}

这两个方法不同的地方是参数z传递给函数f的方式。在foldLeft中，z表示开始值，它作为第一个参数传递给f，在foldRight中开始值则是作为第二个参数传递。函数f是一个组合函数用于接收两个参数并生成一个单结果值。为了理解折叠如何工作，让我们再一次看看之前的flatten实现代码。它和map中的递归实现相似:

def map[A, B](xs: List[A], f: A => B): List[B] = {
  xs match {
    case List() => Nil
    case head :: tail => f(head) :: map(tail, f)
  }
}
def flatten[B](xss: List[List[B]]): List[B] = {
  xss match {
    case List() => Nil
    case head :: tail => head ::: flatten(tail)
  }
}

当List为空时执行某操作、不为空时执行另一操作。你可以使用foldRight来避免重复操作:

def map2[A, B](xs: List[A])(f: A => B): List[B] = {
  val startValue = List.empty[B]
  xs.foldRight(startValue) { f(_) :: _ }
}
def flatten2[B](xss: List[List[B]]): List[B] = {
  val startValue = List.empty[B]
  xss.foldRight(startValue) { _ ::: _ }
}

startValue被设置为一个空List，然后组合函数为所有元素提供二元操作。这里使用foldRight的原因是这里使用了右结合(right-associativeness)的 :: 和 ::: 操作符号。当两者都是接收一个空List参数时就不会调用::或:::。我确定现在你一定很熟悉下划线(_)作为参数占位符。这是一个很好的例子，可以在高阶函数中建立普通操作而不必使用重复代码。
应该尽量避免在foldRight中使用递归，因为它潜在堆栈溢出错误的可能。在某些例子中，Scala编译器会将递归函数转换为loop循环，你会在下一章学习有关方面内容。另一个可选实现是使用foldLeft，然后将得到的结果反转。例如将map修改为:

def map[A, B](xs: List[A])(f: A => B): List[B] = {
  val startValue = List.empty[B]
  xs.foldLeft(startValue)((a, x) => f(x) :: a).reverse
}

方法foldLeft提供了一个二元操作从左到右处理开始值和List的所有元素。如下面使用foldLeft计算List的长度:

scala> List(1, 2, 3, 4).foldLeft(0) { _ + _ }
res25: Int = 10
scala> List(1, 2, 3, 4).foldLeft(0) { (a, b) => a + 1 }
res27: Int = 4

第一个例子计算了所有元素的值，第二个计算了List的长度。第二个例子不能使用占位符，因为你不能用所有函数的参数来计算List的长度。
foldLeft和foldRight都有一个别名版本，/:(foldLeft)和:\(foldRight)，你可以用它替换。但Scala开发者更趁于用foldLeft和foldRight象征表示。
折叠是对处理集合数据来建立返回值是一个好方法。map方法和flatMap方法实现集合转换，折叠则实现了结构类型的转换。你可以使用折叠来处理日常遇到的编程问题。如下面一个exists方法使用了foldLeft来判断元素是否存在:

def exists[A](xs: List[A])(e: A) = xs.foldLeft(false) { (a, x) => a || x == e}

可以看到，使用foldLeft和foldRight的好处是就是只需要通过二元操作而不需要添加额外的方法来处理任何数据类型。
由于篇幅只介绍List集合类型，但对于其他集合类型同样适用，在本章末尾将介绍Scala的其他集合类型。

¶4~6〖Building your own function objects〗P108

函数对象(function object)就是一个对象可以作为函数使用。如下代码:

object fold1{
  def apply[A,B](xs:Traversable[A],defaultValue:B)(op:(B,A)=>B) = (defaultValue /: xs)(op)
}

现在我们可以使用这个fold1函数对象，就像使用函数一样:

scala> foldl(List("1", "2", "3"), "0") { _ + _ }
res0: java.lang.String = 0123
scala> foldl(IndexedSeq("1", "2", "3"), "0") { _ + _ }
res24: java.lang.String = 0123
scala> foldl(Set("1", "2", "3"), "0") { _ + _ }
res25: java.lang.String = 0123

前面我们已经看过不少apply方法的例子，apply在函数对象的用法一样。要把一个对象看作函数对象，你只需要声明apply方法即可。在Scala中， <object>(<arguments>)实际上就是<object>.apply(<arguments>)的语法糖 ，当然你可以设置更多的参数。
因为你定义了参数Traversable，它是Scala所有集合的超类，因此你可以传递任何集合类型参数。
表达式(defaultValue /: xs)(op)看起来有些神秘，但它是由替换语法foldLeft演变而来的，/:是foldLeft的别名，并且是以:结尾，这意味着它是右结合的。
声明了函数对象后，现在我们来探索一下Scala库中定义的Function特质。在Scala中，Function1特性被定义如下:

trait Function1[-T1, +R] extends AnyRef {
def apply(v: T1): R
}

这里的1表示带一个参数的函数，相似地，Scala中定义了两个或者多个的类型Function特质。例如，下面代码创建了一个自增的函数，该函数接收一个参数并加1返回:

object ++ extends Function1[Int, Int]{
def apply(p: Int): Int = p + 1
}

这个函数的简化和等效实现是:

val ++ = (x: Int) => x + 1

还有另外一个方法实现这个函数对象：使用function的替换符号 =>

object ++ extends (Int => Int) {
def apply(p: Int): Int = p + 1
}

最后一个例子，你使用了Function1的简写符号Int => Int，在定义高阶函数时，你使用了相似的语法符号。你可以在lambda或闭包的任何地方使用函数对象，例如，你在map中使用这个++函数:

scala> map(List(10, 20, 30), ++)
res1: List[Int] = List(11, 21, 31)

它实际上和匿名函数是等效的:

scala> map(List(10, 20, 30), (x: Int) => x + 1)
res2: List[Int] = List(11, 21, 31)

最终结果都是调用它的Function特性原型

scala> map(List(10, 20, 30), new Function1[Int, Int] {
def apply(p: Int) = p + 1
})
res3: List[Int] = List(11, 21, 31)

当传递一个已有函数(不是函数对象)作为一个参数时，Scala会创建一个新的匿名函数对象，该匿名函数带apply方法，并调用对应原生函数。像这种称为eta规约(eta-expansion)。

什么是eta-expansion？什么是eta-conversion？
这是lambda演算中定义外延相等的公理。

即 lambda x.f x = f
简单来说就是：
把 x => func(x) 简化为 func _ 或 func 的过程称为 eta-conversion
把 func 或 func _ 展开为 x => func(x) 的过程为 eta-expansion
lambda演算中主要有alpha变换，beta规约，eta规约，你说的eta-expansion其实是eta规约规则的逆用。

¶Function1 is also defined as Function

因为Function1使用得非常频繁，Scala定义了一个类型别名Function。你不会在Scaladoc中找到其相关的文档，因为这个类型别名被定义在Predef类中:

type Function[-A, +B] = Function1[A, B]

type为Scala中的关键字，它用于创建一个类型别名，和C中typedef相似。类型变量将在第六章介绍，并将探索如何通过类型变量来创建抽象成员。
类型变量的一个好处是可以用它来表示一个复杂的类型:

type MILS = Map[Int, List[String]]
val mapping: MILS = Map(
    1 -> List("one", "uno"), 2 -> List("two", "dos"))

函数特质允许你及nag两个函数组合成一个新函数。当你趁于通过组合函数来处理问题时，这显得尤为重要。如下我们将相同的函数组装两次，并创建出一个新的函数:

val addOne: Int => Int = x => x + 1
val addTwo: Int => Int = x => x + 2
val addThree = addOne compose addTwo

它和下面的实现相似:

val addThree: Int => Int = x => addOne(addTwo(x))

组合方法允许你将函数链接在一起来组装成一个新的函数。在下一章将介绍到更多关于函数组合的内容。现在我们来探索一下Scala的集合层次结构。

¶4~7〖Scala collection hierarchy〗P110

在Scala2.8发布以来添加的主要特性是提升的集合库。本小节将探索Scala集合的详细内容。
Scala集合类在scala.collection包以及它的子包中，在scala.collection.mutable包中定义了可以改变集合状态的集合类，相反，在scala.collection.immutable保证了不可变性。不可变集合有时被称为持久化数据结构(persistent data structures)。这里的持久化与数据库无关，是指在随着当前程序执行，一个不可变集合保持不变。在一个不可变集合的任何变化会产生一个新的集合，但不涉及到存在的集合。
为实现多种多样的集合，通过分包提供模块构建。一般地你不需要在同属包做任何处理，除非你要实现自定的集合类。
一个定义在scala.collection包中集合类可以是可变的或不可变的。例如，scala.collection.Map[A,+B]是collection.mutable.Map[A,B]和collection.immutable.Map[A,+B]的超类。一般地，在包scala.collection的根集合为可变集合和不可变集合定义了相同的接口，并在不可变集合的顶部添加附加的转换方法。以map为例，它提供了诸如+=和-=的方法用于添加和删除集合中的元素。尽管你可以使用根集合类型作为一个不可变集合的引用类型，但最好是显式地指明集合的类型(可变的还是不可变的)，因为在处理集合时，开发者可以更好的处理代码。下面你声明了既是可变集合，又是不可变集合的collection.Map类型值，并且不清楚mapping的类型是否可以改变:

scala> val mapping: collection.Map[String, String] = Map("Ron" -> "admin",
"Sam" -> "Analyst")
mapping: scala.collection.Map[String,String] =
Map(Ron -> admin, Sam -> Analyst)
scala> val mapping: collection.Map[String, String] =
collection.mutable.Map("Ron" -> "admin", "Sam" -> "Analyst")
mapping: scala.collection.Map[String,String] = Map(Sam -> Analyst, Ron ->
admin)

Scala会自动导入不可变集合，但你需要显式地导入可变集合类型，如这里导入了collection.mutable.Map。Scala的集合层次结构大概有三个主要的集合类型：Set，Seq，Map
集合层次中的根部是Traversable特质，他实现了所有集合类型的通用功能。在Traversable特质中定义的唯一抽象方法是foreach：

def foreach[U](f: Elem => U)

¶Scala collection hierarchy with three main types of collections: Set, Seq, and Map

¶Useful methods defined in the Traversable trait

方法	描述
xs.size	集合中元素的个数
xs ++ ys	由 xs 和 ys 组合的集合
xs map f	为 xs 中的每个 x 作 f(x)
xs flatMap f	为 xs 中的每个 x 作 f(x)，并串联
xs filter p	xs 中存在 x，使得 x 满足 p(x)
xs find p	xs 中存在 x，使得 x 满足 p(x)，不存在则 None
(z /: xs)(h)	xs 中 foldLeft 从右到左对每个元素折叠 h(x,y)
(xs :\ z)(h)	xs 中 foldLeft 从右到左对每个元素折叠 h(x,y)，并反转
xs.head	集合第一个元素(或迭代中的 next)
xs.tail	xs中除 xs.head 剩余的元素
xs mkString sep	生成以 sep 分割的字符串

下面看看一个例子。我们可以在Scala集合中使用Java集合，这里有一个更简单的例子，它可以在Java集合和Traversable之间任意转换:

class JavaToTraversable[E](javaCollection: JCollection[E]) extends Traversable[E] {
  def foreach[U](f : E => U): Unit = {
    val iterator = javaCollection.iterator
    while(iterator.hasNext) {
      f(iterator.next)
    }
  }
}

这里实现了它的唯一一个抽象方法foreach，通过这个方法，你可以使用Traversable子类中带有foreach方法实现所有方法，如map、foldLeft或filter：

scala> val jCol = new ArrayList[Int]
jCol: java.util.ArrayList[Int] = []
scala> (1 to 5) foreach { jCol.add(_) }
scala> jCol
res3: java.util.ArrayList[Int] = [1, 2, 3, 4, 5]
scala> val jtoT = new JavaToTraversable(jCol)
jtoT: JavaToTraversable[Int] = line3(1, 2, 3, 4, 5)
scala> jtoT map { _ * 10 } filter { _ > 20 }
res10: Traversable[Int] = List(30, 40, 50)

在Scala中，你可以定义一个有限的或无限的traversable对象；hasDefiniteSize会决定一个集合是有限的还是无限的。你会在这章最后看到有关例子。

¶4~8〖Mutable and immutable collections〗P113

在scala.collection包中的集合既是可变的，也是不可变的。在前面小节阅读了可变集合类和不可变集合类的区别。我们来看看Iterable特质这个特殊的集合类。它的超类是Traversable。它提供了foreach的实现并暴露了一个新的抽象方法iterator。同时它还提供了Traversable中定义的takeRight和dropRight方法实现。takeRight返回集合最后的n个元素，dropRight则刚好相反:

scala> Iterable(1, 2, 3, 4, 5) dropRight 2
res0: Iterable[Int] = List(1, 2, 3)
scala> Iterable(1, 2, 3, 4, 5) takeRight 2
res1: Iterable[Int] = List(4, 5)

有趣的是Iterable的三个基础类:Seq，Set和Map。这些子类一个共同点是它们都实现了PartialFunction特质，这意味着它们都具有apply方法。现在我们来看看这些子类有哪些特性。

¶4~9〖Working with List and ListBuffer〗P114

在一个序列中，元素被0到length - 1索引，length即为序列的元素个数。因为Seq实现了PartialFunction，因此它有一个apply方法，它是一个从Int到一个元素的局部函数。原因是索引的Int可能在集合中不存在元素。如下我们访问一个存在的元素和一个不存在:

scala> val languages = Seq("Scala", "Haskell", "OCaml", "ML")
languages: Seq[java.lang.String] = List(Scala, Haskell, OCaml, ML)
scala> languages(1)
res11: java.lang.String = Haskell
scala> languages(10)
java.lang.IndexOutOfBoundsException
at scala.collection.LinearSeqLike$class.apply(LinearSeqLike.scala:78)
at scala.collection.immutable.List.apply(List.scala:46)

¶Using a collection as PartialFunction

在PartialFunction特质中，除了定义了apply方法之外，还定义了两个有趣的方法: andThen和orElse。例如，为了避免Seq中没有元素的情况，你可以使用orElse处理局部函数没有找到值的保障方案。

val default: PartialFunction[Int, String] = {
case _ => "Is it a functional language?" }
val languagesWithDefault = languages orElse default

现在访问一个不存在的下标时，它返回一个默认值作为代替。

languagesWithDefault(10) will produce "Is it a functional language?"

更多函数组件的内容将在本书介绍到。

如果一个序列是可变的，如ListBuffer，那么除了提供apply方法外，它还提供了一个update方法。如下代码你创建一个ListBuffer并进行update操作:

scala> import scala.collection.mutable.ListBuffer
import scala.collection.mutable.ListBuffer
scala> val buf = ListBuffer(1.2, 3.4, 5.6)
buf: scala.collection.mutable.ListBuffer[Double] =
ListBuffer(1.2, 3.4, 5.6)
scala> buf(2) = 10
scala> buf
res30: scala.collection.mutable.ListBuffer[Double] =
ListBuffer(1.2, 3.4, 10.0)
scala> buf.update(2, 20)
scala> buf
res32: scala.collection.mutable.ListBuffer[Double] =
ListBuffer(1.2, 3.4, 20.0)

注意这里的buf(2) = 10 和 buf.update(2,20)方法调用是完全相同的。Scala中，Seq的主要两个子类是LinearSeq和Vector。它们提供了不同的性能特征。Vector提供了高效的apply和length操作、LinearSeq提供了高效的head和tail操作。LinearSeq最常见的两个子类是List和Stream。这里介绍了List的使用例子，很快我们再探索Stream的相关内容。

¶What type of collection should I use?

Scala集合提供了丰富多样的集合类型，每个集合类型有不同的性能特征，因此要确保你选择了一个合适的集合类型来处理你的问题。有些情况是你不确定应该使用哪个集合类型时，则应该使用Vector作为援助。总体来说，Vector相比其他集合类型拥有更好的性能特征。

在Scala中， Sequence s的一个有趣子类范畴是Buffer s。Buffer s 总是可变的，在这里我们说得最多的内建集合类就是使用Buffer s。目前最常见的Buffer s子类包括mutable.ListBuffer 和 mutable.ArrayBuffer。

¶4₉1〖Working with Set and SortedSet〗P115

Set是一个迭代集合类型，它不包含重复元素。Set提供了contains方法来检测给出的元素是否在Set中，并且对应的apply方法会做同样的处理。

val frameworks = Set("Lift", "Akka", "Playframework", "Scalaz")
// Both of contains and apply method doing the same things.
assertResult(true){frameworks contains "Lift"}
assertResult(true){frameworks("Playframework")}

若要从一个不可变Set中添加或移除元素，则可以使用 + 和 - 操作符。对于一个可变的Set不推荐使用这些方法，因为它会创建一个新的Set，因为它不会更新自身。一个好的处理Set s的方法是使用 += 和 -= 方法(如下表格内容)。

方法	描述
xs contains x	x是否为xs的一个元素
xs ++ ys	由 xs 和 ys 组合的集合，但不从 ys 中添加重复的元素
xs & ys, xs intersect ys	xs 和 ys 的交集
`xs	f, xs union ys`
xs &~ ys, xs diff ys	xs 和 ys 的补集
xs ++= ys	只作用于可变Set，从 ys 向 xs 添加元素，返回 xs 自身
xs(x) = b, xs.update(x,b)	如果b为true，则将 x 添加 xs；反之则从 xs 移除 x
xs.clear()	移除所有xs的元素

下面是一些关于可变Set和不可变Set的一些添加和移除的例子:

scala> val frameworks = Set() + "Akka" + "Lift" + "Scalaz"
frameworks: scala.collection.immutable.Set[java.lang.String] = Set(Akka,
Lift, Scalaz)
scala> val frameworks = Set("Akka", "Lift", "Scalaz") - "Lift"
frameworks: scala.collection.immutable.Set[java.lang.String] = Set(Akka,
Scalaz)
scala> val mFrameworks = collection.mutable.Set[String]()
mFrameworks: scala.collection.mutable.Set[String] = Set()
scala> mFrameworks += "Akka" += "Lift"
res5: mFrameworks.type = Set(Lift, Akka)
scala> mFrameworks += "Scalacheck"
res12: mFrameworks.type = Set(Lift, Akka, Scalacheck)

除了add和remove方法之外，你可以使用Set的其他操作，如union，intersect和diff。另外，Set有个子类SortedSet。当iterator和foreach在SortedSet中调用时，它会将产生的元素放在合适的顺序上。下列代码片段你添加了两个Set，其中一个使用了Set，另外一个使用SortedSet，在SortedSet中，将维持元素的顺序:

scala> Set(1, 2, 3) ++ Set(3, 4, 5)
res15: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)
scala> import collection.immutable.SortedSet
import collection.immutable.SortedSet
scala> SortedSet (1, 2, 3) ++ SortedSet(3, 5, 4)
res18: scala.collection.immutable.SortedSet [Int] = TreeSet(1, 2, 3, 4, 5)

¶4₉2〖Working with Map and Tuple〗P117

Maps 是键值对迭代的，键值对由scala.Tuple2表示，即两个元素的管道。和其他集合不一样，管道是异构的集合，因此你可以存储各种各样的元素类型。

scala> val m = Map((1, "1st"), (2, "2nd"))
m: scala.collection.immutable.Map[Int,java.lang.String] =
Map(1 -> 1st, 2 -> 2nd)

一个可选的写法是使用 key->value 表达式表示:

scala> val m = Map(1 -> "1st", 2 -> "2nd")
m: scala.collection.immutable.Map[Int,java.lang.String] =
Map(1 -> 1st, 2 -> 2nd)

Map的大多数操作和Set相似。不同的是，在Map中，apply方法用于返回一个key的value，并且如果对应的value不存在，它将抛出一个异常。下面是使用apply方法的例子:

scala> m(1)
res20: java.lang.String = 1st
scala> m(3)
java.util.NoSuchElementException: key not found: 3
at scala.collection.MapLike$class.default(MapLike.scala:226)
at scala.collection.immutable.Map$Map2.default(Map.scala:88)

最好的key-value关联获取方法是使用 get 方法，它定义在Map中。为了代替返回值，它将返回的value封装在Option容器中:

def get(kye: A): Option[B]

Option和我们之前创建的Maybe结构相似，但Scala中的Option提供了比Maybe更多的特性。你可以把Option认为是只有一个元素的List。当Map中存在元素的时候，它返回Some；否则它返回None。下面例子使用get来检索key的value:

scala> m.get(1)
res22: Option[java.lang.String] = Some(1st)
scala> m.get(3)
res23: Option[java.lang.String] = None

你可以使用get方法来提取Option中的元素，或使用getOrElse检索Option中的值。若要获得Map中的所有key和value，你可以使用m.keys和m.values来获取，两者都返回Iterator。Scala的Map也定义了filter，该方法接受一个断言，当断言为true时，返回一个Map的所有键值。下面代码片段，你要过滤掉所有rock artists。

scala> val artists = Map(
"Pink Floyd" -> "Rock", "Led Zeppelin" -> "Rock",
"Michael Jackson" -> "Pop", "Above & Beyond" -> "Trance")
artists: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
Map(Pink Floyd -> Rock, Led Zeppelin -> Rock, Michael Jackson -> Pop,
Above & Beyond -> Trance)
scala> artists filter { (t) => t._2 == "Rock" }
res26: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
Map(Pink Floyd -> Rock, Led Zeppelin -> Rock)

下面列出一些定义在可变和不可变的Map中的方法

       方法              |            描述

---------------------------- | :----------------------------------------------------------
ms getOrElse (k, d) | 获取 ms 中 键 k 的值，不存在则默认为 d
ms + (k -> v) | 包含 ms 所有映射和 k->v 映射的Map
ms ++ kvs | 包含 ms 所有映射和 kvs 所有键值对
ms filterKeys p | ms 中的 key 满足断言 p的映射
ms mapValues f | 对 ms 中的所有 value 作 f
ms(k) = v, ms.update(k, v) | 对 ms 中的键 k 作更新操作，k 对应的 value 被覆盖
ms getOrElseUpdate(k, d) | 如果 k 在 ms 中有定义，则返回对应的 value，否则添加 k->d 并返回d
ms.clear() | 删除ms中的所有映射

在Map中的filter方法的调用是通过将key-value键值对作为scala.Tuple2实例传递的。Tuple2在Scala中定义了_1和_2两个方法，它用于接收Tuple的第一个和第二个元素。如你可以使用for-comprehension过滤掉所有的rock artists:

scala> for(t <- artists; if(t._2 == "Rock")) yield t
res31: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
Map(Pink Floyd -> Rock, Led Zeppelin -> Rock)

for-comprehension和map方法、filter、foreach方法十分相似。下一小节你将看到for-comprehension在Scala中是如何转换的。

¶4₉3〖Under the hood of for-comprehension〗P118

前面我们学习了for-comprehension的使用方法，但是我们实际上不知道for-comprehension转换时发生了什么，以及如何使用模式匹配与filter、map、faltMap和foreach方法联合起来。学习这些知识后，他会帮助你理解如何联合一些简单的函数来做一些强大的事情。当然，最好的方法是看看底层到底发生了什么。
这里我们创建一个case class来表示艺术家并使用for-comprehension来创建一个摇滚artists的list。下面是代码片段:

case class Artist(name: String, genre: String)
val artists = List(Artist("Pink Floyd", "Rock"),
Artist("Led Zeppelin", "Rock"),
Artist("Michael Jackson", "Pop"),
Artist("Above & Beyond", "trance")
)
for(Artist(name, genre) <- artists; if(genre == "Rock"))
yield name

¶Why use withFilter but not filter?

我i什么要用withFilter而不用filter？答案在于filter的处理是否要求严格还是不严格。filter方法只有在这些元素满足断言/条件的情况下，而不严格的处理则表示计数只在需要的基础上。从Scala 2.8开始，for-comprehension是不严格的。例如:

val list = List(1, 2, 3)
var go = true
val x = for(i <- list; if(go)) yield {
go = false
i
}
println(x)

你期望输出List(1)，但是如果在2.7版本上执行，实际上则输出List(1,2,3)。原因是在2.8之前，for-comprehensions会被如下转换实现:

val y = list filter {
case i => go
} map {
case i => {
go = false
i
}
}
println(y)

可以看到，go为false时根本不会对流程产生影响，因此，从Scala2.8开始使用withFilter修正这个问题，当withFilter被使用时，断言/条件将在元素每次被内部访问时执行。

如果在for-comprehension中有多个计数器，事情将变得有点复杂和有趣了。我们以artist为例，假如你喜欢存储一些艺术家的照片，并且你只喜欢rock artist艺术家的照片。那我们应该如何过滤掉rock albums呢？

case class Artist(name:String,genre:String)
case class ArtistWithAlbums(artist: Artist, albums: List[String])

val artistsWithAlbums = List(
  ArtistWithAlbums(Artist("Pink Floyd", "Rock"),
    List("Dark side of the moon", "Wall")),
  ArtistWithAlbums(Artist("Led Zeppelin", "Rock"),
    List("Led Zeppelin IV", "Presence")),
  ArtistWithAlbums(Artist("Michael Jackson", "Pop"),
    List("Bad", "Thriller")),
  ArtistWithAlbums(Artist("Above & Beyond", "trance"),
    List("Tri-State", "Sirens of the Sea")
  )
)

for {
  ArtistWithAlbums(artist, albums) <- artistsWithAlbums
  album <- albums
  if artist.genre == "Rock"
} yield album

实际上，在Scala中，当包含多个计数器的情况，Scala会使用flatMap而不是map，因此，上述代码实际上被转换为:

artistsWithAlbums flatMap {
case ArtistWithAlbums(artist, albums) => albums withFilter {
album => artist.genre == "Rock"
} map { case album => album }
}

这里使用flatMap的原因是你必须匹配map外层的每个计数器。使用faltMap获得List(Dark side of the moon,Wall,Led Zeppelin IV,Presence)返回，使用map则获得List(List(Dark side of the moon,Wall),List(Led Zeppelin IV,Presence),List(),List())返回。

¶4₉4〖Use Option not Null〗P121

如果你用过Java或Ruby之类的语言，你一定对使用null或nil(Ruby)的痛楚深有感触。在Ruby中还好一些，因为Nil在Ruby中是一个单例对象，这样你可以调用Nil中的方法。但是在Java中，如果一个变量引用是null，会抛出一个NullPoionterException。为了避免这个问题，许多编程开发者混杂了一些带有null checks的基础代码，使得代码难于阅读。
Scala使用了一个不同的方式解决这个问题，这就是Option(参考: http://mng.bz/AsUQ 中的 Option Pattern)。Option中实现了Null Object 模式。Option同时也是一个Monad。至于什么是Monad，会在下一章介绍，现在我们可以把一个Monad认为是一个简单的容器。在Scala中，Option是一个抽象类，它定义了两个子类，Some和None。常常你会遇到一个方法需要返回一个value或什么都不返回的情况。典型地，在Java或者Ruby中你会用null或nil。但是在Scala，Option是被推荐的做法，它会在一个函数中返回一个Some或者None的一个实例。在Scala中map的get方法正是这样实现的。当给定的key存在是，它返回Some封装的值，当key不存在时，则返回None。

val artists = Map("Pink Floyd" -> "Rock", "Led Zeppelin" -> "Rock", "Michael
Jackson" -> "Pop", "Above & Beyond" -> "Trance")
artists: scala.collection.immutable.Map[java.lang.String,java.lang.String] =
Map(Pink Floyd -> Rock, Led Zeppelin -> Rock, Michael Jackson -> Pop,
Above & Beyond -> Trance)
scala> artists.get("Pink Floyd")
res33: Option[java.lang.String] = Some(Rock)
scala> artists.get("Abba")
res34: Option[java.lang.String] = None

你可以在Scala中使用Option来做模式匹配，Option也定义了map、filter、flatMap之类的方法，这样在一个for-comprehension中更容易使用。

¶When should you use Either rather than Option?

scala.Either表示一个两种可能意义的结果，和Option不同，它返回一个单独的有意义的结果或者Nothing。Either提供了两个子类：Left 和 Right。按照惯例，Left表示失败，Right类似于Some。例如，下面代码中要做一些socket连接，我们知道，服务器可以访问则返回一个连接信息否则就是连接失败。我们将这些操作封装在一个叫做throwableToLeft的函数中：

def throwableToLeft[T](block: => T):Either[Throwable, T] =
try {
Right(block)
} catch {
case ex Throwable => Left(ex)
}

当创建一个新的Socket连接时

scala> val r = throwableToLeft {
new java.net.Socket("localhost", 4444)
}
scala> r match {
case Left(e) => e.printStackTrace
case Right(e) => println(e)
}

当一个异常发生时，创建一个Left otherwise Right的实例。大多数开发者会用抛出异常处理，使用Either可能会更加适用。尤其是，在本程序中，抛出一个异常并不是一个好想法，使用Either来接收和发送，在进程和线程处理上则是一个好的方法。

¶4~10〖Working with lazy collections: views and streams〗P122

lazy collections也称为nonstrict collections，它的对立就是——strict collections。strict collections意味着元素会被立即执行。下面例子中向List中每个元素加1操作，但只返回head:

scala> List(1, 2, 3, 4, 5).map( _ + 1).head
res43: Int = 2

这段代码的问题是，我们只需要map中输出结果的head，但实际上从1到5的元素都被处理了。为了更清晰说明，我们将上述代码分开说明:

scala> val newList = List(1, 2, 3, 4, 5).map( _ + 1)
newList: List[Int] = List(2, 3, 4, 5, 6)
scala> newList.head
res44: Int = 2

虽然这不是什么大的问题，但有时为了节省内存空间和时间，不希望集合中的一些不需要的元素被创建。因此，Scala中提供了两个方式:View 和 Stream。下面先从views开始。

¶4₁₀1〖Convert a strict collection to a nonstrict collection with views〗P123

请求式集合(on-demand collections)中出现最多的技术术语是 nonstrict collections。有时也被称为lazy collections，但是lazy通常指的是nonstrict 函数的缓存结果.

TIP: 在Scala 2.8之前，Views被称为Projections。因此在迁移问题上要将Projections改为Views。

几乎所有的集合都暴露了一个称为 view 的方法，该方法将返回一个非严格视图。为了处理前面的List例子问题，你可以这样做:

scala> List(1, 2, 3, 4, 5).view.map( _ + 1).head
res46: Int = 2

在这里，map方法的调用会产生另外一个视图而不会对计数器进行计算，计数器会延迟直到调用head方法时才执行。另外一个有趣的方式是你可以通过惰性求值来避免一些错误问题。例如下面例子中，对List中的所有元素进行 2 / _操作，但是其中有一个元素会出现除数为0的错误:

scala> def strictProcessing = List(-2, -1, 0, 1, 2) map { 2 / _ }
strictProcessing: List[Int]
scala> strictProcessing(0)
java.lang.ArithmeticException: / by zero
at $anonfun$strictProcessing$1.apply(<console>:6)

但是我只关心集合中的第一个元素，整个集合被处理将由第三个元素因此异常。如果是View，则可以避免这类异常问题:

scala> def nonStrictProcessing = List(-2, -1, 0, 1, 2).view map { 2 / _ }
nonStrictProcessing: scala.collection.SeqView[Int,Seq[_]]
scala> nonStrictProcessing(0)
res50: Int = -1

你可以忽略这类错误并处理其他元素，但是这是你如果访问这个错误元素，你会获得一个异常:

scala> nonStrictProcessing(3)
res52: Int = 2
scala> nonStrictProcessing(2)
java.lang.ArithmeticException: / by zero
at $anonfun$nonStrictProcessing$1.apply(<console>:6)

为了在一个视图view中强制strict处理，你可以在此调用force方法，该方法和严格版本一样，会抛出ArithmeticException异常:

scala> nonStrictProcessing.force
java.lang.ArithmeticException: / by zero
...

集合元素的非严格方法处理是一个有用的和方便的提高性能的方式，特别是当一个操作是耗时的情况下。在诸如Haskell、Clean等的惰性函数语言中，几乎每个构造器都是延迟执行的。但是因为Scala不是一个惰性函数式编程语言(lazy functional programming language)，你必须通过使用 名传递函数(call-by-name functions) 或 偏函数(partial functions) 这种额外的步骤来模拟惰性的等效类型。一个例子将阐述这个编程思想。如下面代码片段有一个叫做 tweets 的耗时操作，该方法会处理从Twitter中获得的信息:

import scala.io._
import scala.xml.XML
def tweets(handle: String) = {
println("processing tweets for " + handle)
val source = Source.fromURL(new
java.net.URL("http://search.twitter.com/search.atom?q=" + handle))
val iterator = source.getLines()
val builder = new StringBuilder
for(line <- iterator) builder.append(line)
XML.loadString(builder.toString)
}

使用Source来获取Twitter的XML结果并创建一个XML节点实例。尽管它不会花费太多的时间，假设我们考虑这个操作是耗时和高消耗的。现在你需要为多个用户处理这些Twitter搜索的结果。最明显的解决办法是创建一个Map来存储:

scala> val allTweets = Map("nraychaudhuri" -> tweets("nraychaudhuri"),
"ManningBooks" -> tweets("ManningBooks"),
"bubbl_scala" -> tweets("bubbl_scala")
)
processing tweets for nraychaudhuri
processing tweets for ManningBooks
processing tweets for bubbl_scala

问题是当创建一个Map时，你实际上为所有的users调用了tweets函数。但因为tweets函数是耗时的，你只希望在一个user真正需要时才调用。所以一个可选的处理方法就是使用偏函数，如下讨论:

scala> val allTweets = Map(
"nraychaudhuri" -> tweets _ , "ManningBooks" -> tweets _,
"bubbl_scala" -> tweets _)
allTweets: scala.collection.immutable.Map[java.lang.String,(String) =>
scala.xml.Elem] = Map(nraychaudhuri -> <function1>, ManningBooks ->
<function1>, bubbl_scala -> <function1>)

这里，你使用了一个偏函数来创建一个map。偏函数(partial function)就是指一个不指定所有参数的函数。例如，当你带一个参数调用tweets时，你会获得返回信息；但是如果你省略参数，你将获得获得一个方法返回:

scala> tweets("ManningBooks")
processing tweets for ManningBooks
scala> tweets _
res73: (String) => scala.xml.Elem = <function1>

在Scala中，省略的参数必须指定为 _；否则会报错:

scala> tweets
<console>:19: error: missing arguments for method tweets in object $iw;
follow this method with '_' if you want to treat it as a partially applied
function
tweets

在这个例子中，如果你使用view，你便可以实现你所需要的惰性功能，你的tweets函数将在需要时调用:

scala> allTweets.view.map{ t => t._2(t._1)}.head
processing tweets for nraychaudhuri

在一个Map内部，values被存储为Tuple2，一个管道包含 _1 句柄和_2 值两部分，而值在这里它是一个偏函数。你通过传递name句柄调用tweets函数。如果你想执行Manning Books的信息，你可以使用一个for-comprehension:

for(t <- allTweets; if(t._1 == "ManningBooks")) t._2(t._1)

注意：从Scala2.8开始，for-comprehensions是非严格的for标准操作。

¶4₁₀2〖Working with Streams〗P126

Stream实现了lazy list的功能(Tuple2则实现了lazy Map)，Stream使得元素会在他们真正需要的时候被执行。Stream和list一样，他们的元素被存储为两部分，head和tail，Stream的尾(tail)不会被计算直到它被需要的时候。如果你想，你可以通过Stream建立一个无限大的list，它会消耗掉很大的内存容量。因为Stream继承自LinearSeq，你可以有List中的大部分方法实现。如下面例子使用List的下标来压缩每一个元素:

scala> List("zero", "one", "two", "three", "four",
"five").zip(Stream.from(0))
res88: List[(java.lang.String, Int)] = List((zero,0), (one,1), (two,2),
(three,3), (four,4), (five,5))

这里定义在Stream中的from方法会创建一个从0开始，步长为1递增的无限大的Stream。在Stream中也可以使用view视图技术来提高内存损耗和性能处理的能力。我们以Fibonacci序列为例。在数学中，费波纳茨数为如下序列格式:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
定义规定，前两个数为0和1，后一个数为前两个数之和。实现Fibonacci的最一般做法是使用递归；

def fib(n: Int): Int = n match {
    case 0 => 0
    case 1 => 1
    case n => fib(n - 1) + fib(n - 2)
}

这个函数会返回n个Fibonacci的值。你要n是一个大于20的数时，才看到这个实现上有效率问题。实际上当执行到8时，它的执行过程为:
fib(8)
fib(7) + fib(6)
(fib(6) + fib(5)) + (fib(5) + fib(4))
((fib(5) + fib(4)) + (fib(4) + fib(3)) + ((fib(4) + fib(3)) + (fib(3) +
fib(2))
…
你可以看到，这个计数以指数增长，而又有许多步骤被重复计算。一个实现Fibonacci序列的方式就是通过它建立无穷大的(infinite) Stream。如果你将Fibonacci序列从0(0,1,2,3…)作为tail压缩，你将获得一个序列对(tuples)😦(0, 1), (1, 2), (2, 3)…)。你再用map的sum方法计算两个pair的值，你将获得一个Fibonacci序列数。为了实现这个功能，使用递归的streams。下面是代码片段:

val fib: Stream[Int] = Stream.cons(0, Stream.cons(1,
fib.zip(fib.tail).map(t => t._1 + t._2)))

这里使用了Stream中的cons对象，并使用了cons对象的apply方法，它将0作为head，而另外一个Stream作为tail。现在，你比较一下这两个方法的时间，可以看到基于stream的解决方案比前一个更好。
这里遗留的问题是，tail在被需要时执行，而不是马上执行，那么Stream是如何管理的？答案是名调用(call-by-name)参数。近距离看一下cons对象中声明的apply方法，该方法显示第二个参数被声明为一个函数，该函数被接收参数并返回一个stream。

def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl)

所以，这里的它就是一个名调用参数，它被传入的无参函数编码。注意，当模式匹配一个Stream时，常用的cons(::)不会生效；你必须使用#::。

¶4~11〖Divide and conquer with parallel collections〗P127

到目前为止，你已经看了集合的eager、lazy执行类型，并且集合中的元素是顺序执行的。现在来学习一下Scala的并行集合，它的元素被平行执行。
Scala的并行集合实现了分离(split)和组合(combine)操作的功能，即分治算法。分离操作将并行集合分割成小块的Iterable集合，直到它达到给定的临界点(threshold)。之后一系列的任务被创建来同时处理这些小块的Iterable集合。这些任务(tasks)实现了Fork/Join框架。Fork/Join框架会计算出CPU的可用核数，并用来处理这些操作以及使用线程来执行这些任务。最后，每个任务得到的结果组合(combines)成为最终结果。
如下图，ParVector(10,20,30,40,50,60,70,80,90)被分割成小块的Iterable，每个Iterable集合继承scala.collection.parallel.Splitter特质。为每个并行集合定义的阈值提供了集合元素最小分离个数的计算。一旦分离操作完成，每个集合被线程任务处理操作。例如，TaskA带有10，20作为输入并通过map匿名处理后输出5，10。最后，每个任务的输出再组合成为最终结果。每一个并行集合提供了一个combiner，它知道如何将小块的处理的集合进行组合并输出结果。为了得知有多少个工作被处理，你可以在REPL中尝试一下代码片段:

scala> import scala.collection.parallel.immutable._
import scala.collection.parallel.immutable._
scala> ParVector(10, 20, 30, 40, 50, 60, 70, 80, 90).map {x =>
println(Thread.currentThread.getName); x / 2 }
ForkJoinPool-1-worker-2
ForkJoinPool-1-worker-2
ForkJoinPool-1-worker-3
ForkJoinPool-1-worker-3
ForkJoinPool-1-worker-3
ForkJoinPool-1-worker-3
ForkJoinPool-1-worker-1
ForkJoinPool-1-worker-0
ForkJoinPool-1-worker-0
res2: scala.collection.parallel.immutable.ParVector[Int] = ParVector(5, 10,
15, 20, 25, 30, 35, 40, 45)

¶Configuring parallel collections

负责调度并行集合的引擎称为 TaskSupport。每个并行集合配置了一个任务支持对象，负责跟踪线程池、负载平衡和任务调度。
Scala提供了下面几个任务支持的实现:
"ForkJoinTaskSupport——JVM1.6中使用的fork-join线程池。
"ThreadPoolTaskSupport——稍微比ForkJoinTaskSupport高效；使用常规线程池执行。
"ExecutionContextTaskSupport——Scala所有并行集合中的默认任务支持。它在scala.concurrent包中，后台使用fork-join线程池实现。
若要改变给定集合的TaskSupport，可以如下简单处理:

import scala.collection.parallel._
val pv = immutable.ParVector(1, 2, 3)
pv.tasksupport = new ForkJoinTaskSupport(new
scala.concurrent.forkjoin.ForkJoinPool(4))

这里tasksupport变为了一个4线程的ForkJoinTask任务。

并行集合适用于处理数据并行问题，提高负载操作的性能而不用担心并发性。map 操作就是一个最好的例子，因为它不依赖于集合元素的顺序处理。Scala中并行集合不确保任何顺序执行。另外，foldLeft不适用于并行集合，因为集合中的元素要求在一个正确的顺序上被处理。下面例子演示foldLeft被执行时是单线程的，即使在ParVector上执行:

scala> ParVector(10, 20, 30, 40, 50, 60, 70, 80, 90).foldLeft(0) {(a,x) =>
println(Thread.currentThread.getName); a + x }
Thread-14
Thread-14
Thread-14
Thread-14
Thread-14
Thread-14
Thread-14
Thread-14
Thread-14
res3: Int = 450

¶4₁₁1〖Parallel collection hierarchy〗P129

Scala2.9后，并行集合被添加到了集合库中。所有并行集合类实现了如下单独的层次结构。在最顶部的并行集合库是ParIterable。它实现了所有并行集合的通用行为。

Scala并行集合库实现的集合类型大部分在scala.collection包，包括mutable和immutable类型。之所以说大部分是因为你找不到LinearSeq类型集合对应的List实现，因为它们不适用于并行处理。
要使用这些集合类型，你需要导入scala.collection.parallel.immutable或scala.collection.parallel.mutable包:

scala> import scala.collection.parallel.mutable._
import scala.collection.parallel.mutable._
scala> ParArray(1, 2, 3, 4).sum
res4: Int = 10

你不总是要以并行集合来实现并行处理；如有需要，你可以非常容易地在顺序集合和并行集合之间进行转换。

¶Why there are Gen* classes in the scala.collection package

顺序集合和并行集合库中都实现了Gen*类中的操作。因此，如果你不关心接收的是并行集合还是有序集合，你应该使用带前缀的Gen: Gentraversable，GenIterable，GenSeq，这样，它既是并行的，又是顺序的。

¶4₁₁2〖Switching between sequential and parallel collections〗P130

Scala集合为所有有序集合类型提供了par方法来创建一个并行版本的集合。另一方面，所有并行集合类型实现了seq方法来创建有序版本的集合。下面例子通过转换顺序Vector为并行ParVector来过滤所有偶数。

val vs = Vector.range(1, 100000)
vs.par.filter(_ % 2 == 0)

这里将输出一个ParVector实例的偶数。若要回到Vector，需要调用seq方法。如下

Vector.range(1, 100000).par.filter(_ % 2 == 0).seq

这种转换的一个附加好处是，你可以使用并行集合优化剩余基础代码而不用改变原来代码中的集合类型。

但是，并行集合并不是一个最好的药方。你不希望所有操作都要通过并行集合的转换来进行处理。实际上，在有些情况它可能表现得比有序集合更差。因此，在转换为并行集合前要考虑两点：

1. 类型的操作
2. 转换的开销
   首先，不是所有操作是可并行的，因此这些操作转换为并行集合并不会提高性能。一个理想候选是不产生任何顺序执行、没有任何副作用。诸如map、flatMap、filter和forall这些易于并行化的操作就是一个好的方法例子。
   第二，使用Fork/Join框架来创建并行到顺序集合的转换会有一定的开销。如果处理一个操作比创建一个并行集合花费更小的时间，那么使用并行版本会减少你的性能。另外它也可能由你所使用的集合类型有关。转换Seq为ParSeq比转换List为Vector要快很多，因为没有对List的并行实现，正因为如此，你在List调用par方法时会返回ParVector。

¶4~12〖Summary〗P131

在本章你已经学习了一些重要的概念。类型参数化帮助我们探索类型协变性概念以及Scala类型安全机制。理解了这些概念对创建泛型、类型暗转、可重用组建是重要的。这章还探索了高级函数的使用，例如map和filter，以及他们是如何在Scala库中使用——另外也给集合库提供了丰富的、有用的API。使用这些告诫函数，你可以很容易地封装常用的编程惯用代码。
这章还介绍了Scala集合库以及Scala2.8新创建的API。Scala集合库是一个大的API，目前我们值看到了最重要和最常用的几个。你需要从scala文档中探索更多集合类型类型和API的使用，因为几乎所有的通用的、有用的函数都已经写入到库中。
在使用集合的同时，对于理解一个集合类型的性能和内存要求是非常重要的。知道严格(strict)和非严格(nonstrict)的区别会帮助我们决定哪种集合类型更适用、什么时候更适用。
下一章开始探索函数式编程。你会学习什么是函数式编程，函数式编程在Scala中如何操作。理解函数式编程有助于我们创建函数式的、不可变的以及简单的解决方案。