Chapter 25《The Architecture of Scala Collections》

不同的集合支持实现支持相同的操作，如果在每个集合里面进行单独的实现，会出现大量的代码并且不利于保持集合操作的一致性。新的集合框架主要设计目标就是避免重复，在尽量少的地方定义，并在集合模板中实现大多数操作，由基类和实现灵活继承。

集合构建器

集合的大部分操作都可以通过遍历或者构建器，Traversable的foreach方法来实现集合的遍历，通过Builder的实例来构建新的集合。Builder类中主要的方法如下所示：

class Builder[-Elem, +To] {
def +=(elem: Elem): this.type
def result(): To
def clear()
def mapResult[NewTo](f: To => NewTo): Builder[Elem, NewTo] =
 ...
}

Elem是集合中元素的类型，To是生成的集合的类型。使用result()可以从builder中获取到一个集合，之后builder的状态便是未定义的，可以使用clear将builder的状态重新定义到新的空状态。ArrayBuffer本身就是自己的构造器，使用result会交出本身的buffer。

重构共同操作

Scala中的集合遵循同样类型的原则，在集合上执行的转换方法必须返回同样类型的集合，比如在List上执行filter，返回的还是List，在Map上执行转换返回的还是Map。Scala使用所谓的实现特质中的泛型构建器和遍历器来避免代码重复并达成同样类型的目的。这些特质都带有Like后缀，比如说IndexedSeqLike，TraversableLike，Traversable从TraversableLike中继承所有的具体方法。这些特质的集合类型以及集合底层元素的类型都是泛化的，比如List[I]，rait TraversableLike[+Elem, +Repr] { ... }， Elem是底层元素的类型，Repr的类型没有任何限制，它可以被实例化为Traversable之外的类型，比如String或者Array，这些类型可以使用Like特质中的所有操作。
```
trait TraversableLike[+Elem, +Repr] {
def newBuilder: Builder[Elem, Repr] // deferred
def foreach[U](f: Elem => U)
 // deferred
...
def filter(p: Elem => Boolean): Repr = {
val b = newBuilder
foreach { elem => if (p(elem)) b += elem }
b.result
}
}
```
在TraverableLike中定义了两个抽象方法，newBuilder和foreach，用于具体的子类实现。剩下的具体的操作，比如说filter，都是所有的Traversable子类之间的共同操作，在Like中直接实现即可。
map的操作稍微复杂一些，因为List[Int]可以map成为List[String]，但是上述结构明显是不行的，map需要同样的集合构建器，但是是不同的元素类型，但也可能还和入参类型有关，需要不同的集合构建器。比如说BitSet(1,2,3).map(_.toFloat)最后的类型是Set(1.0,2.0,3.0)，因为BitSet中不能使用Float类型。map函数产生的集合类型跟传入的函数有关，还有另外的操作也会出现类似的情况：
```
scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => (y, x) }
res3: scala.collection.immutable.Map[Int,java.lang.String] =
Map(1 -> a, 2 -> b)
scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => y }
res4: scala.collection.immutable.Iterable[Int] =
List(1, 2)
```

scala解决这个问题的方式是使用重载，不是Java中的重载形式，依然不够灵活，使用的是带有隐式参数的重载，

def map[B, That](f: Elem => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
val b = bf(this)
for (x <- this) b += f(x)
b.result
}

CanBuildFrom特质可以生成新的集合构建器，From是旧的集合类型，Elem是新的元素类型，To是新的集合类型。

trait CanBuildFrom[-From, -Elem, +To] {
// Creates a new builder
def apply(from: From): Builder[Elem, To]
}

在每一个集合的伴生对象中都定义了隐式的CanBuildFrom对象用于构建新的集合。隐式转换对map这样的操作提供了正确的静态类型信息，但是运行时的类型信息呢，比如说：

scala> val xs: Iterable[Int] = List(1, 2, 3)
xs: Iterable[Int] = List(1, 2, 3)
scala> val ys = xs map (x => x * x)
ys: Iterable[Int] = List(1, 4, 9)

ys的类型也是List类型，这是通过另外的机制实现的。 CanBuildFrom的apply方法接收一个collection作为入参，可生成泛型遍历器的许多构建器工厂(事实上除了叶子类的构建器工厂)都会将这个apply请求转发至collection的genericBuilder方法。这个方法进而调用该集合定义时的集合构建器，Scala使用静态的隐式解析来解决map的类型问题，使用虚拟分发来选择与这些类型最匹配的运行时类型。

集成新的序列

RNA是A,T,G,U(继承自Base)的序列组合，可以看做是继承IndexedSeq的子类，如果继承IndexedSeq类，则在IndexedSeq中实现的集合类型全部是IndexedSeq，也就是说RNA(A, T, G, U)调用take(1)方法产生的是IndexedSeq的默认实现是Vector(A)，如果要产生RNA(1)，则需要对take进行覆写，这样一来，RNA需要重写IndexedSeq中的所有方法，比如drop，takeWhile等。另外一种实现的方法是RNA继承IndexedSeqLike[Base, RNA]类，可以进一步的来指定输出的集合类型。要达到这个目的需要重新定义IndexedSeqLike中的集合构建器：
```
final class RNA2 private (val groups: Array[Int], val length: Int) extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA2] {
import RNA2._
override def newBuilder: Builder[Base, RNA2] = new ArrayBuffer[Base] mapResult fromSeq
def apply(idx: Int): Base = // as before
}
```

另外还有一类是map函数以及++，使用map函数目前返回的是Vector而不是RNA，

def map[B, That](f: Elem => B)(implicit cbf: CanBuildFrom[Repr, B, That]): That

Elem是目前集合的元素类型，B是map函数的返回类型，That是生成的集合类型。That的类型是由隐式参数cbf确定的，所以接下来就是在RNA2的伴生对象中添加一个隐式对象即可。伴生对象canBuildFrom[RNA, Base, RNA]，不能放在RNA类中，需要放在RNA的伴生对象中。

集成新的集和映射

继承Like类型是为了在对集合或映射进行转换操作之后还能得到较为精确的类型。

集成集合到框架的步骤：

1. 选择集合是可变的还是不可变的；
1. 继承合适的基本接口和Like实现接口来获取大部分的集合操作，定义Builder来为转换操作提供最优类型；
1. 定义canBuildFrom隐式对象来为map等操作提供最优类型。