Question

1. 很多不同的集合实现都支持相同的操作。如果对于每种集合类型我们都重新实现这些方法，将产生大量重复的代码，其中大部分代码都是从其他地方拷贝过来的。

   随着时间推进，某些集合类库中某个部分添加了新的操作、或者修改了原有操作，这将导致这些代码和其他地方拷贝的代码出现不一致。

   为解决该问题，scala 设计了集合框架，其目标是尽可能避免重复，在尽量少的地方定义每个操作。设计思路是：在集合 “模板” 中实现大多数操作，并由各个基类和实现implementation 灵活地继承。

7.1. 集合构建器

1. 几乎所有的集合操作都是用遍历器 traversal 和构建器 builder 来实现的。

   • Traversal 的 foreach 方法解决了遍历的部分。
   • Builder 类的实例解决了构建集合的部分。

   下面给出了 Builer 类的一个简化版的示例：

   
   xxxxxxxxxx
   package scala.collection.generic
   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 是返回的集合类型。

   可以用 b += x 向构建器 b 添加元素 x ；也可以一次性添加多个元素，如 b += (x, y) 以及 b ++ xs 。

   result() 方法从构建器中返回一个集合。在获取result 之后，构建器的状态是未定义的，可以调用 clear() 方法将它重设为新的空状态。

2. 通常，一个构建器可以引用另一个构建器来组装某个集合的元素，不过需要对另外这个构建器的结果进行变换（比如给它一个不同的类型），因此可以通过Builer 的 mapResult 方法来简化。

   例如，ArrayBuffer 本身就是一个构建器，因此对它调用 result 方法会返回本身。如果希望用 ArrayBuffer 来创建一个数组的构建器，则可以用 mapResult：

   
   xxxxxxxxxx
   val buf = new ArrayBuffer[Int]
   val bldr = buf mapResult(_.toArray) // builder 为一个 Builder[Int, Array[Int]]

7.2 抽取公共操作

1. scala 集合遵循“相同结果类型”的原则：只要有可能，对集合的变换操作将交出相同类型的集合。如：filter 操作应用于 List 将返回 List 类型，应用于 Map 将返回 Map 类型。

2. scala 集合类库是通过使用所谓的实现特质 implementation traits 中的泛型构建器和遍历器来避免代码重复、并达成“相同结果类型” 原则的。这些特质的命名中都带有 Like 后缀。例如 IndexedSeqLike 是 IndexedSeq 的实现特质， TraversableLike 是 Traversable 的实现特质。诸如 Traversable 或 IndexedSeq 这样的集合类的具体方法的实现，都是从这些特质中继承下来的。

3. 实现特质不同于一般的集合，它们有两个类型参数：它们不仅在集合元素的类型上是参数化的，它们在集合的表示类型(representation type ，也就是底层的集合，比如 Traversable 类型默认的底层集合为 List ) 上也是参数化的。

   例如，TraversableLike 特质为：

   
   xxxxxxxxxx
   trait TraversableLike[+Elem, +Repr] {...}

   类型参数 Elem 表示集合的元素类型，类型参数 Repr 为集合的表示类型。

   对于 Repr 并没有什么限制，它可以被实例化为不是 TraversableLike 的子类，例如 String 或者 Array 也可以作为 Repr 的类型实例化。

4. 我们以 filter 为例，这个操作定义在 TraversableLike 特质中，只定义了一次，但是对所有集合类都可用。

   ​x
   package scala.collection
   ​
   trait TraversableLike[+Elem, +Repr]{
     def newBuiler: Builer[Elem, Repr]  // 延迟实现
     def foreach[U](f: Elem => U)       // 延迟实现
     ...
     def filter(p: Elem => Boolean): Repr = {
       val b = newBuiler
       foreach{ elem => if(p(elem)) b += elem}
       b.result
     }
   }

   该特质声明了两个抽象方法：newBuiler 和 foreach ，这些方法在具体的集合类中实现。

   filter 操作对于所有使用这些方法的集合的实现方式都是一致的。

   • 它首先使用 newBuiler 构造出一个新的、表示类型为 Repr 的构建器。
   • 然后使用 foreach 遍历当前集合中的所有元素，如果元素满足给定的前提条件，则将该元素添加到构建器中。
   • 最后，构建器收集到的元素通过构建器的 result 方法，以 Repr 集合类型的实例返回。

5. 集合的 map 操作要更复杂一些，因为 map 操作的返回类型不一定是原始的集合类型。

   举个例子：

   
   xxxxxxxxxx
   import collection.immutable.BitSet
   val bits = BitSet(1,2,3)
   bits map (_ * 2)     // 结果是一个 BitSet
   bits map (_.toFloat) // 结果是一个 Set[Float]

   可以看到，map 操作的返回类型取决于传入的函数。

   Scala 解决该问题的方法是重载：不是 Java 采用的那种简单的重载（那样不够灵活），而是隐式参数提供的更系统化的重载。下面给出 TraversableLike 的 map 实现：

   
   xxxxxxxxxx
   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
   }

   这里主要区别在于：filter 用的是 TraversableLike 的抽象方法 newBuilder，而 map 用的是一个以额外的隐式参数的形式传入的、类型为 CanBuildFrom 的构建器工厂 bf 。

   CanBuildFrom 特质的定义为：

   
   xxxxxxxxxx
   package scala.collection.generic
   trait CanBuildFrom[-From, -Elem, +To]{
     // 创建新的构建器
     def apply(from: From): Builder[Eleem, To]
   }

   该特质代表了构建器工厂，有三个类型参数：Elem 表示要构建的集合的元素类型，To 表示要构建的集合类型（即：目标集合类型），From 表示从哪个集合来构建。

   通过定义正确的构建器工厂的隐式定义，可以按需定制正确的类型行为。

   例如，BitSet 类的伴生对象包含一个类型为 CanBuildFrom[BitSet, Int, BitSet] 的构建器工厂。这意味着当操作一个 BitSet 时，可以构造出另一个 BitSet，只要构建的集合的元素类型为 Int 。

   如果集合类型不是 Int，则退而求其次，采用另一个隐式构建器工厂，一个在 mutable.Set 伴生对象中实现的隐式构建器工厂。这是一个更通用的构建器工厂，定义为（其中 A 为泛型的类型参数）：CanBuildFrom[Set[_]],A, Set[A]] 。这意味着当操作一个以 Set[_] 通配类型表示的任意类型的 Set 时，仍然可以构建出一个 Set，而无论元素类型 A 是什么。

   有了这两个 CanBuildFrom 的隐式实例，就可以依赖 Scala 的隐式解析规则来选取合适的、并且是最具体的那个构建器工厂了。

6. 上述机制对于静态类型的 map 处理较好，但是动态类型的 map 还需要一层额外的处理机制。

   
   xxxxxxxxxx
   val xs: Iterable[Int] = List(1,2,3) // xs 静态类型为 Iterable，动态类型为 List
   val ys = xs.map(x => x*x)  // ys 的静态类型为 Iterable， 动态类型也为 List

   CanBuildFrom 的 apply 方法接受原始集合作为入参传入，大多数构建器工厂都将这个调用转发到原始集合的 genericBuilder 方法，这个 genericBuilder 方法进行调用属于该集合的构建器。

   即：scala 使用静态的隐式解析规则来决定 map 的类型约束，用虚拟分发来选择与这些类型约束相对应的最佳动态类型。

7. Map/Array 都是一种函数，因为它们都继承自 Function1 特质，并且有 apply 方法。如：

   
   xxxxxxxxxx
   val m = Map("a" -> 1, "b" -> 2)
   m("a") // 就像函数调用一样
   val arr = Array("a","b","c")
   arr(0) // 就像函数调用一样

8. 如果想要自定义一个新的集合类库到框架中，需要注意如下几点：

   • 决定该集合是可变的还是不可变的。
   • 选择合适的特质作为集合的基础。
   • 从合适的实现特质继承来实现大多数集合操作。
   • 如果你想让 map 和类似操作返回你的集合类型，你需要在你的类的伴生对象中提供一个隐式的 CanBuildFrom 。