Scala 中的集合(三):实现一个新的 Collection 类
Scala 中的 collection 库是符合 DRY 设计原则的典范,它包含了大量通用的集合操作 API,由此我们可以基于标准库,轻松构建出一个强大的新集合类型。
本文将介绍「如何实现一个新集合类」,在开始之前,我们先来了解下 Scala 2.8 版本后的集合结构设计。
集合通用设计
看过 Scala 中的集合(一) 的朋友已经知道,Scala 的集合类系统地区分了可变的和不可变的集合,它们存在于以下三个包中:
- scala.collection
- scala.collection.mutable
- scala.collection.immutable
然而,以上所有的集合都继承了两个相同的特质 — Traversable
和 Iterable
(后者继承了前者)。
Traversable
Traversable
是集合类最高级的特性,它具有一个抽象方法:
1 | def foreach[U](f: Elem => U) |
顾名思义,foreach
方法用于遍历集合类的所有元素,然后进行指定的操作。Iterable
继承了 Traversable
,也实现了 foreach
方法,继而所有继承了 Iterable
的集合类同时也获得了一个 foreach
的基础版本。
很多集合操作都是基于 foreach
实现,因此它的性能非常关键。一些 Iterable
子类覆写了这个方法的实现,从而获得了符合不同集合特性的优化。
那么,常见的集合类型(如 Seq
) 是如何实现通用操作的呢(如 map
)?
原来,Traversable
除了唯一的抽象方法以外,还包含了大量通用的集合操作方法。
Scala 文档对这些操作方法进行了归类,如下所示:
分类 | 方法 |
---|---|
抽象方法 | foreach |
相加 | ++ |
Map | map / flatMap / collect |
集合转换 | toArray / toList / toIterable / toSeq / toIndexedSeq / toStream / toSet / toMap |
拷贝 | copyToBuffer / copyToArray |
size 信息 | isEmpty / nonEmpty / size / hasDefiniteSize |
元素检索 | head / last / headOption / lastOption / find |
子集合检索 | tail / init / slice / take / drop / takeWhilte / dropWhile / filter / filteNot / withFilter |
拆分 | splitAt / span / partition / groupBy |
元素测试 | exists / forall / count |
折叠 | foldLeft / foldRight / /: / :\ / reduceLeft / reduceRight |
特殊折叠 | sum / product / min / max |
字符串转化 | mkString / addString / stringPrefix |
视图生成 | view |
由此,一个集合仅需定义 foreach
方法,以上所有其它方法都可以从 Traversable
继承。
Iterable
Scala 当前版本的 Iterable
设计略显尴尬,它实现了 Traversable
,也同时被其它所有集合实现。然而事实上这并不是一个好的设计,原因如下:
Traversable
具有隐式的行为假设,它在公开的签名中是不可见的,容易导致 API 出错- 遍历一个
Traversable
比Iterable
性能要差 - 所有继承了
Traversable
的数据类型,无不接受Iterator
的实现,前者显得多余
详情参见 @Alexelcu 的文章 — Why scala.collection.Traversable Is Bad Design
因此,正在进行的 Scala collection redesign 项目也已经抛弃了 Traversable
。
然而,这并不妨碍我们研究 Iterable
中的通用方法,它们也在 collection-strawman 中被保留,如下所示:
分类 | 方法 |
---|---|
抽象方法 | iterator |
其他迭代器 | grouped / sliding |
子集合 | takeRight / dropRight |
拉链操作 | zip / zipAll |
比对 | sameElements |
Builder 类
几乎所有的集合操作都由「遍历器」和「构建器」完成,在了解以上内容之后,我们再来了解下如何构建一个集合类型。在当前的 Scala 中,是利用一个 Builder
类实现的。
1 | package scala.collection.mutable |
注意类型参数,Elem
表示元素的类型(如 Int
),To
表示集合的类型(如 Array[Int]
)。
此外:
+=
可以增加元素result
返回一个集合clear
把集合重置为空状态mapResult
返回一个Builder
,拥有新的集合类型
我们来看下Builder
如何结合 foreach
方法,实现常见的 filter
操作:
1 | def filter(p: Elem => Boolean): Repr = { |
So easy!没什么挑战。
我们再来考虑下 map
,它与 filter
的差异之一,在于前者可以返回一个「元素类型不同」的集合。如:1
2scala > List(1, 2, 3).map(_.toString)
res0: List[String] = List(1, 2, 3)
这下有难度了,仅凭 Builder
和 foreach
组合,似乎完成不了这个任务。
于是,我们决定看下 TraversableLike
中 map
的 Scala 源码实现:
1 | def map[B, That](f: Elem => B) |
当前 Scala 集合中,???Like 命名的特质是 ??? 特质的实现。
一个大发现 — 当前版本的 Scala 原来是利用 CanBuildFrom
类型来解决如何集合「类型转换」的问题。
1 | package scala.collection.generic |
这种利用 TypeClass 技术 — 采用隐式转换来获得扩展的方式,显得强大且灵活,但在新手看来会比较怵。
通过字面的理解,我们知晓 — From
代表当前的集合类型,Elem
代表元素类型,To
代表目标集合的类型。
所以我们可以如此解读 CanBuildFrom
:「有这么一个方法,由给定的 From 类型的集合,使用 Elem 类型,建立 To 类型的集合」。
新集合类实现
通过以上的介绍,大家对 Scala 的集合结构设计有了整体的认识,现在开始来实现一个新的集合类。
以下例子来自 Scala 文档,细节有调整,精简。
假设我们需要设计一套新的「密文编码序列」,由最基本的 A、B、C、D 四个字母组成。定义类型如下:
1 | abstract class Base |
显然,我们可以使用 Seq[Base]
来表示一个密文序列,但由于这个密文可能很长,并且 Base 类型只有 4 种可能,我们可以通过「位计算」的方式来开发一种压缩过的集合,它是 Seq[Base]
的子类。
以下将采用伴生对象的方式来创建
Message
实例,可参考 Builder 创建者模式
1 | import collection.IndexedSeqLike |
测试:
1 | val message = Message(A, B, B ,D) |
- Message 很好地获得了
IndexedSeq
的通用集合方法,如length
、last
- 但
take
方法并没有获得预期的Message(A, B, B)
,而是Vector(A, B, B)
改进一下:
1 | def take(count: Int): Message = Message.fromSeq(super.take(count)) |
- 确实可以解决
take
返回动态类型的问题,可得到Message(A, B, B)
的结果 - 然而集合除了
take
外还有大量通用方法,覆写每个方法的策略不可取
正确的姿势
1 | import collection.mutable.{Builder, ArrayBuffer} |
在伴生类中重新实现 newBuilder
:
1 | final class Message private (val groups: Array[Int], val length: Int) |
改写伴生对象:
1 | object Message { |
此外,如前文提到,我们还可以重新实现 foreach
方法来提高该集合类的效率:
1 | final class Message private (val groups: Array[Int], val length: Int) |
以上,我们便构建了一个新的集合类型 Message
,通过极少的代码,拥有了强大的通用集合特性。
我们将在下一篇文章中进一步介绍 CanBuildFrom
,几乎确定地说,它也会在未来的 Scala 版本中被新的方案替代。