Martin Odersky 和 Lex Spoon
这些页面详细描述了 Scala 集合框架的架构。与 Scala 2.8 集合 API 相比，你将进一步了解框架的内部工作原理。你还会了解此架构如何帮助你用几行代码定义自己的集合，同时重复使用框架中绝大部分的集合功能。
Scala 2.8 集合 API 包含大量集合操作，这些操作在许多不同的集合实现中统一存在。为每种集合类型重新实现每个集合操作将导致大量代码，其中大部分将从其他地方复制。随着时间的推移，当在集合库的一部分中添加或修改操作而不在其他部分中添加或修改操作时，这种代码重复可能会导致不一致。新集合框架的主要设计目标是避免任何重复，尽可能在较少的地方定义每个操作。（理想情况下，所有内容都应该只在一个地方定义，但有一些例外情况需要重新定义。）设计方法是在集合“模板”中实现大多数操作，这些模板可以灵活地从各个基类和实现中继承。以下页面解释了这些模板以及构成框架“构建块”的其他类和特征，以及它们支持的构建原则。
生成器
Builder 特征的概述
package scala.collection.mutable
trait Builder[-Elem, +To] {
def +=(elem: Elem): this.type
def result(): To
def clear(): Unit
def mapResult[NewTo](f: To => NewTo): Builder[Elem, NewTo] = ...
}
几乎所有集合操作都是根据遍历和生成器实现的。遍历由 Traversable 的 foreach 方法处理，而构建新集合由类 Builder 的实例处理。上面的清单展示了此特征的略微简化的概述。
你可以使用 b += x 向构建器 b 添加元素 x。还有语法可以一次添加多个元素，例如 b += (x, y)。使用 b ++= xs 添加另一个集合与缓冲区相同（事实上，缓冲区是构建器的增强版本）。result() 方法从构建器返回一个集合。获取结果后，构建器的状态未定义，但可以使用 clear() 将其重置为新的空状态。构建器在元素类型 Elem 和它们返回的集合类型 To 中都是通用的。
通常，构建器可以引用其他构建器来组装集合的元素，但随后可能希望转换其他构建器的结果，例如为其提供不同的类型。通过 Builder 类中的 mapResult 方法可以简化此任务。例如，假设你有一个数组缓冲区 buf。数组缓冲区是它们自己的构建器，因此获取数组缓冲区的 result() 将返回相同的缓冲区。如果你想使用此缓冲区生成构建数组的构建器，则可以使用 mapResult，如下所示
scala> val buf = new ArrayBuffer[Int]
buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()
scala> val bldr = buf mapResult (_.toArray)
bldr: scala.collection.mutable.Builder[Int,Array[Int]]
= ArrayBuffer()
结果值 bldr 是一个构建器，它使用数组缓冲区 buf 来收集元素。当从 bldr 要求结果时，将计算 buf 的结果，它将产生数组缓冲区 buf 本身。然后使用 _.toArray 将此数组缓冲区映射到一个数组。因此，最终结果是 bldr 是一个数组构建器。
分解常见操作
TraversableLike 特征概述
package scala.collection
trait TraversableLike[+Elem, +Repr] {
def newBuilder: Builder[Elem, Repr] // deferred
def foreach[U](f: Elem => U): Unit // deferred
...
def filter(p: Elem => Boolean): Repr = {
val b = newBuilder
foreach { elem => if (p(elem)) b += elem }
b.result
}
}
集合库重新设计的总体设计目标是同时具有自然类型和最大程度地共享实现代码。特别是，Scala 的集合遵循“相同结果类型”原则：只要有可能，集合上的转换方法将产生相同类型的集合。例如，filter 操作应在每个集合类型上产生相同集合类型的一个实例。对 List 应用 filter 应给出 List；对 Map 应用它应给出 Map，依此类推。在本节的其余部分，你将了解如何实现这一点。
Scala 集合库通过在所谓的实现特征中使用通用构建器和遍历集合来避免代码重复并实现“相同结果类型”原则。这些特征以 Like 后缀命名；例如，IndexedSeqLike 是 IndexedSeq 的实现特征，类似地，TraversableLike 是 Traversable 的实现特征。诸如 Traversable 或 IndexedSeq 之类的集合特征从这些特征继承了它们的所有具体方法实现。实现特征有两个类型参数，而不是普通集合的一个。它们不仅对集合的元素类型进行参数化，还对集合的表示类型进行参数化，即底层集合的类型，例如 Seq[T] 或 List[T]。例如，以下是特征 TraversableLike 的头文件
trait TraversableLike[+Elem, +Repr] { ... }
类型参数 Elem 表示可遍历元素的类型，而类型参数 Repr 表示其表示形式。对 Repr 没有约束。特别是，Repr 可能会实例化为本身不是 Traversable 子类型的类型。这样，集合层次结构之外的类，例如 String 和 Array 仍然可以使用集合实现特征中定义的所有操作。
以 filter 为例，此操作在特征 TraversableLike 中为所有集合类定义一次。相关代码的大纲显示在上面的 特征 TraversableLike 的大纲 中。该特征声明了两个抽象方法 newBuilder 和 foreach，它们在具体集合类中实现。filter 操作使用这些方法以相同的方式为所有集合实现。它首先使用 newBuilder 为表示类型 Repr 构建一个新的构建器。然后，它使用 foreach 遍历当前集合的所有元素。如果元素 x 满足给定的谓词 p（即 p(x) 为 true），则将其添加到构建器中。最后，通过调用构建器的 result 方法，将收集在构建器中的元素作为 Repr 集合类型的实例返回。
集合上的 map 操作稍微复杂一些。例如，如果 f 是从 String 到 Int 的函数，并且 xs 是 List[String]，则 xs map f 应该给出 List[Int]。同样，如果 ys 是 Array[String]，则 ys map f 应该给出 Array[Int]。问题是如何在不重复列表和数组中 map 方法的定义的情况下实现这一点。在 特质 TraversableLike 中所示的 newBuilder/foreach 框架对此并不足够，因为它只允许创建同一集合类型的新实例，而 map 需要同一集合类型构造函数的实例，但可能具有不同的元素类型。
此外，像 map 这样的函数的结果类型构造函数也可能以非平凡的方式依赖于其他参数类型。这是一个例子
scala> import collection.immutable.BitSet
import collection.immutable.BitSet
scala> val bits = BitSet(1, 2, 3)
bits: scala.collection.immutable.BitSet = BitSet(1, 2, 3)
scala> bits map (_ * 2)
res13: scala.collection.immutable.BitSet = BitSet(2, 4, 6)
scala> bits map (_.toFloat)
res14: scala.collection.immutable.Set[Float]
= Set(1.0, 2.0, 3.0)
如果你对位集 map 加倍函数 _ * 2，你会得到另一个位集。但是，如果你对同一位集 map 函数 (_.toFloat)，结果是常规 Set[Float]。当然，它不能是位集，因为位集包含 Int，而不是 Float。
请注意，map 的结果类型取决于传递给它的函数类型。如果该函数参数的结果类型又是 Int，则 map 的结果是 BitSet，但如果函数参数的结果类型是其他内容，则 map 的结果只是 Set。你很快就会发现 Scala 中是如何实现这种类型灵活性。
使用 BitSet 的问题并非孤立情况。以下是与解释器的另外两个交互，它们都将函数 map 到 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)
第一个函数交换键/值对的两个参数。映射此函数的结果仍然是一个映射，但现在朝另一个方向进行。事实上，第一个表达式产生原始映射的逆，前提是它是可逆的。然而，第二个函数将键/值对映射到一个整数，即它的值组件。在这种情况下，我们无法从结果中形成一个 Map，但我们仍然可以形成一个 Iterable，它是 Map 的超特征。
你可能会问，为什么不限制 map，以便它始终能返回同类型的集合？例如，在位集 map 上，只能接受 Int 到 Int 的函数，而在 Map 上，它只能接受成对到成对的函数。不仅从面向对象建模的角度来看，此类限制是不需要的，而且它们是非法的，因为它们会违反里氏替换原则：Map 是 Iterable。因此，对 Iterable 合法的每个操作，对 Map 也必须合法。
相反，Scala 通过重载来解决这个问题：不是 Java 继承的简单形式的重载（不够灵活），而是隐式参数提供的更系统的重载形式。
在 TraversableLike 中实现 map
def map[B, That](f: Elem => B)
(implicit bf: CanBuildFrom[Repr, B, That]): That = {
val b = bf(this)
this.foreach(x => b += f(x))
b.result
}
上面的清单展示了特征 TraversableLike 的 map 实现。它与 特征 TraversableLike 中展示的 filter 实现非常相似。主要区别在于，filter 使用 newBuilder 方法，该方法在 TraversableLike 中是抽象的，而 map 使用一个作为类型为 CanBuildFrom 的附加隐式参数传递的生成器工厂。
CanBuildFrom 特征
package scala.collection.generic
trait CanBuildFrom[-From, -Elem, +To] {
// Creates a new builder
def apply(from: From): Builder[Elem, To]
}
上面的清单展示了表示生成器工厂的特征 CanBuildFrom 的定义。它有三个类型参数：From 指示此生成器工厂适用的类型，Elem 指示要构建的集合的元素类型，To 指示要构建的集合的类型。通过定义生成器工厂的正确隐式定义，您可以根据需要定制正确的类型化行为。以类 BitSet 为例。它的伴随对象将包含类型为 CanBuildFrom[BitSet, Int, BitSet] 的生成器工厂。这意味着当对 BitSet 进行操作时，您可以构造另一个 BitSet，前提是要构建的集合的元素类型为 Int。如果不是这种情况，编译器将检查超类，并回退到 mutable.Set 的伴随对象中定义的隐式生成器工厂。此更通用的生成器工厂的类型（其中 A 是泛型类型参数）为
CanBuildFrom[Set[_], A, Set[A]]
这意味着在对任意 Set（由存在类型 Set[_] 表示）进行操作时，无论元素类型 A 为何，都可以再次构建一个 Set。给定 CanBuildFrom 的这两个隐式实例，然后可以依靠 Scala 的隐式解析规则来选择适当且最具体的实例。
因此，隐式解析为 map 等棘手的集合操作提供了正确的静态类型。但是动态类型呢？具体来说，假设您将某个函数映射到一个 List 值，该值具有 Iterable 作为其静态类型
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 的静态类型是 Iterable，符合预期。但其动态类型是（并且仍然应该是）List！此行为通过一个间接实现。将 CanBuildFrom 中的 apply 方法作为参数传递给源集合。大多数用于泛型遍历的构建器工厂（实际上除了叶类构建器工厂之外的所有构建器工厂）都会将调用转发到集合的 genericBuilder 方法。反过来，genericBuilder 方法调用属于其定义的集合的构建器。因此，Scala 使用静态隐式解析来解析 map 类型上的约束，并使用虚拟分派来选择与这些约束对应的最佳动态类型。
在当前示例中，静态隐式解析将选择 Iterable 的 CanBuildFrom，该 CanBuildFrom 调用 genericBuilder 对作为参数接收的值进行操作。但在运行时，由于虚拟分派，调用的是 List.genericBuilder 而不是 Iterable.genericBuilder，因此 map 构建了一个 List。
集成新集合：RNA 序列
如果您想集成一个新的集合类，以便它可以从所有预定义操作中获益，那么需要做什么？在接下来的几节中，您将了解两个执行此操作的示例，即使用 Patricia 树实现的 RNA 碱基序列和前缀映射。
从第一个示例开始，我们定义四个 RNA 碱基
abstract class Base
case object A extends Base
case object U extends Base
case object G extends Base
case object C extends Base
object Base {
val fromInt: Int => Base = Array(A, U, G, C)
val toInt: Base => Int = Map(A -> 0, U -> 1, G -> 2, C -> 3)
}
假设您想为 RNA 链创建一个新的序列类型，这些链是碱基 A（腺嘌呤）、U（尿嘧啶）、G（鸟嘌呤）和 C（胞嘧啶）的序列。碱基的定义很容易设置，如上所示的 RNA 碱基列表中所示。
每个碱基都被定义为从公共抽象类 Base 继承的 case 对象。 Base 类有一个伴随对象，该对象定义了两个函数，用于在碱基和整数 0 到
- 您可以在示例中看到使用集合来实现这些函数的两种不同方式。
toInt函数被实现为从Base值到整数的Map。反向函数fromInt被实现为一个数组。这利用了映射和数组都是函数这一事实，因为它们继承自Function1特征。
下一个任务是为 RNA 链定义一个类。从概念上讲，RNA 链只是一个 Seq[Base]。但是，RNA 链可能会变得很长，因此在紧凑表示上投入一些工作是有意义的。因为只有四个碱基，所以一个碱基可以用两个位来标识，因此您可以将十六个碱基作为两个位值存储在一个整数中。然后，这个想法是构建 Seq[Base] 的一个专门子类，它使用这种打包表示。
RNA 链类的第一个版本
import collection.IndexedSeqLike
import collection.mutable.{Builder, ArrayBuffer}
import collection.generic.CanBuildFrom
final class RNA1 private (val groups: Array[Int],
val length: Int) extends IndexedSeq[Base] {
import RNA1._
def apply(idx: Int): Base = {
if (idx < 0 || length <= idx)
throw new IndexOutOfBoundsException
Base.fromInt(groups(idx / N) >> (idx % N * S) & M)
}
}
object RNA1 {
// Number of bits necessary to represent group
private val S = 2
// Number of groups that fit in an Int
private val N = 32 / S
// Bitmask to isolate a group
private val M = (1 << S) - 1
def fromSeq(buf: Seq[Base]): RNA1 = {
val groups = new Array[Int]((buf.length + N - 1) / N)
for (i <- 0 until buf.length)
groups(i / N) |= Base.toInt(buf(i)) << (i % N * S)
new RNA1(groups, buf.length)
}
def apply(bases: Base*) = fromSeq(bases)
}
The RNA strands class listing above
presents the first version of this
class. It will be refined later. The class RNA1 has a constructor that
takes an array of Ints as its first argument. This array contains the
packed RNA data, with sixteen bases in each element, except for the
last array element, which might be partially filled. The second
argument, length, specifies the total number of bases on the array
(and in the sequence). Class RNA1 extends IndexedSeq[Base]. Trait
IndexedSeq, which comes from package scala.collection.immutable,
defines two abstract methods, length and apply. These need to be
implemented in concrete subclasses. Class RNA1 implements length
automatically by defining a parametric field of the same name. It
implements the indexing method apply with the code given in class
RNA1. Essentially, apply first
extracts an integer value from the
groups array, then extracts the correct two-bit number from that
integer using right shift (>>) and mask (&). The private constants S,
N, and M come from the RNA1 companion object. S specifies the size of
each packet (i.e., two); N specifies the number of two-bit packets per
integer; and M is a bit mask that isolates the lowest S bits in a
word.
请注意，类 RNA1 的构造函数是 private。这意味着客户端无法通过调用 new 来创建 RNA1 序列，这是有道理的，因为它隐藏了用户对 RNA1 序列的打包数组表示形式。如果客户端看不到 RNA 序列的表示形式详细信息，则可以在将来任何时候更改这些表示形式详细信息，而不会影响客户端代码。换句话说，这种设计实现了 RNA 序列的接口及其实现之间的良好解耦。但是，如果使用 new 构造 RNA 序列是不可能的，那么肯定还有其他方法来创建新的 RNA 序列，否则整个类将毫无用处。事实上，有两种创建 RNA 序列的替代方法，都由 RNA1 伴生对象提供。第一种方法是 fromSeq 方法，它将给定的碱基序列（即类型为 Seq[Base] 的值）转换为 RNA1 类的实例。 fromSeq 方法通过将参数序列中包含的所有碱基打包到一个数组中，然后使用该数组和原始序列的长度作为参数调用 RNA1 的私有构造函数来实现此目的。这利用了这样一个事实：类的私有构造函数在其伴生对象中是可见的。
创建 RNA1 值的第二种方法由 RNA1 对象中的 apply 方法提供。它接受可变数量的 Base 参数，并简单地将它们作为序列转发给 fromSeq。以下是两种创建方案的实际操作
scala> val xs = List(A, G, U, A)
xs: List[Product with Serializable with Base] = List(A, G, U, A)
scala> RNA1.fromSeq(xs)
res1: RNA1 = RNA1(A, G, U, A)
scala> val rna1 = RNA1(A, U, G, G, C)
rna1: RNA1 = RNA1(A, U, G, G, C)
调整 RNA 方法的结果类型
以下是与 RNA1 抽象的更多交互
scala> rna1.length
res2: Int = 5
scala> rna1.last
res3: Base = C
scala> rna1.take(3)
res4: IndexedSeq[Base] = Vector(A, U, G)
前两个结果符合预期，但获取 rna1 的前三个元素的最后一个结果可能不符合预期。事实上，您会看到 IndexedSeq[Base] 作为静态结果类型，而 Vector 作为结果值的动态类型。您可能希望看到 RNA1 值。但这不可能，因为在 类 RNA1 中所做的所有事情都是使 RNA1 扩展 IndexedSeq。另一方面，类 IndexedSeq 有一个 take 方法，它返回一个 IndexedSeq，并且它是根据 IndexedSeq 的默认实现 Vector 实现的。因此，这就是您在上一次交互的最后一行中看到的内容。
既然您已了解事物的本质，那么下一个问题应该是需要做什么才能改变它们？一种方法是覆盖类 RNA1 中的 take 方法，如下所示
def take(count: Int): RNA1 = RNA1.fromSeq(super.take(count))
这将完成 take 的工作。但是 drop、filter 或 init 呢？事实上，序列中有五十多种方法会再次返回序列。为了保持一致性，所有这些方法都必须被覆盖。这看起来越来越不像一个有吸引力的选择。幸运的是，有一种更简单的方法可以达到相同的效果，如下一节所示。
RNA 链类的第二个版本
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
}
RNA 类不仅需要从 IndexedSeq 继承，还需要从其实现特征 IndexedSeqLike 继承。这在类 RNA2 的上述列表中有所体现。新的实现仅在两个方面与之前的实现不同。首先，类 RNA2 现在还扩展了 IndexedSeqLike[Base, RNA2]。其次，它为 RNA 链提供了一个构建器。IndexedSeqLike 特征以可扩展的方式实现了 IndexedSeq 的所有具体方法。例如，take、drop、filter 或 init 等方法的返回类型是传递给类 IndexedSeqLike 的第二个类型参数，即在类 RNA2 中，它是 RNA2 本身。
为了能够做到这一点，IndexedSeqLike 以 newBuilder 抽象为基础，该抽象创建了正确类型的构建器。特征 IndexedSeqLike 的子类必须覆盖 newBuilder 以返回它们自己类型的集合。在类 RNA2 中，newBuilder 方法返回类型为 Builder[Base, RNA2] 的构建器。
要构建此构建器，它首先创建一个 ArrayBuffer，它本身是 Builder[Base, ArrayBuffer]。然后，它通过调用 mapResult 方法将 ArrayBuffer 构建器转换为 RNA2 构建器。 mapResult 方法期望一个从 ArrayBuffer 到 RNA2 的转换函数作为其参数。给定的函数只是 RNA2.fromSeq，它将任意碱基序列转换为 RNA2 值（回想一下，数组缓冲区是一种序列，因此 RNA2.fromSeq 可以应用于它）。
如果您遗漏了 newBuilder 定义，您将收到如下错误消息
RNA2.scala:5: error: overriding method newBuilder in trait
TraversableLike of type => scala.collection.mutable.Builder[Base,RNA2];
method newBuilder in trait GenericTraversableTemplate of type
=> scala.collection.mutable.Builder[Base,IndexedSeq[Base]] has
incompatible type
class RNA2 private (val groups: Array[Int], val length: Int)
^
one error found
错误消息很长且复杂，反映了集合库的复杂组合方式。最好忽略有关方法来源的信息，因为在这种情况下，它带来的弊大于利。剩下的就是需要定义一个结果类型为 Builder[Base, RNA2] 的方法 newBuilder，但找到了一个结果类型为 Builder[Base,IndexedSeq[Base]] 的方法 newBuilder。后者不会覆盖前者。第一个方法（其结果类型为 Builder[Base, RNA2]）是一个抽象方法，在 类 RNA2 中通过将 RNA2 类型参数传递给 IndexedSeqLike 在此类型中实例化。第二个方法（结果类型为 Builder[Base,IndexedSeq[Base]]）是由继承的 IndexedSeq 类提供的。换句话说，如果没有结果类型为第一种类型的 newBuilder 定义，RNA2 类就是无效的。
通过 RNA2 类 的精细实现，take、drop 或 filter 等方法现在按预期工作
scala> val rna2 = RNA2(A, U, G, G, C)
rna2: RNA2 = RNA2(A, U, G, G, C)
scala> rna2 take 3
res5: RNA2 = RNA2(A, U, G)
scala> rna2 filter (U !=)
res6: RNA2 = RNA2(A, G, G, C)
处理 map 及相关方法
然而，集合中还有另一类方法尚未处理。这些方法并不总是准确返回集合类型。它们可能会返回相同类型的集合，但具有不同的元素类型。经典示例是 map 方法。如果 s 是 Seq[Int]，并且 f 是从 Int 到 String 的函数，那么 s.map(f) 将返回 Seq[String]。因此，元素类型在接收方和结果之间发生变化，但集合类型保持不变。
还有许多其他方法的行为类似于 map。对于其中一些，你会期望这样（例如，flatMap、collect），但对于其他一些，你可能不会期望。例如，追加方法 ++ 也可能会返回与参数类型不同的结果——将 String 列表追加到 Int 列表将得到 Any 列表。这些方法应如何适应 RNA 链？期望的行为是在将碱基映射到碱基或使用 ++ 追加两个 RNA 链时取回 RNA 链
scala> val rna = RNA(A, U, G, G, C)
rna: RNA = RNA(A, U, G, G, C)
scala> rna map { case A => U case b => b }
res7: RNA = RNA(U, U, G, G, C)
scala> rna ++ rna
res8: RNA = RNA(A, U, G, G, C, A, U, G, G, C)
另一方面，将碱基映射到 RNA 链上的其他类型不能产生另一个 RNA 链，因为新元素类型错误。它必须产生序列。同样，将非 Base 类型的元素追加到 RNA 链可以产生常规序列，但不能产生另一个 RNA 链。
scala> rna map Base.toInt
res2: IndexedSeq[Int] = Vector(0, 1, 2, 2, 3)
scala> rna ++ List("missing", "data")
res3: IndexedSeq[java.lang.Object] =
Vector(A, U, G, G, C, missing, data)
这是你在理想情况下所期望的。但这并不是 RNA2 类 提供的。事实上，所有示例都将返回 Vector 的实例，而不仅仅是后两个。如果你使用此类的实例运行以上前三个命令，你将获得
scala> val rna2 = RNA2(A, U, G, G, C)
rna2: RNA2 = RNA2(A, U, G, G, C)
scala> rna2 map { case A => U case b => b }
res0: IndexedSeq[Base] = Vector(U, U, G, G, C)
scala> rna2 ++ rna2
res1: IndexedSeq[Base] = Vector(A, U, G, G, C, A, U, G, G, C)
因此，map 和 ++ 的结果永远不是 RNA 链，即使生成集合的元素类型是 Base。要了解如何做得更好，最好仔细查看 map 方法（或具有类似签名的 ++）的签名。 map 方法最初在类 scala.collection.TraversableLike 中定义，其签名如下
def map[B, That](f: A => B)
(implicit cbf: CanBuildFrom[Repr, B, That]): That
此处 A 是集合元素的类型，Repr 是集合本身的类型，即传递给 TraversableLike 和 IndexedSeqLike 等实现类的第二个类型参数。map 方法需要另外两个类型参数，B 和 That。B 参数表示映射函数的结果类型，也是新集合的元素类型。That 显示为 map 的结果类型，因此它表示所创建的新集合的类型。
如何确定 That 类型？事实上，它通过类型 CanBuildFrom[Repr, B, That] 的隐式参数 cbf 与其他类型关联。这些 CanBuildFrom 隐式参数由各个集合类定义。回想一下，类型为 CanBuildFrom[Repr, B, That] 的隐式值表示：“给定类型为 Repr 的集合和类型为 B 的新元素，这里有一种方法可以构建包含这些元素的类型为 That 的集合”。
现在，RNA2 序列上 map 和 ++ 的行为变得更加清晰。没有 CanBuildFrom 实例可以创建 RNA2 序列，因此在继承特征 IndexedSeq 的伴随对象中找到了下一个可用的 CanBuildFrom。该隐式参数创建 Vector（回想一下，Vector 是 IndexedSeq 的默认实现），这就是将 map 应用于 rna2 时所看到的内容。
RNA 链类的最终版本
final class RNA private (val groups: Array[Int], val length: Int)
extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA] {
import RNA._
// Mandatory re-implementation of `newBuilder` in `IndexedSeq`
override protected[this] def newBuilder: Builder[Base, RNA] =
RNA.newBuilder
// Mandatory implementation of `apply` in `IndexedSeq`
def apply(idx: Int): Base = {
if (idx < 0 || length <= idx)
throw new IndexOutOfBoundsException
Base.fromInt(groups(idx / N) >> (idx % N * S) & M)
}
// Optional re-implementation of foreach,
// to make it more efficient.
override def foreach[U](f: Base => U): Unit = {
var i = 0
var b = 0
while (i < length) {
b = if (i % N == 0) groups(i / N) else b >>> S
f(Base.fromInt(b & M))
i += 1
}
}
}
RNA 伴随对象的最终版本
object RNA {
private val S = 2 // number of bits in group
private val M = (1 << S) - 1 // bitmask to isolate a group
private val N = 32 / S // number of groups in an Int
def fromSeq(buf: Seq[Base]): RNA = {
val groups = new Array[Int]((buf.length + N - 1) / N)
for (i <- 0 until buf.length)
groups(i / N) |= Base.toInt(buf(i)) << (i % N * S)
new RNA(groups, buf.length)
}
def apply(bases: Base*) = fromSeq(bases)
def newBuilder: Builder[Base, RNA] =
new ArrayBuffer mapResult fromSeq
implicit def canBuildFrom: CanBuildFrom[RNA, Base, RNA] =
new CanBuildFrom[RNA, Base, RNA] {
def apply(): Builder[Base, RNA] = newBuilder
def apply(from: RNA): Builder[Base, RNA] = newBuilder
}
}
To address this shortcoming, you need to define an implicit instance
of CanBuildFrom in the companion object of the RNA class. That
instance should have type CanBuildFrom[RNA, Base, RNA]. Hence, this
instance states that, given an RNA strand and a new element type Base,
you can build another collection which is again an RNA strand. The two
listings above of class RNA and
its companion object show the
details. Compared to class RNA2
there are two important
differences. First, the newBuilder implementation has moved from the
RNA class to its companion object. The newBuilder method in class RNA
simply forwards to this definition. Second, there is now an implicit
CanBuildFrom value in object RNA. To create this value you need to
define two apply methods in the CanBuildFrom trait. Both create a new
builder for an RNA collection, but they differ in their argument
list. The apply() method simply creates a new builder of the right
type. By contrast, the apply(from) method takes the original
collection as argument. This can be useful to adapt the dynamic type
of builder’s return type to be the same as the dynamic type of the
receiver. In the case of RNA this does not come into play because RNA
is a final class, so any receiver of static type RNA also has RNA as
its dynamic type. That’s why apply(from) also simply calls newBuilder,
ignoring its argument.
就是这样。最终的 RNA 类 以其预期类型实现了所有集合方法。其实现需要一些协议。从本质上讲，你需要知道在何处放置 newBuilder 工厂和 canBuildFrom 隐式函数。从积极的一面来看，只需很少的代码，你就可以自动定义大量方法。此外，如果你不打算对集合执行诸如 take、drop、map 或 ++ 之类的批量操作，则可以选择不采用额外的长度，而是在 类 RNA1 中所示的实现处停止。
到目前为止的讨论集中在定义新序列所需的最小定义量上，这些序列使用遵守特定类型的方法。但在实践中，你可能还希望向序列添加新功能或覆盖现有方法以提高效率。一个示例是类 RNA 中覆盖的 foreach 方法。foreach 本身就是一个重要的方法，因为它实现了对集合的循环。此外，许多其他集合方法都是根据 foreach 实现的。因此，投入一些精力优化方法的实现是有意义的。在 IndexedSeq 中 foreach 的标准实现将使用 apply 简单地选择集合的每个第 i 个元素，其中 i 的范围从 0 到集合的长度减一。因此，此标准实现选择一个数组元素，并为 RNA 链中的每个元素从中解包一个碱基。类 RNA 中覆盖的 foreach 比这更智能。对于每个选定的数组元素，它会立即将给定的函数应用于其中包含的所有碱基。因此，数组选择和位解包的工作量大大减少。
集成新的前缀映射
作为第二个示例，你将学习如何将一种新的映射集成到集合框架中。这个想法是通过“Patricia 树”实现一个以 String 作为键类型的可变映射。术语Patricia 实际上是“检索以字母数字编码的信息的实用算法”的缩写，而trie 则来自 retrieval（trie 也称为基数树或前缀树）。这个想法是将集合或映射存储为一棵树，其中搜索键中的后续字符唯一地确定了通过该树的路径。例如，存储字符串“abc”、“abd”、“al”、“all”和“xy”的 Patricia 树将如下所示
一个示例 Patricia 树：
要在此树中查找对应于字符串“abc”的节点，只需按照标记为“a”的子树，从那里继续到标记为“b”的子树，最终到达其标记为“c”的子树。如果 Patricia 树用作映射，则与键关联的值存储在可通过键访问的节点中。如果它是一个集合，则只需存储一个标记，表示该节点存在于集合中。
Patricia 树支持非常高效的查找和更新。另一个不错的特性是它们支持通过给定前缀选择子集合。例如，在上面的 Patricia 树中，只需从树的根节点按照“a”链接，即可获得所有以“a”开头的键的子集合。
基于这些想法，我们现在将引导您完成实现作为 Patricia 树的映射。我们将映射称为 PrefixMap，这意味着它提供了一个方法 withPrefix，该方法选择所有以给定前缀开头的键的子映射。我们首先使用正在运行的示例中显示的键定义一个前缀映射
scala> val m = PrefixMap("abc" -> 0, "abd" -> 1, "al" -> 2,
"all" -> 3, "xy" -> 4)
m: PrefixMap[Int] = Map((abc,0), (abd,1), (al,2), (all,3), (xy,4))
然后在 m 上调用 withPrefix 将生成另一个前缀映射
scala> m withPrefix "a"
res14: PrefixMap[Int] = Map((bc,0), (bd,1), (l,2), (ll,3))
Patricia 树实现
import collection._
class PrefixMap[T]
extends mutable.Map[String, T]
with mutable.MapLike[String, T, PrefixMap[T]] {
var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
var value: Option[T] = None
def get(s: String): Option[T] =
if (s.isEmpty) value
else suffixes get (s(0)) flatMap (_.get(s substring 1))
def withPrefix(s: String): PrefixMap[T] =
if (s.isEmpty) this
else {
val leading = s(0)
suffixes get leading match {
case None =>
suffixes = suffixes + (leading -> empty)
case _ =>
}
suffixes(leading) withPrefix (s substring 1)
}
override def update(s: String, elem: T) =
withPrefix(s).value = Some(elem)
override def remove(s: String): Option[T] =
if (s.isEmpty) { val prev = value; value = None; prev }
else suffixes get (s(0)) flatMap (_.remove(s substring 1))
def iterator: Iterator[(String, T)] =
(for (v <- value.iterator) yield ("", v)) ++
(for ((chr, m) <- suffixes.iterator;
(s, v) <- m.iterator) yield (chr +: s, v))
def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this }
def -= (s: String): this.type = { remove(s); this }
override def empty = new PrefixMap[T]
}
前面的列表显示了 PrefixMap 的定义。该映射的键类型为 String，值类型为参数类型 T。它扩展了 mutable.Map[String, T] 和 mutable.MapLike[String, T, PrefixMap[T]]。您已经在 RNA 链示例中为序列看到了此模式；然后，现在继承一个实现类（例如 MapLike）是为了为诸如 filter 之类的转换获取正确的结果类型。
前缀映射节点有两个可变字段：suffixes 和 value。value 字段包含与节点关联的可选值。它被初始化为 None。suffixes 字段包含从字符到 PrefixMap 值的映射。它被初始化为空映射。
您可能会问，我们为何选择不可变映射作为 suffixes 的实现类型？可变映射不是更标准吗，因为 PrefixMap 作为一个整体也是可变的？答案是，仅包含几个元素的不可变映射在空间和执行时间方面都非常高效。例如，包含少于 5 个元素的映射表示为单个对象。相比之下，标准可变映射是 HashMap，即使为空，通常也占用约 80 个字节。因此，如果小型集合很常见，最好选择不可变而不是可变。对于 Patricia 尝试，我们期望除树最顶部的节点外的大多数节点仅包含几个后继。因此，将这些后继存储在不可变映射中可能更有效。
现在，让我们看看需要为映射实现的第一个方法：get。算法如下：要获取与前缀映射中空字符串关联的值，只需选择存储在树根（当前映射）中的可选 value。否则，如果键字符串不为空，请尝试选择对应于字符串第一个字符的子映射。如果产生映射，请继续查找该映射中第一个字符之后的键字符串的其余部分。如果选择失败，则该键未存储在映射中，因此返回 None。使用 opt.flatMap(x => f(x)) 可以优雅地表示对选项值 opt 的组合选择。当应用于 None 的可选值时，它返回 None。否则 opt 是 Some(x)，并且函数 f 应用于封装的值 x，产生一个新选项，由 flatMap 返回。
为可变映射实现的下一个两个方法是 += 和 -=。在 PrefixMap 的实现中，它们由其他两个方法定义：update 和 remove。
remove 方法与 get 非常相似，只是在返回任何关联值之前，将包含该值的字段设置为 None。update 方法首先调用 withPrefix 导航到需要更新的树节点，然后将该节点的 value 字段设置为给定值。withPrefix 方法遍历树，并在必要时创建子映射，如果某个字符前缀尚未包含在树中作为路径。
要为可变映射实现的最后一个抽象方法是 iterator。此方法需要生成一个迭代器，以产生存储在映射中的所有键/值对。对于任何给定的前缀映射，此迭代器由以下部分组成：首先，如果映射在根部的 value 字段中包含一个已定义的值 Some(x)，则 ("", x) 是从迭代器返回的第一个元素。此外，迭代器需要遍历存储在 suffixes 字段中的所有子映射的迭代器，但它需要在这些迭代器返回的每个键字符串前面添加一个字符。更准确地说，如果 m 是通过字符 chr 从根部到达的子映射，并且 (s, v) 是从 m.iterator 返回的元素，则根部的迭代器将返回 (chr +: s, v)。此逻辑在 PrefixMap 中 iterator 方法的实现中作为两个 for 表达式的连接而实现得非常简洁。第一个 for 表达式遍历 value.iterator。这利用了以下事实：Option 值定义了一个迭代器方法，如果选项值为 None，则不返回任何元素，如果选项值为 Some(x)，则返回一个元素 x。
请注意，在 PrefixMap 中没有定义 newBuilder 方法。没有必要，因为映射和集合带有默认构建器，它们是类 MapBuilder 的实例。对于可变映射，默认构建器从一个空映射开始，然后使用映射的 += 方法添加连续的元素。对于不可变映射，使用非破坏性元素添加方法 + 代替方法 +=。集合的工作方式相同。
然而，在所有这些情况下，要构建正确类型的集合，您需要从该类型的空集合开始。这是由 empty 方法提供的，这是 PrefixMap 中定义的最后一个方法。此方法仅返回一个新的 PrefixMap。
前缀映射的伴生对象
import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom
object PrefixMap extends {
def empty[T] = new PrefixMap[T]
def apply[T](kvs: (String, T)*): PrefixMap[T] = {
val m: PrefixMap[T] = empty
for (kv <- kvs) m += kv
m
}
def newBuilder[T]: Builder[(String, T), PrefixMap[T]] =
new MapBuilder[String, T, PrefixMap[T]](empty)
implicit def canBuildFrom[T]
: CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] =
new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {
def apply(from: PrefixMap[_]) = newBuilder[T]
def apply() = newBuilder[T]
}
}
现在，我们转向伴生对象 PrefixMap。事实上，严格来说，没有必要定义这个伴生对象，因为类 PrefixMap 可以独立存在。对象 PrefixMap 的主要目的是定义一些方便的工厂方法。它还定义了一个隐式的 CanBuildFrom，以更好地进行类型化处理。
这两个方便的方法是 empty 和 apply。对于 Scala 集合框架中的所有其他集合，都存在相同的方法，因此在此处定义它们也很有意义。使用这两个方法，您可以像对任何其他集合一样编写 PrefixMap 字面量
scala> PrefixMap("hello" -> 5, "hi" -> 2)
res0: PrefixMap[Int] = Map(hello -> 5, hi -> 2)
scala> PrefixMap.empty[String]
res2: PrefixMap[String] = Map()
对象 PrefixMap 中的另一个成员是一个隐式的 CanBuildFrom 实例。它与上一节中 RNA 伴生对象 中的 CanBuildFrom 定义具有相同目的：使 map 等方法返回最佳可能的类型。例如，考虑将一个函数映射到 PrefixMap 的键/值对。只要该函数生成字符串对和某些第二类型，结果集合将再次成为 PrefixMap。这是一个示例
scala> res0 map { case (k, v) => (k + "!", "x" * v) }
res8: PrefixMap[String] = Map(hello! -> xxxxx, hi! -> xx)
给定函数参数采用前缀映射 res0 的键/值绑定，并生成字符串对。 map 的结果是 PrefixMap，这次值类型为 String，而不是 Int。如果没有 PrefixMap 中隐含的 canBuildFrom，结果将只是一个常规可变映射，而不是前缀映射。为方便起见， PrefixMap 对象定义了一个 newBuilder 方法，但它仍然只使用默认 MapBuilder。
摘要
总之，如果你想将一个新的集合类完全集成到框架中，你需要注意以下几点
- 确定集合应该是可变的还是不可变的。
- 为集合选择正确的基本特征。
- 从正确的实现特征继承以实现大多数集合操作。
- 如果你希望
map和类似操作返回你的集合类型的实例，请在类的伴随对象中提供一个隐式的CanBuildFrom。
你现在已经了解了 Scala 的集合是如何构建的，以及如何添加新的集合类型。由于 Scala 对抽象的丰富支持，每个新的集合类型都有大量的函数，而无需重新实现所有这些函数。
致谢
这些页面包含改编自 Odersky、Spoon 和 Venners 所著的 Programming in Scala 第二版的资料。我们感谢 Artima 欣然同意其出版。