Scala 2.8集合设计教程

继 我无法呼吸的困惑之后，有哪些好的资源可以解释新的 斯卡拉 2.8集合库是如何构建的。我有兴趣找到一些关于如何将以下内容组合在一起的信息:

  • 集合类/trait 本身(例如 List，Iterable)
  • 为什么存在 喜欢类(例如 TraversableLike)
  • 配套方法的用途(例如 List.companion)
  • 我如何知道什么 implicit对象在给定的点范围
19906 次浏览
小开
最佳答案

前言

有一个 2.8版收藏的马丁奥德斯基，这可能是你的第一个参考。它还补充了 建筑笔记，这将是特别感兴趣的那些谁想要设计自己的收藏品。

这个答案的其余部分是在这样的东西存在之前写的(事实上，在2.8.0本身发布之前)。

你可以找到一篇关于它的论文作为 Scala SID # 3。对于那些对 Scala 2.7和2.8之间的区别感兴趣的人来说，这个领域的其他论文也应该是有趣的。

我将有选择地引用这篇文章，并补充我的一些想法。还有一些由 Matthias 在 decdified.com 上生成的图像，原始的 SVG 文件可以在 给你中找到。

集合类/特性本身

实际上，集合的 trait 有三个层次结构: 一个用于可变集合，一个用于不可变集合，还有一个不对集合做任何假设。

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

下图显示了 Scala 2.8引入的非特定层次结构: General collection hierarchy

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

不可变层次结构图: Immutable collection hierarchy

可变层次结构图: Mutable collection hierarchy

图例:

Graph legend

下面是对集合层次结构的简化 ASCII 描述，适用于那些看不到图像的用户。

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

平行收藏

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

然而，由于直到那时所有的集合都是串行的，所以许多使用它们的算法都假定并依赖于它们是 曾经是串行的这一事实。提供给具有这种假设的方法的并行集合将会失败。由于这个原因，上一节 要求串行处理中描述的所有层次结构。

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

并行集合层次结构对于 trait 有相同的名称，但是在 Par之前有 ParIterable、 ParSeq、 ParMap和 ParSet。注意，没有 ParTraversable，因为任何支持并行访问的集合都能够支持更强的 ParIterable特性。它也没有串行层次结构中出现的一些更加专门化的特性。整个层次结构位于 scala.collection.parallel目录下。

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

另一个层次结构也存在，它反映了串行和并行集合的特征，但前缀为 Gen: GenTraversable、 GenIterable、 GenSeq、 GenMap和 GenSet。这些特性对于并行和串行集合都是 父母。这意味着采用 Seq的方法不能接收并行集合，但是采用 GenSeq的方法可以同时处理串行集合和并行集合。

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

使用并行集合

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

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

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

主要特征

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

在接下来的小节中，我将简要描述这些主要特征以及它们背后的思想。

特征可穿越一次

这个 trait 非常类似于下面描述的 trait Traversable，但是有一个限制，那就是您只能使用它 一次。也就是说，对 TraversableOnce梅调用的任何方法都会使其无法使用。

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

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

特征可通过

在 收藏品层次结构的顶部是 trait Traversable，它唯一的抽象操作是

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

该操作意味着遍历集合中的所有元素，并将给定的操作 f 应用于每个元素 应用程序只是为了它的副作用而完成; 实际上，f 的任何函数结果都被 Foreach.

可遍历对象可以是有限的，也可以是无限的 方法 hasDefiniteSize指示一个集合是否可能是 如果 hasDefiniteSize返回 true，则该集合当然是有限的。如果返回 false，则 集合还没有被完全阐述，所以它可能是无限的或有限的。

这个类定义了可以根据 foreach(超过40个)有效实现的方法。

可改变的特质

这个 trait 声明了一个抽象方法 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指向真正的集合。
    • 一些非严格方法的可遍历性。
    • TraversableForwarder——将大多数方法转发到 underlying，除了 toString、 hashCode、 equals、 stringPrefix、 newBuilder、 view以及创建一个新的同类可迭代对象的所有调用。
    • mutable.Traversable和 immutable.Traversable——与 Traversable相同，但限制了集合类型。
    • 还存在其他特殊情况下的 Iterable类，例如 MetaData。
    • Iterable——可为其创建 Iterator(通过 iterator)的集合。
      • IterableProxy，IterableView，mutable和 immutable.Iterable。
  • 不是 Traversable后代的性状。定义 next和 hasNext。
    • CountedIterator——定义 count的 Iterator，它返回到目前为止看到的元素。
    • 定义 head，它返回下一个元素而不使用它。
    • 还存在其他特殊情况下的 Iterator类，例如 Source。

地图

  • Map—— Tuple2的 Iterable，它还提供方法来检索给定键(元组的第一个元素)的值(元组的第二个元素)。也扩展 PartialFunction。
    • MapProxy-Proxy代表 Map。
    • DefaultMap——实现某些 Map抽象方法的特性。
    • SortedMap——键被排序的 Map。
        • immutable.TreeMap——实现 immutable.SortedMap的类。
      • immutable.MapProxy
      • immutable.HashMap——通过键哈希实现 immutable.Map的类。
      • immutable.IntMap——专门用于 Int键的实现 immutable.Map的类。使用基于键的二进制数的树。
      • immutable.ListMap——通过列表实现 immutable.Map的类。
      • immutable.LongMap——专门用于 Long键的实现 immutable.Map的类。参见 IntMap。
      • 还有为特定数量的元素优化的其他类。
      • mutable.HashMap——通过键哈希实现 mutable.Map的类。
      • mutable.ImmutableMapAdaptor——从现有的 immutable.Map实现 mutable.Map的类。
      • mutable.LinkedHashMap—— ？
      • mutable.ListMap——通过列表实现 mutable.Map的类。
      • mutable.MultiMap——为每个键接受多个不同值的类。
      • mutable.ObservableMap——当与 Map混合时，混音通过 Publisher接口向观察者发布事件。
      • mutable.OpenHashMap——基于开放哈希算法的类。
      • mutable.SynchronizedMap—— 混音应该与 Map混合以提供具有同步方法的 Map版本。
      • mutable.MapProxy.

序列

  • 元素序列。一个元素的大小和元素重复定义明确。也扩展了 PartialFunction。
    • IndexedSeq——支持 O (1)元素访问和 O (1)长度计算的序列。
      • IndexedSeqView
      • immutable.PagedSeq—— IndexedSeq的一种实现，其中元素是由通过构造函数传递的函数按需生成的。
        • immutable.Range——一个分隔的整数序列，在下端关闭，在高端打开，并有一个步骤。
          • immutable.Range.Inclusive—— Range也在高端关闭。
          • 步长为1的 Range。
        • immutable.NumericRange—— Range的一个更通用的版本，可以与任何 Integral协同工作。
          • immutable.NumericRange.Inclusive，immutable.NumericRange.Exclusive.
          • immutable.WrappedString，immutable.RichString——包装器，它能够将 String视为 Seq[Char]，同时仍然保留 String方法。我不知道他们之间有什么区别。
        • mutable.GenericArray——一种基于 Seq的类阵列结构。请注意，“ class”Array是 Java 的 Array，它更像是一个内存存储方法而不是类。
        • mutable.ResizableArray——基于可调整数组的类使用的内部类。
        • mutable.PriorityQueue，mutable.SynchronizedPriorityQueue——实现优先队列的类——元素首先按照 Ordering出队，最后按照排队顺序排队的队列。
        • mutable.PriorityQueueProxy—— PriorityQueue的摘要 Proxy。
    • 线性序列的一个特征，对于 isEmpty，head和 tail有效时间。
        • immutable.List——一个不可变的、单链接的列表实现。
        • immutable.Stream——一个懒惰列表。它的元素只是按需计算，但事后被制表(保存在内存中)。理论上可以是无限的。
        • 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.Queue——实现 FIFO 优化(先进先出)数据结构的类。mutable和 immutable队列没有公共的超类。
      • immutable.Stack——实现 LIFO 优化(后进先出)数据结构的类。两个 mutable immutable堆栈没有共同的超类。
      • immutable.Vector—— ？
      • scala.xml.NodeSeq——扩展 immutable.Seq的专用 XML 类。
      • 如上所示。
      • 如上所示。
    • mutable.ArrayStack——使用数组实现 LIFO 优化数据结构的类。据推测比普通堆栈快得多。
    • mutable.Stack，mutable.SynchronizedStack——实现 LIFO 优化数据结构的类。
    • mutable.StackProxy-Proxy代表 mutable.Stack。
      • mutable.Buffer——可以通过添加、预置或插入新成员来更改的元素序列。
        • mutable.ArrayBuffer—— mutable.Buffer类的一个实现，对于追加、更新和随机访问操作具有固定的摊销时间。它有一些专门的子类，比如 NodeBuffer。
        • mutable.BufferProxy，mutable.SynchronizedBuffer.
        • mutable.ListBuffer——由列表支持的缓冲区。它提供了常量时间附加和预置，其他大多数操作都是线性的。
        • mutable.ObservableBuffer——一种 混音特性，当它与 Buffer混合时，通过 Publisher接口提供通知事件。
        • 如上所示。
        • 如上所示。

布景

  • Set——集合是一个集合，它至多包含任何对象中的一个。
    • BitSet——作为位集存储的一组整数。
      • immutable.BitSet
      • mutable.BitSet
    • SortedSet——元素有序的集合。
        • immutable.TreeSet——基于树的 SortedSet实现。
    • SetProxy-Proxy代表 Set。
      • immutable.HashSet——基于元素散列的 Set实现。
      • immutable.ListSet——基于列表的 Set实现。
      • 存在其他集合类，以便为0到4个元素的集合提供优化的实现。
      • 不可变 Set的 Proxy。
      • mutable.HashSet——基于元素散列的 Set实现。
      • mutable.ImmutableSetAdaptor——从不可变的 Set实现可变的 Set的类。
      • LinkedHashSet——基于列表的 Set实现。
      • ObservableSet——一种 混音特性，当与 Set混合时，通过 Publisher接口提供通知事件。
      • SetProxy-Proxy代表 Set。
      • SynchronizedSet——一种 混音特性，当与 Set混合时，通过 Publisher接口提供通知事件。
  • 为什么存在 Like 类(例如 TraversableLike)

这样做是为了实现最大限度的代码重用。具有特定结构(可遍历、映射等)的类的具体 一般实现是在 Like 类中完成的。然后，用于一般使用的类将重写可优化的选定方法。

  • 伙伴方法的用途(例如 List.partners)

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

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

  • 我如何知道在给定点的作用域中有哪些隐式对象

你不应该关心这个。它们是隐式的，所以你不需要知道如何使它工作。

这些隐式的存在是为了使集合上的方法能够在父类上定义，但仍然返回相同类型的集合。例如，map方法是在 TraversableLike上定义的，但是如果您在 List上使用 map方法，您将得到返回的 List。


提交答案