Scala 2.8 集合设计教程

Question

继我的困惑之后，有哪些好的资源可以解释新的Scala 2.8 集合库已经结构化。我有兴趣找到有关以下内容如何组合在一起的一些信息：

• 集合类/特征本身（例如List、Iterable）
• 为什么喜欢 类存在（例如 TraversableLike）
• 伴随方法的用途（例如 List.companion）
• 我如何知道哪些隐式对象在作用域内给定点

Answer 1

前言

Martin Odersky 有一个 2.8 集合演练，可能应该是你的第一个参考。它还补充了架构注释 ，这对于那些想要设计自己的系列的人来说会特别感兴趣。

这个答案的其余部分是在任何此类东西存在之前写的（事实上，在 2.8.0 本身发布之前）。

您可以找到一篇关于它的论文 Scala SID #3。对于那些对 Scala 2.7 和 2.8 之间的差异感兴趣的人来说，该领​​域的其他论文也应该很有趣。

我将选择性地引用该论文，并补充我的一些想法。还有一些由 Matthias 在 decodified.com 生成的图像，原始 SVG 文件可以在 这里。

集合类/特征本身

集合的特征实际上分为三种层次结构：一种用于可变集合，一种用于不可变集合，一种不对集合做出任何假设。

并行、串行和可能并行集合之间也有区别，这是在 Scala 2.9 中引入的。我将在下一节中讨论它们。本节中描述的层次结构专门针对非并行集合。

下图显示了 Scala 2.8 引入的非特定层次结构：

显示的所有元素都是特征。在另外两个层次结构中，还有直接继承特征的类以及通过隐式转换为包装类可以被视为属于该层次结构的类。这些图表的图例可以在它们后面找到。

不可变层次结构图：

可变层次结构图：

图例：

这是集合层次结构的缩写 ASCII 描述，供那些看不到图像的人参考。

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

并行集合

当 Scala 2.9 引入并行集合时，设计目标之一是使其使用尽可能无缝。用最简单的术语来说，可以用并行集合替换非并行（串行）集合，并立即获得好处。

然而，由于在此之前所有集合都是串行的，因此许多使用它们的算法都假设并依赖于它们是串行的这一事实。提供给具有此类假设的方法的并行集合将会失败。因此，上一节中描述的所有层次结构都要求串行处理。

创建了两个新的层次结构来支持并行集合。

并行集合层次结构具有相同的特征名称，但前面带有 Par：ParIterable、ParSeq、ParMap 和ParSet。请注意，没有 ParTraversable，因为任何支持并行访问的集合都能够支持更强的 ParIterable 特征。它也不具有串行层次结构中存在的一些更专门的特征。整个层次结构位于目录 scala.collection.parallel 下。

实现并行集合的类也有所不同，ParHashMap 和 ParHashSet 用于可变和不可变并行集合，还有 ParRange 和 ParVector code> 实现 immutable.ParSeq 和 ParArray 实现 mutable.ParSeq。

还存在另一个层次结构，它反映了串行和并行集合的特征，但带有前缀 Gen：GenTraversable、GenIterable、GenSeq< /code>、GenMap 和 GenSet。这些特征是并行和串行集合的父。这意味着采用 Seq 的方法无法接收并行集合，但采用 GenSeq 的方法预计可以处理串行和并行集合。

鉴于这些层次结构的构造方式，为 Scala 2.8 编写的代码与 Scala 2.9 完全兼容，并且需要串行行为。如果不重写，它就无法利用并行集合，但所需的更改非常小。

使用并行集合

任何集合都可以通过调用方法 par 转换为并行集合。同样，任何集合都可以通过调用方法 seq 转换为串行集合。

如果集合已经是所请求的类型（并行或串行），则不会发生任何转换。然而，如果对并行集合调用 seq 或对串行集合调用 par，则会生成具有所请求特征的新集合。

不要混淆 seq（将集合转换为非并行集合）和 toSeq（返回从集合的元素创建的 Seq）收藏。对并行集合调用 toSeq 将返回 ParSeq，而不是串行集合。

主要特征

虽然有许多实现类和子特征，但层次结构中有一些基本特征，每个特征都提供更多方法或更具体的保证，但减少了可以实现它们的类的数量。

在下面的小节中，我将简要描述主要特征及其背后的想法。

Trait TraversableOnce

此特征与下面描述的特征 Traversable 非常相似，但有一个限制，即您只能使用它一次。也就是说，在 TraversableOnce 上调用的任何方法都可能导致其无法使用。

此限制使得可以在集合和迭代器之间共享相同的方法。这使得使用 Iterator 但不使用特定于 Iterator 的方法的方法实际上能够使用任何集合，加上迭代器（如果重写）接受TraversableOnce。

因为 TraversableOnce 统一了集合和迭代器，所以它不会出现在前面的图中，这些图中只涉及集合。

Trait Traversable

位于集合层次结构顶部的是Traversable 特征。它唯一的抽象操作是

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

该操作旨在遍历集合的所有元素，并将给定的操作 f 应用于每个元素
元素。这样做只是为了它的副作用；事实上 f 的任何函数结果都会被丢弃
foreach。

可遍历的对象可以是有限的或无限的。无限可遍历对象的一个​​例子是流
自然数Stream.from(0)。方法hasDefiniteSize指示集合是否可能
无限。如果 hasDefiniteSize 返回 true，则该集合肯定是有限的。如果返回 false，则
集合尚未完全阐述，因此它可能是无限的或有限的。

此类定义了可以通过 foreach 有效实现的方法（超过 40 个）。

Trait Iterable

该特征声明了一个抽象方法iterator，它返回一个迭代器，该迭代器一一生成集合的所有元素。 Iterable 中的 foreach 方法是通过 iterator 实现的。为了提高效率，Iterable 的子类通常使用直接实现来重写 foreach。

Iterable 类还为 Traversable 添加了一些不常用的方法，只有在 iterator 可用的情况下才能有效实现。它们总结如下。

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

其他特征

在Iterable之后，有三个继承自它的基本特征：Seq、Set和Map。这三个都有一个 apply 方法，并且三个都实现了 PartialFunction 特征，但是 apply 的含义在每种情况下都不同。

我相信 Seq、Set 和 Map 的含义很直观。在它们之后，这些类分解为特定的实现，这些实现提供了有关性能的特定保证，以及由此而提供的方法。还可以使用一些经过进一步细化的特征，例如 LinearSeq、IndexedSeq 和 SortedSet。

下面的列表可能会得到改进。留下评论和建议，我会修复它。

基类和特征

• Traversable -- 基本集合类。只需使用foreach即可实现。
  • TraversableProxy -- Traversable 的代理。只需将 self 指向真正的集合即可。
  • TraversableView -- 具有一些非严格方法的 Traversable。
  • TraversableForwarder -- 将大多数方法转发到底层，除了 toString、hashCode、equals< /code>、stringPrefix、newBuilder、view 以及创建同类新可迭代对象的所有调用。
  • mutable.Traversable 和 immutable.Traversable -- 与 Traversable 相同，但限制集合类型。
  • 存在其他特殊情况的Iterable类，例如MetaData。
  • Iterable -- 可以为其创建Iterator 的集合（通过iterator）。
    • IterableProxy、IterableView、mutable 和 immutable.Iterable。

• Iterator —— 不是 Traversable 后代的特征。定义 next 和 hasNext。
  • CountedIterator -- 定义 count 的 Iterator，它返回到目前为止看到的元素。
  • BufferedIterator -- 定义 head，它返回下一个元素而不消耗它。
  • 存在其他特殊情况的 Iterator 类，例如 Source。

Maps

• Map - Tuple2 的 Iterable，它还提供了根据给定键检索值（元组的第二个元素）的方法（元组的第一个元素）。还扩展了 PartialFunction。
  • MapProxy -- Map 的代理。
  • DefaultMap -- 实现一些 Map 抽象方法的特征。
  • SortedMap -- 其键已排序的 Map。
    • immutable.SortMap
      • immutable.TreeMap -- 实现 immutable.SortedMap 的类。
  • immutable.Map
    • immutable.MapProxy
    • immutable.HashMap -- 通过键散列实现 immutable.Map 的类。
    • immutable.IntMap -- 实现专用于 Int 键的 immutable.Map 的类。使用基于密钥的二进制数字的树。
    • immutable.ListMap -- 通过列表实现 immutable.Map 的类。
    • immutable.LongMap -- 实现专用于 Long 键的 immutable.Map 的类。请参阅IntMap。
    • 还有针对特定数量的元素进行了优化的其他类。
  • 可变.Map
    • mutable.HashMap -- 通过键散列实现 mutable.Map 的类。
    • mutable.ImmutableMapAdaptor -- 从现有 immutable.Map 实现 mutable.Map 的类。
    • mutable.LinkedHashMap -- ?
    • mutable.ListMap -- 通过列表实现 mutable.Map 的类。
    • mutable.MultiMap -- 一个类，每个键接受多个不同的值。
    • mutable.ObservableMap -- 一个mixin，当与Map混合时，通过Publisher<向观察者发布事件/code> 接口。
    • mutable.OpenHashMap -- 基于开放哈希算法的类。
    • mutable.SynchronizedMap -- 一个mixin，应与Map混合以提供具有同步方法的版本。
    • mutable.MapProxy。

  


序列

• Seq ——元素序列。假设有明确定义的大小和元素重复。还扩展了 PartialFunction。
  • IndexedSeq -- 支持 O(1) 元素访问和 O(1) 长度计算的序列。
    • IndexedSeqView
    • immutable.PagedSeq -- IndexedSeq 的实现，其中元素由通过构造函数传递的函数按需生成。
    • immutable.IndexedSeq
      • immutable.Range -- 一个分隔的整数序列，在低端封闭，在高端开放，并且有一个步长。
        • immutable.Range.Inclusive - Range 也在高端闭合。
        • immutable.Range.ByOne -- 步长为 1 的 Range。
      • immutable.NumericRange -- 更通用的 Range 版本，可与任何 Integral 配合使用。
        • immutable.NumericRange.Inclusive、immutable.NumericRange.Exclusive。
        • immutable.WrappedString、immutable.RichString -- 包装器，可以将 String 视为 Seq[Char]，同时仍然保留 String 方法。我不确定它们之间有什么区别。

        


      


    • mutable.IndexedSeq
      • mutable.GenericArray -- 基于 Seq 的类数组结构。请注意，“类”Array 是 Java 的 Array，它更多的是一种内存存储方法，而不是类。
      • mutable.ResizableArray -- 基于可调整大小数组的类使用的内部类。
      • mutable.PriorityQueue、mutable.SynchronizedPriorityQueue -- 实现优先队列的类 -- 元素首先根据 Ordering 出列的队列，以及最后排队的顺序。
      • mutable.PriorityQueueProxy -- PriorityQueue 的抽象Proxy。

  • LinearSeq -- 线性序列的特征，对于 isEmpty、head 和 tail 具有高效的时间。
    • immutable.LinearSeq
      • immutable.List -- 不可变的单链接列表实现。
      • immutable.Stream -- 惰性列表。它的元素仅按需计算，但随后会被记忆（保存在内存中）。理论上可以是无限的。
    • mutable.LinearSeq
      • mutable.DoublyLinkedList -- 具有可变 prev、head (elem) 和 的列表尾部（下一个）。
      • mutable.LinkedList -- 具有可变 head (elem) 和 tail (下一步）。
      • mutable.MutableList -- 内部用于实现基于可变列表的类的类。
        • mutable.Queue、mutable.QueueProxy -- 针对 FIFO（先进先出）操作进行优化的数据结构。
        • mutable.QueueProxy -- mutable.Queue 的代理。
  • SeqProxy、SeqView、SeqForwarder
  • immutable.Seq
    • immutable.Queue -- 实现 FIFO 优化（先进先出）数据结构的类。 可变和不可变队列没有共同的超类。
    • immutable.Stack -- 实现 LIFO 优化（后进先出）数据结构的类。两个mutable immutable 堆栈没有共同的超类。
    • immutable.Vector -- ?
    • scala.xml.NodeSeq -- 扩展immutable.Seq的专用 XML 类。
    • immutable.IndexedSeq -- 如上所示。
    • immutable.LinearSeq -- 如上所示。
  • mutable.ArrayStack -- 使用数组实现 LIFO 优化数据结构的类。据说比普通堆栈快得多。
  • mutable.Stack、mutable.SynchronizedStack -- 实现 LIFO 优化数据结构的类。
  • mutable.StackProxy -- mutable.Stack 的 Proxy..
  • 可变的.Seq
    • mutable.Buffer -- 可以通过追加、前置或插入新成员来更改的元素序列。
      • mutable.ArrayBuffer -- mutable.Buffer 类的实现，具有用于追加、更新和随机访问操作的恒定摊销时间。它有一些专门的子类，例如NodeBuffer。
      • mutable.BufferProxy、mutable.SynchronizedBuffer。
      • mutable.ListBuffer -- 由列表支持的缓冲区。它提供恒定时间追加和前置，大多数其他操作都是线性的。
      • mutable.ObservableBuffer -- 一个mixin特征，当混合到Buffer时，通过Publisher< /code> 接口。
      • mutable.IndexedSeq -- 如上所示。
      • mutable.LinearSeq -- 如上所示。

    


  


集合

• set - 集合是一个集合，其中最多包含任何对象之一。
  • bitset - 一组作为bitset存储的整数。
    • immutable.bitset
    • mutable.bitset
  • sortedset - 订购元素的集合。
    • 不变。SortedSet
      • immutable.treeset - 基于树的sortedset的实现。
  • setProxy - 代理 set> set。
  • 不成熟的
    • immutable.hashset - 基于元素hashing的set> set>的实现。
    • immutable.listset - 基于列表的set>的实现。
    • 存在其他集合类，以提供从0到4个元素的集合的优化实现。
    • immutable.setproxy - 代理 for Inmundable SET。

    。


  


  • Mutable.set

    • mutable.hashset - 基于元素hashing的set> set>的实现。

    


    • Mutable.MmutablesEtadaptor - 从不变的 set set。
    • linkedhashset - 基于列表的Set>的实现。
    • observableset - a mixin 特征，当与set set混合时，通过Publisher 接口。
    • setProxy - 代理 set> set。
    • synchronizedset - a mixin 特征，当与set set混合时，通过Publisher 接口。

    


  


---

• 为何存在类似类（例如traversablele），

这是为了实现最大代码重用。类似的类别完成了具有特定结构（可遍历，地图等）类的混凝土通用实现。然后，旨在进行一般消费的类，然后覆盖可以选择的选定方法。

• （例如list.companion）

类的构建器，即知道如何以map，可以使用的方式来使用该类实例的对象，即由伴随对象中的方法创建。因此，为了构建类型X的对象，我需要从X的伴侣对象中获取该构建器。不幸的是，在Scala中，从类X到Object X中没有办法。 X，companion的每个实例中定义的方法，它返回X类的伴随对象。

尽管在普通程序中可能有某种用途，但其目标是在集合库中启用代码重用。

• 我怎么知道在给定点的范围中有什么隐式对象，

您不应该关心这一点。它们是隐含的，因此您无需弄清楚如何使其起作用。

这些隐含物存在是为了使集合上的方法在父类中定义，但仍返回相同类型的集合。例如，map方法是在traversablelike上定义的，但是如果您在list list上使用了list list 代码>返回。