Scala 2.8集合devise教程

接下来, 我不知所措地混淆了什么,一些很好的资源解释了如何构build新的Scala 2.8集合库。 我有兴趣find一些有关以下方面的信息:

  • 集合类/特性本身(例如ListIterable
  • 为什么Like类存在(例如TraversableLike
  • 伴随方法是什么(例如List.companion
  • 我怎么知道implicit对象在给定点的范围内

前言

马丁·奥德斯基(Martin Odersky)有一个2.8集合的漫步 ,可能是你的第一个参考。 它也与build筑笔记一起得到了补充,对于那些想要devise自己的藏品的人来说,这些笔记会特别感兴趣。

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

你可以find一个关于它的Scala SID#3的文章 。 对于那些对Scala 2.7和2.8之间的差异感兴趣的人,那个领域的其他论文也应该很有趣。

我会select性地引用这篇论文,并补充一些我的想法。 在decodified.com上也有一些由Matthias生成的图片,原始的SVG文件可以在这里find。

收集类/性状本身

实际上有三个集合的特征层次:一个是可变集合,一个是不可变集合,另一个是对集合没有任何假设。

在Scala 2.9中引入了并行,串行和可能并行收集之间的区别。 我将在下一节中讨论它们。 本节中描述的层次结构非平行集合

下图显示了Scala 2.8引入的非特定层次结构: 一般收集层次结构

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

不可变层次结构图 不可变的收集层次结构

可变层次图: 可变的集合层次结构

传说:

图例

下面是对收集层次结构的缩写ASCII描述,对于那些看不到图像的人来说。

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

平行集合

当Scala 2.9引入并行集合时,其中一个devise目标是尽可能无缝地使用它们。 用最简单的话来说,可以用一个并行(串行)集合取代一个并行(串行)集合,并立即获得好处。

然而,由于在此之前的所有集合都是串行的,所以许多使用它们的algorithm都假设并依赖于它们串行的。 用这种假设向方法提供的并行集合将会失败。 由于这个原因,上一节中描述的所有层次都要求串行处理

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

并行集合层次结构具有相同的特征名称,但前面带有ParParIterableParSeqParMapParSet 。 请注意,没有ParTraversable ,因为任何支持并行访问的集合都能够支持更强大的ParIterable特性。 它在串行层次结构中没有一些更专门化的特征。 这整个层次结构可以在scala.collection.parallel目录下find。

实现并行集合的类也不同, ParHashMapParHashSet用于可变和不可变并行集合, ParRangeParVector实现immutable.ParSeq ParArrayParArray实现mutable.ParSeq

还有另一种层次结构,它反映了串行和并行集合的特征,但带有前缀GenGenTraversableGenIterableGenSeqGenMapGenSet 。 这些特征是平行和连续收集的父母 。 这意味着采用Seq的方法不能接收并行集合,但是采用GenSeq的方法有望与串行和并行集合一起工作。

鉴于这些层次结构的方式,为Scala 2.8编写的代码与Scala 2.9完全兼容,并要求串行行为。 没有被重写,它不能利用并行集合,但所需的变化是非常小的。

使用并行集合

任何集合都可以通过调用其中的方法来转换为并行集合。 同样,通过调用seq方法,可以将任何集合转换为串行集合。

如果集合已经是所请求的types(并行或串行),则不会进行转换。 如果在并行集合上调用seq或者在串行集合上调用seq ,则会生成具有所请求特征的新集合。

不要混淆seq ,它将一个集合转换为一个非并行集合, toSeq返回一个由集合元素创build的Seq 。 在并行集合上调用toSeq将返回一个ParSeq ,而不是一个序列集合。

主要特征

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

在下面的小节中,我将简要介绍一下主要特征和背后的想法。

特质TraversableOnce

这个特性与下面介绍的特质Traversable非常相似,但是限制只能使用一次 。 也就是说,在TraversableOnce上调用的任何方法都可能使其无法使用。

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

由于TraversableOnce统一了集合和迭代器,因此它不会出现在前面的图中,这些图只关心集合。

Traitable Traversable

收集层次结构的顶部是特质Traversable 。 它唯一的抽象操作是

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

该操作是为了遍历集合的所有元素,并将给定的操作f应用于每个元素。 该应用程序只是为了副作用。 其实f的任何函数结果都是被foreach丢弃的。

可遍历的对象可以是有限的或无限的。 无限可遍历对象的一个​​例子是自然数Stream.from(0)的stream。 hasDefiniteSize方法指示集合是否可能是无限的。 如果hasDefiniteSize返回true,则集合当然是有限的。 如果它返回错误,集合还没有完全阐述,所以它可能是无限的或有限的。

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

特征Iterable

这个特征声明了一个抽象方法iterator ,它返回一个迭代器,它可以逐个生成所有集合的元素。 Iterableforeach方法是用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之后,有三个从它inheritance的基本特征: SeqSetMap 。 三种都有apply方法,三种都实现了PartialFunction特性,但是应用的含义各不相同。

我相信SeqSetMap的含义是直观的。 之后,这些类在特定的实现中分解,这些实现提供了关于性能的特定保证,以及由此产生的方法。 还有一些有进一步改进的特性,比如LinearSeqIndexedSeqSortedSet

下面的清单可能会有所改进。 留下评论的build议,我会解决它。

基础类和特征

  • Traversable – 基本集合类。 可以用foreach来实现。
    • TraversableProxy – 一个Traversable代理。 只要指出self的真实collections。
    • TraversableView – 一些非严格方法的Traversable。
    • TraversableForwarder – 将大多数方法转发到underlying ,除了toStringhashCodeequalsstringPrefixnewBuilderview和所有调用创build一个新的同类的可迭代对象。
    • mutable.Traversableimmutable.Traversable – 与Traversable相同,但限制集合types。
    • 其他特例Iterable类,如MetaData ,存在。
    • Iterable – 可以创buildIterator (通过iterator )的集合。
      • IterableProxyIterableViewmutableimmutable.Iterable
  • Iterator – 不是Traversable后裔。 定义nexthasNext
    • CountedIterator – 一个Iterator定义count ,返回到目前为止看到的元素。
    • BufferedIterator – 定义head ,它返回下一个元素而不消耗它。
    • 其他特殊的Iterator类,例如Source存在。

地图

  • Map – 一个Tuple2Iterable ,它也提供了获取给定一个键(元组的第一个元素)的值(元组的第二个元素)的方法。 还扩展了PartialFunction
    • MapProxyMapProxy
    • DefaultMap – 实现一些Map抽象方法的特征。
    • SortedMap – 按键sorting的Map
      • immutable.SortMap
        • immutable.TreeMap – 一个实现了immutable.SortedMap的类。
    • immutable.Map
      • immutable.MapProxy
      • immutable.HashMap – 通过密钥散列实现immutable.Map的类。
      • immutable.IntMap – 一个实现immutable.Map专用的immutable.IntMap的类。 使用基于键的二进制数字的树。
      • immutable.ListMap – 通过列表实现immutable.Map的类。
      • immutable.LongMap – 一个实现了Long键专用的immutable.LongMap的类。 请参阅IntMap
      • 还有一些为特定数量的元素进行了优化的类。
    • mutable.Map
      • mutable.HashMap – 通过密钥散列实现mutable.Map的类。
      • mutable.ImmutableMapAdaptor – 从现有的immutable.Map实现mutable.ImmutableMapAdaptor的类。
      • mutable.LinkedHashMap – ?
      • mutable.ListMap – 通过列表实现mutable.Map的类。
      • mutable.MultiMap – 为每个键接受多个不同值的类。
      • mutable.ObservableMap – 一个mixin ,当它和Map混合在一起时,通过Publisher接口将事件发布给观察者。
      • mutable.OpenHashMap – 一个基于开放哈希algorithm的类。
      • mutable.SynchronizedMap – 一个mixin ,它应该和一个Map混合,为它提供一个带有同步方法的版本。
      • mutable.MapProxy

序列

  • Seq – 一系列元素。 一个假定一个明确的大小和元素重复。 还扩展了PartialFunction
    • IndexedSeq – 支持O(1)元素访问和O(1)长度计算的序列。
      • IndexedSeqView
      • immutable.PagedSeqIndexedSeq一个实现,其中元素是通过构造函数传递的函数按需生成的。
      • immutable.IndexedSeq
        • immutable.Range – 一个整数的分隔序列,在较低的一端closures,在高端打开,并且有一个步骤。
          • immutable.Range.InclusiveRange 。包含 – Range也在高端closures。
          • immutable.Range.ByOne – 一个步长为1的Range
        • immutable.NumericRangeRange更通用的版本,适用于任何Integral
          • immutable.NumericRange.Inclusiveimmutable.NumericRange.Exclusive
          • immutable.WrappedStringimmutable.RichString – 使得能够将String视为Seq[Char]包装,同时仍然保留String方法。 我不确定它们之间有什么区别。
      • mutable.IndexedSeq
        • mutable.GenericArray – 一个基于Seq的数组结构。 请注意,“类” Array是Java的Array ,它比类更多的是一种内存存储方法。
        • mutable.ResizableArray – 基于可resize数组的类使用的内部类。
        • mutable.PriorityQueuemutable.SynchronizedPriorityQueue – 实现优先级队列的类 – 队列首先根据Ordering排队,排队顺序排在最后。
        • mutable.PriorityQueueProxy – 一个PriorityQueue的抽象Proxy
    • LinearSeq – 线性序列的特征,有效时间为isEmptyheadtail
      • immutable.LinearSeq
        • immutable.List – 一个不可变的,单链接的列表实现。
        • immutable.Stream – 一个懒惰的列表。 它的元素只是按需计算的,但后来被记忆(保存在内存中)。 这在理论上可以是无限的。
      • mutable.LinearSeq
        • mutable.DoublyLinkedList – 一个可变的prevheadelem )和tailnext )的列表。
        • mutable.LinkedList – 具有可变headelem )和tailnext )的列表。
        • mutable.MutableList – 一个内部用于实现基于可变列表的类的类。
          • mutable.Queuemutable.QueueProxy – 为FIFO(先入先出)操作优化的数据结构。
          • mutable.QueueProxy – 一个mutable.QueueProxyProxy
    • SeqProxySeqViewSeqForwarder
    • immutable.Seq
      • immutable.Queue – 实现FIFO优化(先入先出)数据结构的类。 没有mutable队列和immutable队列的共同超类。
      • immutable.Stack – 实现LIFO优化(Last-In,First-Out)数据结构的类。 两个mutable immutable栈都没有共同的超类。
      • immutable.Vector – ?
      • scala.xml.NodeSeq – 一个扩展了immutable.Seq专门的XML类。
      • immutable.IndexedSeq – 如上所示。
      • immutable.LinearSeqimmutable.LinearSeq – 如上所示。
    • mutable.ArrayStack – 使用数组实现LIFO优化数据结构的类。 据说明显快于正常堆栈。
    • mutable.Stackmutable.SynchronizedStack – 实现LIFO优化的数据结构的类。
    • mutable.StackProxy – 一个mutable.StackProxyProxy
    • mutable.Seq
      • mutable.Buffer – 可通过追加,预先添加或插入新成员来更改元素的顺序。
        • mutable.ArrayBuffer – 一个mutable.Buffer类的实现,对append,update和random访问操作有不变的分摊时间。 它有一些专门的子类,比如NodeBuffer
        • mutable.BufferProxymutable.SynchronizedBuffer
        • mutable.ListBuffer – 由列表支持的缓冲区。 它提供了不变的时间追加和前置,大多数其他操作是线性的。
        • mutable.ObservableBuffermixin特性,当混合到一个Buffer ,通过一个Publisher接口提供通知事件。
        • mutable.IndexedSeq – 如上所示。
        • mutable.LinearSeq – 如上所示。

集合

  • Set – 一个集合是一个至多包含任何一个对象的集合。
    • BitSet集 – 以位集存储的一组整数。
      • immutable.BitSet
      • mutable.BitSet
    • SortedSet – 元素sorting的集合。
      • immutable.SortedSet
        • immutable.TreeSet – 一个基于树的SortedSet的实现。
    • SetProxySetProxy
    • immutable.Set
      • immutable.HashSet – 基于元素散列的Set实现。
      • immutable.ListSet – 基于列表的Set实现。
      • 存在额外的集合类,为从0到4个元素的集合提供优化的实现。
      • immutable.SetProxy – 不可变Set Proxy
    • mutable.Set
      • mutable.HashSet – 基于元素散列的Set的实现。
      • mutable.ImmutableSetAdaptor – 一个实现了一个不可变Set的可变Set类。
      • LinkedHashSet – 基于列表的Set实现。
      • ObservableSet – 一个mixin特征,当与一个Set混合时,通过一个Publisher接口提供通知事件。
      • SetProxySetProxy
      • SynchronizedSet – 一个mixin特征,当与一个Set混合时,通过一个Publisher接口提供通知事件。

  • 为什么Like类存在(例如TraversableLike)

这样做是为了实现最大的代码重用。 具有特定结构(可遍历的,地图等)的类的具体generics实现在Like类中完成。 然后,用于一般消费的类将覆盖可以被优化的选定方法。

  • 伴随方法是什么(例如List.companion)

类的构build器,即知道如何创build类的实例的对象,可以通过像map这样的方法来使用,是通过伴随对象中的方法创build的。 所以,为了构build一个Xtypes的对象,我需要从X的伴侣对象中获取这个构造器。不幸的是,在Scala中,没有办法从类X获得对象X.因此,一个在每个X, companion实例中定义的方法,它返回类X的伴随对象。

虽然在正常的程序中可能会有这种方法的使用,但其目标是使集合库中的代码重用。

  • 我怎么知道隐式对象在给定点的范围内

你不应该关心这个。 它们是隐含的,所以你不需要弄清楚如何使它工作。

这些含义使得集合上的方法能够在父类上定义,但仍然返回相同types的集合。 例如, map方法在TraversableLike上定义,但是如果您在List上使用,则会返回List