73

继我喘不过气来的困惑之后，有哪些很好的资源可以解释新的Scala 2.8集合库是如何构建的。我有兴趣找到一些有关以下内容如何组合在一起的信息：

  • 集合类/特征本身（例如List，Iterable）
  • 为什么存在Like类（例如TraversableLike）
  • 伴随方法的用途（例如List.companion）
  • 我如何知道implicit在给定点的范围内有哪些对象
4

1 回答 1

188

前言

Martin Odersky的2.8 合集演练应该是您的第一个参考。它还补充了建筑笔记，这对于那些想要设计自己的收藏品的人来说将特别感兴趣。

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

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

我将选择性地引用论文中的内容，并补充我的一些想法。还有一些图像，由 Matthias 在 decodedified.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和。请注意，没有，因为任何支持并行访问的集合都能够支持更强的特征。它也没有序列层次结构中存在的一些更专业的特征。整个层次结构都在目录下。ParMapParSetParTraversableParIterablescala.collection.parallel

实现并行集合的类也不同，ParHashMap包括ParHashSet可变和不可变并行集合，ParRange以及ParVector实现immutable.ParSeq和ParArray实现mutable.ParSeq。

还存在另一个层次结构，它反映了串行和并行集合的特征，但带有前缀Gen: GenTraversable、GenIterable、GenSeq和. 这些特征是并行和串行集合的父母。这意味着采用 a 的方法无法接收并行集合，但采用 a 的方法预计可用于串行和并行集合。GenMapGenSetSeqGenSeq

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

使用并行集合

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

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

不要混淆seq，它将集合转换为非并行集合，与toSeq，它返回Seq从集合元素创建的 a 。调用toSeq并行集合将返回一个ParSeq，而不是串行集合。

主要特征

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

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

特征 TraversableOnce

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

这种限制使得集合和Iterator. 这使得使用 anIterator但不使用Iterator-specific 方法的方法实际上能够使用任何集合，加上迭代器，如果重写为 accept TraversableOnce。

因为TraversableOnce统一了集合和迭代器，所以它没有出现在前面的图中，它们只关心集合。

特征可遍历

集合层次结构的顶部是 trait Traversable。它唯一的抽象操作是

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

该操作旨在遍历集合的所有元素，并将给定的操作 f 应用于每个元素。该应用程序仅针对其副作用进行；实际上 f 的任何函数结果都会被 foreach 丢弃。

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

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

特征可迭代

此 trait 声明了一个抽象方法iterator，该方法返回一个迭代器，该迭代器一个一个地产生所有集合的元素。中的foreach方法Iterable是根据 来实现的iterator。的子类Iterable通常使用直接实现覆盖 foreach 以提高效率。

ClassIterable还向 中添加了一些不常用的方法Traversable，只有在 aniterator可用的情况下才能有效地实现。它们总结如下。

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方法，三个都实现了trait，但在每种情况下PartialFunction的含义是不同的。apply

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

下面的列表可能会有所改进。发表评论并提出建议，我会修复它。

基类和特征

  • Traversable-- 基本集合类。可以只用foreach.
    • TraversableProxy- 的代理Traversable。只需指向self真正的收藏。
    • TraversableView-- 带有一些非严格方法的 Traversable。
    • TraversableForwarder-- 将大多数方法转发到underlying, toString, hashCode, equals,stringPrefix和所有创建相同类型的新可迭代对象的调用newBuilder。view
    • mutable.Traversable和immutable.Traversable-- 与 相同Traversable，但限制集合类型。
    • 存在其他特殊情况Iterable类，例如MetaData。
    • IterableIterator--可以为其创建an 的集合（通过iterator）。
      • IterableProxy, IterableView,mutable和immutable.Iterable.
  • Iterator-- 不是 . 的后代的特征Traversable。定义next和hasNext。
    • CountedIterator-- 一个Iterator定义count，它返回到目前为止看到的元素。
    • BufferedIterator-- 定义head，它返回下一个元素而不使用它。
    • 存在其他特殊情况Iterator类，例如Source。

地图

  • Map-- 一个Iterableof Tuple2，它还提供了在给定键（元组的第一个元素）的情况下检索值（元组的第二个元素）的方法。也延伸PartialFunction。
    • MapProxy-Proxy一个Map。
    • DefaultMap-- 实现一些Map抽象方法的特征。
    • SortedMap--Map其键已排序 的 A。
      • immutable.SortMap
        • immutable.TreeMap- 一个实现immutable.SortedMap.
    • immutable.Map
      • immutable.MapProxy
      • immutable.HashMap--immutable.Map通过密钥散列实现的类。
      • immutable.IntMap-- 一个immutable.Map专门为Int键实现的类。使用基于键的二进制数字的树。
      • immutable.ListMap--immutable.Map通过列表实现的类。
      • immutable.LongMap-- 一个immutable.Map专门为Long键实现的类。见IntMap。
      • 还有针对特定数量的元素进行了优化的其他类。
    • mutable.Map
      • mutable.HashMap--mutable.Map通过密钥散列实现的类。
      • mutable.ImmutableMapAdaptor-mutable.Map从现有immutable.Map.
      • mutable.LinkedHashMap——？
      • mutable.ListMap--mutable.Map通过列表实现的类。
      • mutable.MultiMap-- 为每个键接受多个不同值的类。
      • mutable.ObservableMap-- 一个mixin，当与 a 混合时Map，通过Publisher接口向观察者发布事件。
      • mutable.OpenHashMap-- 基于开放散列算法的类。
      • mutable.SynchronizedMap-- 一个mixin，它应该与 a 混合Map以提供一个带有同步方法的版本。
      • mutable.MapProxy.

序列

  • Seq-- 一系列元素。一种假设是明确定义的大小和元素重复。也延伸PartialFunction。
    • IndexedSeq-- 支持 O(1) 元素访问和 O(1) 长度计算的序列。
      • IndexedSeqView
      • immutable.PagedSeq--IndexedSeq通过构造函数传递的函数按需生成元素的实现。
      • immutable.IndexedSeq
        • immutable.Range-- 一个定界的整数序列，在低端闭合，在高端打开，并带有一个台阶。
          • immutable.Range.Inclusive-- ARange也关闭了高端。
          • immutable.Range.ByOne--Range步长为 1的 A。
        • immutable.NumericRange- 一个更通用的版本，Range它适用于任何Integral.
          • immutable.NumericRange.Inclusive, immutable.NumericRange.Exclusive.
          • immutable.WrappedString, immutable.RichString-- 允许将 aString视为 a 的包装器Seq[Char]，同时仍保留String方法。我不确定它们之间有什么区别。
      • mutable.IndexedSeq
        • mutable.GenericArray--Seq基于 - 的类数组结构。请注意，“类”Array是 Java 的Array，与其说是类，不如说是一种内存存储方法。
        • mutable.ResizableArray-- 基于可调整大小数组的类使用的内部类。
        • mutable.PriorityQueue, mutable.SynchronizedPriorityQueue-- 实现优先队列的类 -- 元素根据Ordering第一个和最后排队的顺序出队的队列。
        • mutable.PriorityQueueProxyProxy-- a的摘要PriorityQueue。
    • LinearSeqisEmpty-- 线性序列的特征，对于head和具有有效时间tail。
      • immutable.LinearSeq
        • immutable.List-- 一个不可变的、单链接的列表实现。
        • immutable.Stream-- 一个懒惰的列表。它的元素仅按需计算，但随后被记忆（保存在内存中）。它理论上可以是无限的。
      • mutable.LinearSeq
        • mutable.DoublyLinkedList-- 带有可变prev、head( elem) 和tail( next) 的列表。
        • mutable.LinkedList-- 带有可变head( elem) 和tail( next) 的列表。
        • mutable.MutableList-- 内部用于实现基于可变列表的类的类。
          • mutable.Queue, mutable.QueueProxy-- 针对 FIFO（先进先出）操作优化的数据结构。
          • mutable.QueueProxy-Proxy一个mutable.Queue。
    • SeqProxy, SeqView,SeqForwarder
    • immutable.Seq
      • immutable.Queue-- 实现 FIFO 优化（先进先出）数据结构的类。mutable和immutable队列没有共同的超类。
      • immutable.Stack-- 一个实现 LIFO 优化（后进先出）数据结构的类。mutable immutable两个堆栈没有共同的超类。
      • immutable.Vector——？
      • scala.xml.NodeSeq- 扩展的专用 XML 类immutable.Seq。
      • immutable.IndexedSeq——如上所见。
      • immutable.LinearSeq——如上所见。
    • mutable.ArrayStack-- 使用数组实现 LIFO 优化数据结构的类。据说比普通堆栈快得多。
    • mutable.Stack, mutable.SynchronizedStack-- 实现 LIFO 优化数据结构的类。
    • mutable.StackProxy--Proxy一个mutable.Stack..
    • mutable.Seq
      • mutable.Buffer-- 可以通过追加、前置或插入新成员来更改的元素序列。
        • mutable.ArrayBuffer--mutable.Buffer类的实现，对于追加、更新和随机访问操作具有恒定的摊销时间。它有一些专门的子类，例如NodeBuffer.
        • mutable.BufferProxy, mutable.SynchronizedBuffer.
        • mutable.ListBuffer-- 由列表支持的缓冲区。它提供恒定时间追加和前置，大多数其他操作是线性的。
        • mutable.ObservableBuffer-- 一个mixin特征，当它与 a 混合时Buffer，通过Publisher接口提供通知事件。
        • mutable.IndexedSeq——如上所见。
        • mutable.LinearSeq——如上所见。

套装

  • Set-- 集合是最多包含任何对象之一的集合。
    • BitSet-- 存储为位集的一组整数。
      • immutable.BitSet
      • mutable.BitSet
    • SortedSet-- 一个集合，其元素是有序的。
      • immutable.SortedSet
        • immutable.TreeSet--SortedSet基于树的 a 的实现。
    • SetProxy-Proxy一个Set。
    • immutable.Set
      • immutable.HashSet--Set基于元素散列的实现。
      • immutable.ListSet--Set基于列表的实现。
      • 存在额外的集合类来为从 0 到 4 个元素的集合提供优化的实现。
      • immutable.SetProxy- AProxy表示不可变的Set.
    • mutable.Set
      • mutable.HashSet--Set基于元素散列的实现。
      • mutable.ImmutableSetAdaptorSet-从不可变实现可变的类Set。
      • LinkedHashSet--Set基于列表的实现。
      • ObservableSet-- 一个mixin特征，当它与 a 混合时Set，通过Publisher接口提供通知事件。
      • SetProxy-Proxy一个Set。
      • SynchronizedSet-- 一个mixin特征，当它与 a 混合时Set，通过Publisher接口提供通知事件。
  • 为什么存在 Like 类（例如 TraversableLike）

这样做是为了实现最大的代码重用。具有特定结构（可遍历、映射等）的类的具体通用实现在 Like 类中完成。然后，用于一般消费的类会覆盖可以优化的选定方法。

  • 伴随方法的用途（例如 List.companion）

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

虽然这种方法在普通程序中可能会有一些用途，但它的目标是在集合库中启用代码重用。

  • 我如何知道在给定点的范围内有哪些隐式对象

你不应该关心这个。它们是隐含的，因此您无需弄清楚如何使其工作。

存在这些隐式以使集合上的方法能够在父类上定义，但仍返回相同类型的集合。例如，该map方法定义在 上TraversableLike，但如果您在 a 上使用，List您会得到List回报。

于 2009-11-12T19:36:26.423 回答