73

私の息を呑むような混乱に続いて、新しいScala2.8 コレクションライブラリがどのように構成されているかを説明するいくつかの優れたリソースは何ですか。以下がどのように組み合わされるかについての情報を見つけたいと思います。

  • コレクションクラス/特性自体（例List、Iterable）
  • Likeクラスが存在する理由（例TraversableLike）
  • コンパニオンメソッドの目的（例List.companion）
  • implicit特定の時点でスコープ内にあるオブジェクトを知る方法
4

1 に答える 1

188

序文

Martin Oderskyによる2.8コレクションのウォークスルーがあります。これは、おそらく最初の参照になるはずです。独自のコレクションをデザインしたい人にとって特に興味深い建築ノートも追加されています。

この回答の残りの部分は、そのようなものが存在する前に（実際、2.8.0自体がリリースされる前に）書かれていました。

それに関する論文はScalaSID＃3として見つけることができます。その分野の他の論文も、Scala2.7と2.8の違いに興味のある人にとっては興味深いはずです。

私は論文から選択的に引用し、私の考えを補足します。また、decodified.comでMatthiasによって生成されたいくつかの画像があり、元のSVGファイルはここにあります。

コレクションクラス/特性自体

コレクションには、実際には3つの特性の階層があります。1つは可変コレクション用、1つは不変コレクション用、もう1つはコレクションについて何も仮定していません。

また、Scala 2.9で導入された、並列、シリアル、およびおそらく並列のコレクションには違いがあります。それらについては次のセクションで説明します。このセクションで説明する階層は、非並列コレクションのみを参照しています。

次の画像は、Scala2.8で導入された非特定の階層を示しています。 一般的なコレクション階層

示されているすべての要素は特性です。他の2つの階層には、特性を直接継承するクラスと、ラッパークラスへの暗黙的な変換を通じてその階層に属していると見なすことができるクラスもあります。これらのグラフの凡例は、それらの後にあります。

不変の階層のグラフ： 不変のコレクション階層

可変階層のグラフ： 可変コレクション階層

伝説：

グラフの凡例

これは、画像を見ることができない人のために、コレクション階層の簡略化されたASCII描写です。

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

並列コレクション

Scala 2.9が並列コレクションを導入したとき、設計目標の1つは、それらを可能な限りシームレスに使用することでした。簡単に言うと、非並列（シリアル）コレクションを並列コレクションに置き換えて、すぐにメリットを享受できます。

ただし、それまでのすべてのコレクションはシリアルであったため、それらを使用する多くのアルゴリズムは、それらがシリアルであるという事実を想定し、それに依存していました。そのような仮定でメソッドに供給された並列コレクションは失敗します。このため、前のセクションで説明したすべての階層でシリアル処理が義務付けられています。

並列コレクションをサポートするために、2つの新しい階層が作成されました。

並列コレクション階層の特性の名前は同じですが、前に：Par、、、ParIterableおよびが付いています。並列アクセスをサポートするコレクションは、より強力な特性をサポートできるため、はないことに注意してください。シリアル階層に存在する、より特殊な特性のいくつかもありません。この階層全体は、ディレクトリの下にあります。ParSeqParMapParSetParTraversableParIterablescala.collection.parallel

並列コレクションを実装するクラスも異なり、可変ParHashMapおよびParHashSet不変の並列コレクションに加えParRangeて、のParVector実装immutable.ParSeqとParArray実装がありますmutable.ParSeq。

シリアルコレクションとパラレルコレクションの特性を反映する別の階層も存在しますが、プレフィックスは：Gen、、、、GenTraversableおよびです。これらの特性は、並列コレクションと直列コレクションの両方の親です。これは、aを取得するメソッドは並列コレクションを受信できないことを意味しますが、aを取得するメソッドは、シリアルコレクションとパラレルコレクションの両方で機能することが期待されます。GenIterableGenSeqGenMapGenSetSeqGenSeq

これらの階層が構造化された方法を考えると、Scala2.8用に記述されたコードはScala2.9と完全に互換性があり、シリアル動作が要求されました。書き直さないと、並列コレクションを利用できませんが、必要な変更はごくわずかです。

並列コレクションの使用

コレクションは、そのコレクションのメソッドを呼び出すことにより、並列コレクションに変換できますpar。同様に、コレクションのメソッドを呼び出すことで、コレクションをシリアルコレクションに変換できますseq。

コレクションがすでに要求されたタイプ（パラレルまたはシリアル）であった場合、変換は行われません。seqただし、並列コレクションまたはparシリアルコレクションを呼び出すと、要求された特性を持つ新しいコレクションが生成されます。

seqコレクションを非並列コレクションに変換する、と、コレクションの要素から作成されたtoSeqものを返す、を混同しないでください。並列コレクションをSeq呼び出すと、シリアルコレクションではなくが返されます。toSeqParSeq

主な特徴

多くの実装クラスとサブトレイトがありますが、階層にはいくつかの基本的なトレイトがあり、それぞれがより多くのメソッドまたはより具体的な保証を提供しますが、それらを実装できるクラスの数を減らします。

次のサブセクションでは、主な特徴とその背後にある考え方について簡単に説明します。

特性TraversableOnce

この特性は、以下で説明する特性とほとんど同じですが、 1回しTraversableか使用できないという制限があります。つまり、で呼び出されたメソッドは、それを使用できなくする可能性があります。TraversableOnce

この制限により、コレクションとの間で同じメソッドを共有することが可能になりIteratorます。これにより、特定のメソッドをIterator使用せずIteratorに機能するメソッドが、実際にはすべてのコレクションと、受け入れるように書き直された場合はイテレータを使用できるようになりますTraversableOnce。

TraversableOnceコレクションとイテレータを統合するため、コレクションのみに関係する前のグラフには表示されません。

特性トラバース可能

コレクション階層の最上位には、traitがありますTraversable。その唯一の抽象的な操作は

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

この操作は、コレクションのすべての要素をトラバースし、指定された操作fを各要素に適用することを目的としています。アプリケーションは、その副作用のためにのみ行われます。実際、fの関数結果はforeachによって破棄されます。

トラバース可能なオブジェクトは、有限または無限にすることができます。無限に通過可能なオブジェクトの例は、自然数のストリームですStream.from(0)。このメソッドhasDefiniteSizeは、コレクションが無限である可能性があるかどうかを示します。trueを返す場合hasDefiniteSize、コレクションは確かに有限です。falseが返された場合、コレクションはまだ完全に作成されていないため、無限または有限である可能性があります。

foreachこのクラスは、 （40を超える）という観点から効率的に実装できるメソッドを定義します。

特性反復可能

iteratorこのトレイトは、コレクションのすべての要素を1つずつ生成するイテレータを返す抽象メソッドを宣言します。のforeachメソッドIterableは、の観点から実装され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、それを継承する3つの基本特性があります：Seq、、、SetおよびMap。3つすべてにメソッドがあり、3つすべてが特性をapply実装しますが、それぞれの場合の意味は異なります。PartialFunctionapply

の意味を信じて、Seq直感的ですSet。Mapその後、クラスは、パフォーマンスとその結果として利用可能になるメソッドに関して特定の保証を提供する特定の実装に分割されます。LinearSeq、、など、IndexedSeqさらに改良されたいくつかの特性も利用できますSortedSet。

以下のリストは改善される可能性があります。提案をコメントに残してください。修正します。

基本クラスと特性

  • Traversable-基本的なコレクションクラス。だけで実装できますforeach。
    • TraversableProxy--のプロキシTraversable。self実際のコレクションを指すだけです。
    • TraversableView-いくつかの非厳密な方法でトラバース可能。
    • TraversableForwarderunderlying--、、、、、を除くほとんどのメソッドをに転送し、すべてtoStringの呼び出しで同じ種類の新しい反復可能なオブジェクトを作成します。hashCodeequalsstringPrefixnewBuilderview
    • mutable.Traversableおよびimmutable.Traversable-と同じですTraversableが、コレクションタイプを制限します。
    • など、他の特殊なケースのIterableクラスMetaDataが存在します。
    • IterableIterator-- （を通じて）を作成できるコレクションiterator。
      • IterableProxy、、、および。IterableView_mutableimmutable.Iterable
  • Iterator--の子孫ではない特性Traversable。とを定義nextしhasNextます。
    • CountedIterator--これまでに見た要素を返すIterator定義。count
    • BufferedIterator--定義headします。これは、次の要素を消費せずに返します。
    • など、他の特殊なケースのIteratorクラスSourceが存在します。

マップ

  • Map--An Iterableof Tuple2。これは、キー（タプルの最初の要素）を指定して値（タプルの2番目の要素）を取得するためのメソッドも提供します。同様に拡張PartialFunctionします。
    • MapProxy--AProxyはMap。
    • DefaultMapMap--いくつかの抽象メソッドを実装するトレイト。
    • SortedMap--Mapキーがソートされている A。
      • immutable.SortMap
        • immutable.TreeMap--を実装するクラスimmutable.SortedMap。
    • immutable.Map
      • immutable.MapProxy
      • immutable.HashMapimmutable.Map-キーハッシュを介して実装するクラス。
      • immutable.IntMap-キーimmutable.Mapに特化した実装クラス。Intキーの2進数に基づくツリーを使用します。
      • immutable.ListMapimmutable.Map-リストを介して実装するクラス。
      • immutable.LongMap-キーimmutable.Mapに特化した実装クラス。Longを参照してくださいIntMap。
      • 特定の数の要素に最適化された追加のクラスがあります。
    • mutable.Map
      • mutable.HashMapmutable.Map-キーハッシュを介して実装するクラス。
      • mutable.ImmutableMapAdaptormutable.Map--既存のからを実装するクラスimmutable.Map。
      • mutable.LinkedHashMap-？
      • mutable.ListMapmutable.Map-リストを介して実装するクラス。
      • mutable.MultiMap-キーごとに複数の異なる値を受け入れるクラス。
      • mutable.ObservableMap--mixinは、と混合すると、インターフェイスMapを介してオブザーバーにイベントを公開しPublisherます。
      • mutable.OpenHashMap-オープンハッシュアルゴリズムに基づくクラス。
      • mutable.SynchronizedMap--同期されたメソッドを備えたバージョンを提供するためにと混合する必要があるミックスイン。Map
      • 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のA。
        • immutable.NumericRange--より一般的なバージョンはRangeどの。でも機能しますIntegral。
          • immutable.NumericRange.Inclusive、immutable.NumericRange.Exclusive。
          • immutable.WrappedString、 -メソッドを保持しながら、をとしてimmutable.RichString表示できるラッパー。それらの違いはわかりません。StringSeq[Char]String
      • mutable.IndexedSeq
        • mutable.GenericArray--Seqベースの配列のような構造。「クラス」ArrayはJavaArrayであり、クラスというよりもメモリストレージメソッドであることに注意してください。
        • mutable.ResizableArray--サイズ変更可能な配列に基づくクラスによって使用される内部クラス。
        • mutable.PriorityQueue、mutable.SynchronizedPriorityQueue-優先キューを実装するクラス-要素がOrdering最初にデキューされ、最後にキューの順序が付けられるキュー。
        • mutable.PriorityQueueProxyProxy--の要約PriorityQueue。
    • LinearSeqisEmpty- 、、headおよびの効率的な時間を持つ線形シーケンスの特性tail。
      • immutable.LinearSeq
        • immutable.List-不変の単一リンクのリスト実装。
        • immutable.Stream-怠惰なリスト。その要素はオンデマンドでのみ計算されますが、後でメモ化（メモリに保持）されます。理論的には無限大です。
      • mutable.LinearSeq
        • mutable.DoublyLinkedList-可変のリストprev、head（elem）およびtail（next）。
        • mutable.LinkedListhead--変更可能な（elem）とtail（ ）のリストnext。
        • mutable.MutableList-可変リストに基づくクラスを実装するために内部的に使用されるクラス。
          • mutable.Queue、mutable.QueueProxy-FIFO（先入れ先出し）操作用に最適化されたデータ構造。
          • mutable.QueueProxy--AProxyはmutable.Queue。
    • SeqProxy、、SeqView_SeqForwarder
    • immutable.Seq
      • immutable.Queue--FIFO最適化（先入れ先出し）データ構造を実装するクラス。mutableとimmutableキューの両方に共通のスーパークラスはありません。
      • immutable.Stack--LIFOに最適化された（後入れ先出し）データ構造を実装するクラス。mutable immutable両方のスタックに共通のスーパークラスはありません。
      • immutable.Vector-？
      • scala.xml.NodeSeq--を拡張する特殊なXMLクラスimmutable.Seq。
      • immutable.IndexedSeq-上記のように。
      • immutable.LinearSeq-上記のように。
    • mutable.ArrayStack-配列を使用してLIFOに最適化されたデータ構造を実装するクラス。おそらく、通常のスタックよりも大幅に高速です。
    • mutable.Stack、mutable.SynchronizedStack-LIFOに最適化されたデータ構造を実装するクラス。
    • mutable.StackProxy--AProxyはmutable.Stack..
    • mutable.Seq
      • mutable.Buffer-新しいメンバーを追加、追加、または挿入することで変更できる要素のシーケンス。
        • mutable.ArrayBuffer-クラスの実装mutable.Buffer。追加、更新、およびランダムアクセス操作の償却時間が一定です。など、いくつかの特殊なサブクラスがありNodeBufferます。
        • mutable.BufferProxy、mutable.SynchronizedBuffer。
        • mutable.ListBuffer-リストに裏打ちされたバッファ。それは一定時間の追加と追加を提供し、他のほとんどの操作は線形です。
        • mutable.ObservableBuffer--ミックスイン特性。にミックスすると、インターフェイスBufferを介して通知イベントを提供しPublisherます。
        • mutable.IndexedSeq-上記のように。
        • mutable.LinearSeq-上記のように。

セット

  • Set-セットは、最大で1つのオブジェクトを含むコレクションです。
    • BitSet-ビットセットとして格納されている整数のセット。
      • immutable.BitSet
      • mutable.BitSet
    • SortedSet-要素が順序付けられているセット。
      • immutable.SortedSet
        • immutable.TreeSetSortedSet-ツリーに基づくの実装。
    • SetProxy--AProxyはSet。
    • immutable.Set
      • immutable.HashSetSet-要素ハッシュに基づくの実装。
      • immutable.ListSetSet-リストに基づくの実装。
      • 0から4の要素のセットに最適化された実装を提供するために、追加のセットクラスが存在します。
      • immutable.SetProxy--Proxy不変のSetA。
    • mutable.Set
      • mutable.HashSetSet-要素ハッシュに基づくの実装。
      • mutable.ImmutableSetAdaptorSet--不変から可変を実装するクラスSet。
      • LinkedHashSetSet-リストに基づくの実装。
      • ObservableSet-と混合すると、インターフェイスを介して通知イベントを提供するミックスイン特性。SetPublisher
      • SetProxy--AProxyはSet。
      • SynchronizedSet-と混合すると、インターフェイスを介して通知イベントを提供するミックスイン特性。SetPublisher
  • Likeクラスが存在する理由（例：TraversableLike）

これは、コードを最大限に再利用するために行われました。特定の構造（トラバース可能、マップなど）を持つクラスの具体的なジェネリック実装は、Likeクラスで実行されます。次に、一般消費を目的としたクラスは、最適化できる選択されたメソッドをオーバーライドします。

  • コンパニオンメソッドの目的（例：List.companion）

クラスのビルダー、つまり、などのメソッドで使用できる方法でそのクラスのインスタンスを作成する方法を知っているオブジェクトmapは、コンパニオンオブジェクトのメソッドによって作成されます。したがって、タイプXのオブジェクトをビルドするには、Xのコンパニオンオブジェクトからそのビルダーを取得する必要があります。残念ながら、Scalaでは、クラスXからオブジェクトXに取得する方法はありません。そのため、 Xの各インスタンスで定義されたメソッドcompanion。クラスXのコンパニオンオブジェクトを返します。

通常のプログラムではこのようなメソッドが使用される可能性がありますが、そのターゲットはコレクションライブラリでのコードの再利用を可能にすることです。

  • 特定の時点でスコープ内にある暗黙のオブジェクトを知る方法

あなたはそれを気にするべきではありません。それらは正確に暗黙的であるため、それを機能させる方法を理解する必要はありません。

これらの暗黙は、コレクションのメソッドを親クラスで定義できるようにするために存在しますが、それでも同じタイプのコレクションを返します。たとえば、mapメソッドはで定義されていますが、TraversableLikeで使用すると元に戻ります。ListList

于 2009-11-12T19:36:26.423 に答える