Scala 2.13 集合的架构

语言

    Julien Richard-Foy

    本文档详细描述了 Scala 集合框架的架构。与 集合简介 相比，你将进一步了解框架的内部工作原理。你还会了解此架构如何帮助你用几行代码定义自己的集合，同时重复使用框架中绝大部分的集合功能。

    集合 API 包含大量集合操作，这些操作在许多不同的集合实现中统一存在。为每种集合类型重新实现每个集合操作将导致大量的代码，其中大部分将从其他地方复制。随着时间推移，当在集合库的一部分中添加或修改操作，而在其他部分中不添加或修改操作时，这种代码重复会导致不一致。集合框架的主要设计目标是避免任何重复，在尽可能少的地方定义每个操作。（理想情况下，所有内容都应该只在一个地方定义，但有一些例外情况需要重新定义。）设计方法是在集合“模板”中实现大多数操作，这些模板可以灵活地从各个基类和实现中继承。

    更准确地说，这些模板解决了以下挑战

    • 一些转换操作返回相同的具体集合类型（例如，filter，在 List[Int] 上调用返回 List[Int]），
    • 一些转换操作返回具有不同元素类型的相同具体集合类型（例如，对 List[Int] 调用 map 可以返回 List[String]），
    • 一些集合具有单个元素类型（例如 List[A]），而另一些集合具有两个元素类型（例如 Map[K, V]），
    • 对集合执行的一些操作会根据元素类型返回不同的具体集合。例如，如果映射函数返回键值对，则对 Map 调用 map 会返回 Map，否则会返回 Iterable，
    • 对某些集合执行的转换操作需要其他隐式参数（例如，对 SortedSet 执行 map 会采用隐式 Ordering），
    • 一些集合是严格的（例如 List），而另一些集合是非严格的（例如 View 和 LazyList）。

    以下部分将说明模板如何应对这些挑战。

    分解常见操作

    本部分介绍集合中发现的可变性，必须对其进行抽象化才能定义可重用的操作实现。

    我们可以将集合操作分为两类

    • 转换操作，它返回另一个集合（例如 map、filter、zip 等），
    • 归约操作，它返回一个值（例如 isEmpty、foldLeft、find 等）。

    转换操作在模板特征中更难实现，因为我们希望它们返回尚未了解的集合类型。例如，考虑对 List[A] 和 Vector[A] 执行 map 操作的签名

    trait List[A] {
  def map[B](f: A => B): List[B]
}

trait Vector[A] {
  def map[B](f: A => B): Vector[B]
}

    trait List[A]:
  def map[B](f: A => B): List[B]

trait Vector[A]:
  def map[B](f: A => B): Vector[B]

    要概括 map 的类型签名，我们必须抽象化结果集合类型构造函数。

    一个略有不同的示例是 filter。考虑对其在 List[A] 和 Map[K, V] 上的类型签名

    trait List[A] {
  def filter(p: A => Boolean): List[A]
}

trait Map[K, V] {
  def filter(p: ((K, V)) => Boolean): Map[K, V]
}

    trait List[A]:
  def filter(p: A => Boolean): List[A]

trait Map[K, V]:
  def filter(p: ((K, V)) => Boolean): Map[K, V]

    要概括 filter 的类型签名，我们必须抽象化结果集合类型。

    总之，更改元素类型的操作（map、flatMap、collect 等）需要抽象化结果集合类型构造函数，而保持相同元素类型的操作（filter、take、drop 等）需要抽象化结果集合类型。

    对集合类型进行抽象

    模板特质 IterableOps 实现 Iterable[A] 集合类型上可用的操作。

    以下是特质 IterableOps 的头文件

    trait IterableOps[+A, +CC[_], +C] { … }

    类型参数 A 表示可迭代元素的类型，类型参数 CC 表示集合类型构造函数，类型参数 C 表示集合类型。

    这允许我们定义 filter 和 map 的签名，如下所示

    trait IterableOps[+A, +CC[_], +C] {
  def filter(p: A => Boolean): C = …
  def map[B](f: A => B): CC[B] = …
}

    trait IterableOps[+A, +CC[_], +C]:
  def filter(p: A => Boolean): C = …
  def map[B](f: A => B): CC[B] = …

    叶集合类型适当地实例化类型参数。例如，在 List[A] 的情况下，我们希望 CC 为 List，C 为 List[A]

    trait List[+A] extends Iterable[A]
  with IterableOps[A, List, List[A]]

    模板特质的四个分支

    精明的读者可能已经注意到，给定的 map 操作类型签名不适用于 Map 集合，因为 IterableOps 特质的 CC[_] 类型参数采用一个类型参数，而 Map[K, V] 采用两个类型参数。

    为了支持具有两个类型参数的集合类型构造函数，我们有另一个名为 MapOps 的模板特质

    trait MapOps[K, +V, +CC[_, _], +C] extends IterableOps[(K, V), Iterable, C] {
  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] = …
}

    trait MapOps[K, +V, +CC[_, _], +C] extends IterableOps[(K, V), Iterable, C]:
  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] = …

    然后 Map[K, V] 可以扩展此特质并适当地实例化其类型参数

    trait Map[K, V] extends Iterable[(K, V)]
  with MapOps[K, V, Map, Map[K, V]]

    请注意，MapOps 特质继承自 IterableOps，以便在 IterableOps 中定义的操作也在 MapOps 中可用。还要注意，传递给 IterableOps 特质的集合类型构造函数是 Iterable。这意味着 Map[K, V] 继承了 map 操作的两个重载

    // from MapOps
def map[K2, V2](f: ((K, V)) => (K2, V2)): Map[K2, V2]

// from IterableOps
def map[B](f: ((K, V)) => B): Iterable[B]

    在使用站点，当您调用 map 操作时，编译器会选择两个重载之一。如果作为参数传递给 map 的函数返回一个对，则两个函数都适用。在这种情况下，将使用 MapOps 中的版本，因为根据重载解析规则，它更具体，因此生成的集合是一个 Map。如果参数函数不返回对，则只适用于在 IterableOps 中定义的版本。在这种情况下，生成的集合是一个 Iterable。这就是我们遵循“相同结果类型”原则的方式：在可能的情况下，集合上的转换方法会生成相同类型的集合。

    总之，Map 集合类型采用两个类型参数的事实使得无法将其转换操作与 IterableOps 中的操作统一，因此需要专门的 MapOps 模板特征。

    在 IterableOps 中定义的转换操作的类型签名与更具体的集合类型的类型签名不匹配时，还会有另一种情况：SortedSet[A]。在这种情况下，map 操作的类型签名如下

    def map[B](f: A => B)(implicit ord: Ordering[B]): SortedSet[B]

    def map[B](f: A => B)(using ord: Ordering[B]): SortedSet[B]

    与我们在 IterableOps 中的签名不同之处在于，这里我们需要一个元素类型的隐式 Ordering 实例。

    与 Map 一样，SortedSet 需要一个专门的模板特征，其中包含转换操作的重载

    trait SortedSetOps[A, +CC[_], +C] extends IterableOps[A, Set, C] {
  def map[B](f: A => B)(implicit ord: Ordering[B]): CC[B] = …
}

    trait SortedSetOps[A, +CC[_], +C] extends IterableOps[A, Set, C]:
  def map[B](f: A => B)(using ord: Ordering[B]): CC[B] = …

    然后，继承 SortedSetOps 特征的集合类型会适当地实例化其类型参数

    trait SortedSet[A] extends SortedSetOps[A, SortedSet, SortedSet[A]]

    最后，有第四种需要专门模板特征的集合：SortedMap[K, V]。此类型的集合有两个类型参数，并且需要在键类型上有一个隐式排序实例。因此，我们有一个 SortedMapOps 模板特征，它提供了适当的重载。

    总的来说，我们已经看到我们有四个模板特征分支

    kind 未排序 已排序
    CC[_] IterableOps SortedSetOps
    CC[_, _] MapOps SortedMapOps

    这里有一个说明架构的图表

    模板特征以灰色显示，而集合类型以白色显示。

    严格和非严格集合

    集合框架设计中考虑的另一个差异是，某些集合类型急切地评估其元素（例如 List、Set 等），而其他集合类型则延迟评估，直到有效访问该元素（例如 LazyList 和 View）。前一类集合被称为“严格”，而后一类被称为“非严格”。

    因此，转换操作的默认实现必须保留继承这些实现的具体集合类型的“严格性”。例如，我们希望默认 map 实现当由 View 继承时是非严格的，当由 List 继承时是严格的。

    为了实现这一点，操作默认情况下是根据非严格 View 实现的。有记录可查，View “描述”应用于集合的操作，但直到 View 有效遍历时才评估其结果。以下是 View 的（简化）定义

    trait View[+A] extends Iterable[A] with IterableOps[A, View, View[A]] {
  def iterator: Iterator[A]
}

    trait View[+A] extends Iterable[A], IterableOps[A, View, View[A]]:
  def iterator: Iterator[A]

    View 是一个 Iterable，它只有一个抽象方法，用于返回一个 Iterator 以遍历其元素。View 元素仅在其 Iterator 被遍历时才被评估。

    操作实现

    现在我们更熟悉模板特征的层次结构，我们可以看看一些操作的实际实现。例如，考虑 filter 和 map 的实现

    trait IterableOps[+A, +CC[_], +C] {

  def filter(pred: A => Boolean): C =
    fromSpecific(new View.Filter(this, pred))

  def map[B](f: A => B): CC[B] = 
    from(new View.Map(this, f))

  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def from[E](it: IterableOnce[E]): CC[E]
}

    trait IterableOps[+A, +CC[_], +C]:

  def filter(pred: A => Boolean): C =
    fromSpecific(View.Filter(this, pred))

  def map[B](f: A => B): CC[B] = 
    from(View.Map(this, f))

  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def from[E](it: IterableOnce[E]): CC[E]

    让我们逐步详细介绍 filter 的实现

    • View.Filter 的实例化创建一个（非严格）View，该视图过滤基础集合的元素；
    • 对 fromSpecific 的调用将 View 转换为具体集合 C。 fromSpecific 的实现留给具体集合：它们可以决定以严格或非严格的方式评估操作产生的元素。

    map 的实现类似，只是它没有使用 fromSpecific，而是使用了 from，后者将一个可迭代对象作为参数，其元素类型 E 是任意的。

    实际上， from 操作并未直接在 IterableOps 中定义，而是通过（抽象）iterableFactory 成员访问

    trait IterableOps[+A, +CC[_], +C] {

  def iterableFactory: IterableFactory[CC]
  
  def map[B](f: A => B): CC[B] = 
    iterableFactory.from(new View.Map(this, f))  
}

    trait IterableOps[+A, +CC[_], +C]:

  def iterableFactory: IterableFactory[CC]
  
  def map[B](f: A => B): CC[B] = 
    iterableFactory.from(View.Map(this, f))

    此 iterableFactory 成员由具体集合实现，并且通常引用其伴随对象，该对象提供创建具体集合实例的工厂方法。以下是 IterableFactory 定义的摘录

    trait IterableFactory[+CC[_]] {
  def from[A](source: IterableOnce[A]): CC[A]
}

    trait IterableFactory[+CC[_]]:
  def from[A](source: IterableOnce[A]): CC[A]

    最后但并非最不重要的一点是，如上文所述，由于我们有四个模板特征分支，因此我们有四个相应的工厂分支。例如，以下是 MapOps 中 map 操作实现中相关的代码部分

    trait MapOps[K, +V, +CC[_, _], +C]
  extends IterableOps[(K, V), Iterable, C] {

  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] =
    mapFactory.from(new View.Map(this, f))

  // Similar to iterableFactory, but for Map collection types
  def mapFactory: MapFactory[CC]

}

trait MapFactory[+CC[_, _]] {
  def from[K, V](it: IterableOnce[(K, V)]): CC[K, V]
}

    trait MapOps[K, +V, +CC[_, _], +C]
  extends IterableOps[(K, V), Iterable, C]:

  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] =
    mapFactory.from(View.Map(this, f))

  // Similar to iterableFactory, but for Map collection types
  def mapFactory: MapFactory[CC]

trait MapFactory[+CC[_, _]]:
  def from[K, V](it: IterableOnce[(K, V)]): CC[K, V]

    当严格评估更可取（或不可避免）时

    在前面的部分中，我们解释了默认操作实现应该保留具体集合的“严格性”。但是，在某些情况下，这会导致效率较低的实现。例如， partition 必须对基础集合执行两次遍历。在其他一些情况下（例如 groupBy），如果不评估集合元素，就根本无法实现操作。

    对于这些情况，我们还提供了以严格模式实现操作的方法。模式不同：它不是基于 View，而是基于 Builder。以下是 Builder 特征的概述

    package scala.collection.mutable

trait Builder[-A, +C] {
  def addOne(elem: A): this.type
  def result(): C
}

    package scala.collection.mutable

trait Builder[-A, +C]:
  def addOne(elem: A): this.type
  def result(): C

    Builder 在元素类型 A 和它们返回的集合类型 C 中都是通用的。你可以使用 b.addOne(x)（或 b += x）将元素 x 添加到 builder b 中。 result() 方法从 builder 返回一个集合。

    通过与 fromSpecificIterable 和 fromIterable 对称，模板特征提供了获取 builder 的方法，该 builder 产生具有相同类型元素的集合，以及获取 builder 的方法，该 builder 产生具有相同类型但元素类型不同的集合。以下代码显示了 IterableOps 和 IterableFactory 的相关部分，以在严格模式和非严格模式下构建集合

    trait IterableOps[+A, +CC[_], +C] {
  def iterableFactory: IterableFactory[CC]
  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def newSpecificBuilder: Builder[A, C]
}

trait IterableFactory[+CC[_]] {
  def from[A](source: IterableOnce[A]): CC[A]
  def newBuilder[A]: Builder[A, CC[A]]
}

    trait IterableOps[+A, +CC[_], +C]:
  def iterableFactory: IterableFactory[CC]
  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def newSpecificBuilder: Builder[A, C]

trait IterableFactory[+CC[_]]:
  def from[A](source: IterableOnce[A]): CC[A]
  def newBuilder[A]: Builder[A, CC[A]]

    请注意，一般来说，不必是严格的操作应该以非严格模式实现，否则在非严格具体集合上使用时会导致令人惊讶的行为（你可以在 这篇文章 中阅读有关该语句的更多信息）。话虽如此，严格模式通常更有效。这就是我们提供模板特征的原因，其操作实现已被覆盖以利用严格 builder。这些模板特征的名称始终以 StrictOptimized 开头。如果你的自定义集合是严格集合，则应为其使用此类模板特征。

    总结

    本文档说明

    • 集合操作在以 Ops 为后缀的模板特征中实现（例如 IterableOps[A, CC[_], C]），
    • 这些模板特征抽象了集合元素的类型（A）、返回集合的类型构造函数（CC）和返回集合的类型（C），
    • 模板特征有四个分支（IterableOps、MapOps、SortedSetOps 和 SortedMapOps），
    • 某些转换操作（例如 map）被重载以根据其参数类型返回不同的结果类型，
    • 转换操作的逻辑主要在视图中实现，但模板特征有专门版本（以 StrictOptimized 为前缀），覆盖这些操作以使用基于 builder 的方法。

    你现在拥有实现 自定义集合类型 所需的所有知识。

    致谢

    此页面包含改编自 Odersky、Spoon 和 Venners 所著书籍 Programming in Scala 的材料。我们感谢 Artima 同意将其发布。

    此页面的贡献者

    内容
    此页面有问题？
         请帮助我们修复它！