Scala 2.8系列设计教程-Java 学习之路

继my breathless confusion之后，有哪些好资源可以解释新的Scala 2.8 集合库是如何构建的 . 我有兴趣找到以下如何融合在一起的一些信息：

集合类/特征本身（例如 List ， Iterable ）
为什么存在Like类（例如 TraversableLike ）
配套方法的用途（例如 List.companion ）
我怎么知道 implicit 对象在给定点的范围内

1 回答

188
前言

Martin Odersky有一个2.8 collection walk-through应该是你的第一个参考 . 它也得到了architectural notes的补充，对于那些想要设计自己的系列的人来说，这将是特别有趣的 .

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

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

我将从论文中有选择地引用，并与我的一些想法相辅相成 . 还有一些图像，由Matthias在decodified.com生成，原始的SVG文件可以找到here .

集合类/特征本身

实际上，集合有三个特征层次结构：一个用于可变集合，一个用于不可变集合，另一个不对集合做任何假设 .

's also a distinction between parallel, serial and maybe-parallel collections, which was introduced with Scala 2.9. I'将在下一节讨论它们 . 本节中描述的层次结构仅指非并行集合 .

下图显示了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 实现 immutable.ParSeq 和 ParArray 实现 mutable.ParSeq .

还存在另一个层次结构，它反映了串行和并行集合的特征，但带有前缀 Gen ： GenTraversable ， GenIterable ， GenSeq ， 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 但不使用 Iterator 特定方法的方法实际上可以使用任何集合，加上迭代器，如果重写为接受 TraversableOnce .

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

Trait Traversable

在集合层次结构的顶部是trait 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 .

The listing below may be improved. Leave a comment with suggestions and I'll fix it.

基类和特征
- Traversable - 基本集合类 . 可以用 foreach 实现 .
- TraversableProxy - Traversable 的代理 . 只需将 self 指向真实集合即可 .
- TraversableView - 带有一些非严格方法的Traversable .
- TraversableForwarder - 将大多数方法转发到 underlying ，但 toString ， hashCode ， equals ， stringPrefix ， newBuilder ， view 除外，所有调用都创建了相同类型的新可迭代对象 .
- mutable.Traversable 和 immutable.Traversable - 与 Traversable 相同，但限制了集合类型 .
- 存在其他特殊情况 Iterable 类，例如 MetaData .
- Iterable - 可以创建 Iterator 的集合（通过 iterator ） .
- IterableProxy ， IterableView ， mutable 和 immutable.Iterable .
- Iterator - 不是 Traversable 的后代的特征 . 定义 next 和 hasNext .
- CountedIterator - Iterator 定义了 count ，它返回到目前为止看到的元素 .
- BufferedIterator - 定义 head ，它返回下一个元素而不使用它 .
- 存在其他特殊情况 Iterator 类，例如 Source .
Map
- Map - Iterable Tuple2 ，它还提供了在给定键（元组的第一个元素）的情况下检索值（元组的第二个元素）的方法 . 也扩展了 PartialFunction .
- MapProxy - Proxy 表示 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 .
- 还有针对特定数量的元素优化的其他类 .
- mutable.Map
- mutable.HashMap - 通过密钥散列实现 mutable.Map 的类 .
- mutable.ImmutableMapAdaptor - 从现有 immutable.Map 实现 mutable.Map 的类 .
- mutable.LinkedHashMap - ？
- mutable.ListMap - 通过列表实现 mutable.Map 的类 .
- mutable.MultiMap - 为每个键接受多个不同值的类 .
- mutable.ObservableMap - mixin，当与 Map 混合时，通过 Publisher 接口向观察者发布事件 .
- mutable.OpenHashMap - 基于开放哈希算法的类 .
- mutable.SynchronizedMap - 应与 Map 混合的mixin，以提供具有同步方法的版本 .
- mutable.MapProxy .
序列
- Seq - 一系列元素 . 一个假设一个明确定义的大小和元素重复 . 也扩展 PartialFunction .
- IndexedSeq - 支持O（1）元素访问和O（1）长度计算的序列 .
- IndexedSeqView
- immutable.PagedSeq - IndexedSeq 的实现，其中元素由通过构造函数传递的函数按需生成 .
- immutable.IndexedSeq
- immutable.Range - 以整数分隔的整数序列，在下端封闭，在高端打开，并带有一个步长 .
- immutable.Range.Inclusive - Range 也在高端关闭 .
- immutable.Range.ByOne - Range ，其步骤为1 .
- immutable.NumericRange - Range 的更通用版本，适用于任何 Integral .
- immutable.NumericRange.Inclusive ， immutable.NumericRange.Exclusive .
- immutable.WrappedString ， immutable.RichString - 能够将 String 视为 Seq[Char] ，同时仍然保留 String 方法的包装器 . 我不确定它们之间有什么区别 .
- mutable.IndexedSeq
- mutable.GenericArray - 基于 Seq 的类似数组的结构 . 请注意"class" 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 ）和 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 - 扩展 immutable.Seq 的专用XML类 .
- immutable.IndexedSeq - 如上所示 .
- immutable.LinearSeq - 如上所示 .
- mutable.ArrayStack - 使用数组实现LIFO优化数据结构的类 . 据称比正常堆栈快得多 .
- mutable.Stack ， mutable.SynchronizedStack - 实现LIFO优化数据结构的类 .
- mutable.StackProxy - Proxy for mutable.Stack ..
- mutable.Seq
- mutable.Buffer - 可以通过追加，添加或插入新成员来更改的元素序列 .
- mutable.ArrayBuffer - mutable.Buffer 类的实现，具有用于追加，更新和随机访问操作的常量摊销时间 . 它有一些专门的子类，例如 NodeBuffer .
- mutable.BufferProxy ， mutable.SynchronizedBuffer .
- mutable.ListBuffer - 由列表支持的缓冲区 . 它提供恒定的时间附加和前置，大多数其他操作是线性的 .
- mutable.ObservableBuffer - mixin特性，当混合到 Buffer 时，通过 Publisher 接口提供通知事件 .
- mutable.IndexedSeq - 如上所示 .
- mutable.LinearSeq - 如上所示 .
集
- Set - 集合是一个集合，最多包含任何一个对象 .
- BitSet - 存储为bitset的一组整数 .
- immutable.BitSet
- mutable.BitSet
- SortedSet - 元素所在的集合订购 .
- immutable.SortedSet
- immutable.TreeSet - 基于树的 SortedSet 的实现 .
- SetProxy - Proxy for Set .
- immutable.Set
- immutable.HashSet - 基于元素散列的 Set 实现 .
- immutable.ListSet - 基于列表的 Set 实现 .
- 存在其他集合类，以便为0到4个元素的集合提供优化的实现 .
- immutable.SetProxy - Proxy 表示不可变的 Set .
- mutable.Set
- mutable.HashSet - 基于元素散列的 Set 实现 .
- mutable.ImmutableSetAdaptor - 从不可变的 Set 实现可变 Set 的类 .
- LinkedHashSet - 基于列表的 Set 实现 .
- ObservableSet - mixin特性，当与 Set 混合时，通过 Publisher 接口提供通知事件 .
- SetProxy - Proxy 表示 Set .
- SynchronizedSet - mixin特性，当与 Set 混合时，通过 Publisher 接口提供通知事件 .
- 为什么存在Like类（例如TraversableLike）
这样做是为了实现最大程度的代码重用 . 具有特定结构的类（可遍历，映射等）的具体通用实现在Like类中完成 . 然后，用于一般消费的类覆盖可以优化的选定方法 .
- 配套方法的用途（例如List.companion）
类的构建器，即知道如何以可由 map 等方法使用的方式创建该类的实例的对象，是由伴随对象中的方法创建的 . 因此，为了构建X类型的对象，我需要从X的伴随对象中获取该构建器 . 不幸的是，在Scala中，没有办法从类X到对象X.因此，有在每个X， companion 实例中定义的方法，它返回类X的伴随对象 .

虽然在普通程序中可能会使用这种方法，但其目标是在集合库中启用代码重用 .
- 我如何知道给定点的隐式对象在范围内
你不应该关心那个 . 它们是隐含的，因此您无需弄清楚如何使其工作 .

这些隐含存在使得集合上的方法可以在父类上定义，但仍然返回相同类型的集合 . 例如， map 方法在 TraversableLike 上定义，但如果您在 List 上使用，则会返回 List .
回复于 2024-05-03T05:31:49+08:00

Scala 2.8系列设计教程

1 回答

前言

集合类/特征本身

并行集合

使用并行集合

主要特征

Trait TraversableOnce

Trait Traversable

Trait Iterable

其他特征

基类和特征

Map

序列

集

相关问题