Scala 2.8集合devise教程
接下来, 我不知所措地混淆了什么,一些很好的资源解释了如何构build新的Scala 2.8集合库。 我有兴趣find一些有关以下方面的信息:
- 集合类/特性本身(例如
List
,Iterable
) - 为什么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了两个新的层次结构来支持并行集合。
并行集合层次结构具有相同的特征名称,但前面带有Par
: ParIterable
, ParSeq
, ParMap
和ParSet
。 请注意,没有ParTraversable
,因为任何支持并行访问的集合都能够支持更强大的ParIterable
特性。 它在串行层次结构中没有一些更专门化的特征。 这整个层次结构可以在scala.collection.parallel
目录下find。
实现并行集合的类也不同, ParHashMap
和ParHashSet
用于可变和不可变并行集合, ParRange
和ParVector
实现immutable.ParSeq
ParArray
和ParArray
实现mutable.ParSeq
。
还有另一种层次结构,它反映了串行和并行集合的特征,但带有前缀Gen
: GenTraversable
, GenIterable
, GenSeq
, GenMap
和GenSet
。 这些特征是平行和连续收集的父母 。 这意味着采用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
,它返回一个迭代器,它可以逐个生成所有集合的元素。 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
之后,有三个从它inheritance的基本特征: Seq
, Set
和Map
。 三种都有apply
方法,三种都实现了PartialFunction
特性,但是应用的含义各不相同。
我相信Seq
, Set
和Map
的含义是直观的。 之后,这些类在特定的实现中分解,这些实现提供了关于性能的特定保证,以及由此产生的方法。 还有一些有进一步改进的特性,比如LinearSeq
, IndexedSeq
和SortedSet
。
下面的清单可能会有所改进。 留下评论的build议,我会解决它。
基础类和特征
-
Traversable
– 基本集合类。 可以用foreach
来实现。-
TraversableProxy
– 一个Traversable
代理。 只要指出self
的真实collections。 -
TraversableView
– 一些非严格方法的Traversable。 -
TraversableForwarder
– 将大多数方法转发到underlying
,除了toString
,hashCode
,equals
,stringPrefix
,newBuilder
,view
和所有调用创build一个新的同类的可迭代对象。 -
mutable.Traversable
和immutable.Traversable
– 与Traversable
相同,但限制集合types。 - 其他特例
Iterable
类,如MetaData
,存在。 -
Iterable
– 可以创buildIterator
(通过iterator
)的集合。-
IterableProxy
,IterableView
,mutable
和immutable.Iterable
。
-
-
-
Iterator
– 不是Traversable
后裔。 定义next
和hasNext
。-
CountedIterator
– 一个Iterator
定义count
,返回到目前为止看到的元素。 -
BufferedIterator
– 定义head
,它返回下一个元素而不消耗它。 - 其他特殊的
Iterator
类,例如Source
存在。
-
地图
-
Map
– 一个Tuple2
的Iterable
,它也提供了获取给定一个键(元组的第一个元素)的值(元组的第二个元素)的方法。 还扩展了PartialFunction
。-
MapProxy
–Map
的Proxy
。 -
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.PagedSeq
–IndexedSeq
一个实现,其中元素是通过构造函数传递的函数按需生成的。 -
immutable.IndexedSeq
-
immutable.Range
– 一个整数的分隔序列,在较低的一端closures,在高端打开,并且有一个步骤。-
immutable.Range.Inclusive
。Range
。包含 –Range
也在高端closures。 -
immutable.Range.ByOne
– 一个步长为1的Range
。
-
-
immutable.NumericRange
–Range
更通用的版本,适用于任何Integral
。-
immutable.NumericRange.Inclusive
,immutable.NumericRange.Exclusive
。 -
immutable.WrappedString
,immutable.RichString
– 使得能够将String
视为Seq[Char]
包装,同时仍然保留String
方法。 我不确定它们之间有什么区别。
-
-
-
mutable.IndexedSeq
-
mutable.GenericArray
– 一个基于Seq
的数组结构。 请注意,“类”Array
是Java的Array
,它比类更多的是一种内存存储方法。 -
mutable.ResizableArray
– 基于可resize数组的类使用的内部类。 -
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
– 一个mutable.QueueProxy
的Proxy
。
-
-
-
-
SeqProxy
,SeqView
,SeqForwarder
-
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.LinearSeq
。immutable.LinearSeq
– 如上所示。
-
-
mutable.ArrayStack
– 使用数组实现LIFO优化数据结构的类。 据说明显快于正常堆栈。 -
mutable.Stack
,mutable.SynchronizedStack
– 实现LIFO优化的数据结构的类。 -
mutable.StackProxy
– 一个mutable.StackProxy
的Proxy
-
mutable.Seq
-
mutable.Buffer
– 可通过追加,预先添加或插入新成员来更改元素的顺序。-
mutable.ArrayBuffer
– 一个mutable.Buffer
类的实现,对append,update和random访问操作有不变的分摊时间。 它有一些专门的子类,比如NodeBuffer
。 -
mutable.BufferProxy
,mutable.SynchronizedBuffer
。 -
mutable.ListBuffer
– 由列表支持的缓冲区。 它提供了不变的时间追加和前置,大多数其他操作是线性的。 -
mutable.ObservableBuffer
– mixin特性,当混合到一个Buffer
,通过一个Publisher
接口提供通知事件。 -
mutable.IndexedSeq
– 如上所示。 -
mutable.LinearSeq
– 如上所示。
-
-
-
集合
-
Set
– 一个集合是一个至多包含任何一个对象的集合。-
BitSet
集 – 以位集存储的一组整数。-
immutable.BitSet
-
mutable.BitSet
-
-
SortedSet
– 元素sorting的集合。-
immutable.SortedSet
-
immutable.TreeSet
– 一个基于树的SortedSet
的实现。
-
-
-
SetProxy
–Set
的Proxy
。 -
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
接口提供通知事件。 -
SetProxy
–Set
的Proxy
。 -
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
。