Scala 2.8 コレクション設計チュートリアル

StackOverflow https://stackoverflow.com/questions/1722137

質問

に続いて 私の息もできない混乱, 、新しい機能を説明する良いリソースは何ですか? スカラ座 2.8 コレクションライブラリが構造化されました。以下のものがどのように組み合わされるかについての情報を見つけることに興味があります。

  • コレクションのクラス/特性自体 (例: List, Iterable)
  • なぜ のように クラスが存在します (例: TraversableLike)
  • コンパニオンメソッドの目的 (例: List.companion)
  • どのようにして何を知っているのか implicit オブジェクトは特定の時点でスコープ内にあります
役に立ちましたか？

解決

序文

あります 2.8 コレクションのウォークスルー Martin Odersky著。おそらく最初の参考資料となるでしょう。こちらも補足されております 建築メモ, 、独自のコレクションをデザインしたい人にとっては特に興味深いでしょう。

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

それに関する論文は次のとおりです。 スカラ SID #3. 。Scala 2.7 と 2.8 の違いに興味がある人にとっては、その分野の他の論文も興味深いはずです。

論文から選択的に引用し、私の考えをいくつか補足します。Matthias が decodified.com で生成した画像もいくつかあり、オリジナルの SVG ファイルが見つかります。 ここ.

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

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

また、Scala 2.9 で導入された、並列コレクション、直列コレクション、およびおそらく並列コレクションの区別もあります。それらについては次のセクションで説明します。このセクションで説明する階層は、 非並列コレクション専用.

次の図は、Scala 2.8 で導入された非特定の階層を示しています。General collection hierarchy

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

不変階層のグラフ:Immutable collection hierarchy

可変階層のグラフ:Mutable collection hierarchy

伝説：

Graph legend

画像が見えない人のために、コレクション階層を ASCII で簡略化して示します。

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

並行コレクション

Scala 2.9 で並列コレクションが導入されたときの設計目標の 1 つは、それらの使用を可能な限りシームレスにすることでした。最も単純に言えば、非並列 (シリアル) コレクションを並列コレクションに置き換えることで、即座にメリットを得ることができます。

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

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

並列コレクション階層には特性の名前が同じですが、先頭に次の名前が付きます。 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, 、シリアルコレクションではありません。

主な特徴

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

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

特性 TraversableOnce

この特性は の特性によく似ています Traversable 以下に説明しますが、あなただけが使用できるという制限があります 一度. 。つまり、 TraversableOnce 5月 使用不能にしてしまいます。

この制限により、コレクションとコレクション間で同じメソッドを共有できるようになります。 Iterator. 。これにより、 Iterator でも使っていない Iterator- 受け入れるように書き換えられた場合、実際に任意のコレクションとイテレータを実際に操作できる固有のメソッド TraversableOnce.

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

トラバーサブルな特性

の上部にある コレクション 階層は特性です Traversable. 。その唯一の抽象的な操作は、

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

操作は、コレクションのすべての要素を通過し、与えられた操作Fを各要素に適用することを目的としています。この適用は副作用のみを目的として行われます。実際、Fの関数結果はforeachによって破棄されます。

通過可能なオブジェクトは有限または無限になります。無限の横断可能なオブジェクトの例は、自然数の流れです Stream.from(0). 。方法 hasDefiniteSize コレクションがおそらく無限であるかどうかを示します。もし hasDefiniteSize true を返す場合、コレクションは確かに有限です。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 つすべてが持っています apply メソッドを実装しており、3 つすべてが PartialFunction 特性ですが、その意味は apply それぞれの場合で異なります。

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

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

基本クラスと特性

  • 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 -- アン Iterable の Tuple2, 、キー (タプルの最初の要素) を指定して値 (タプルの 2 番目の要素) を取得するメソッドも提供します。伸びる PartialFunction 同じように。
    • MapProxy --A Proxy のために Map.
    • DefaultMap -- の一部を実装する特性 Mapの抽象メソッド。
    • SortedMap --A Map キーがソートされています。
      • immutable.SortMap
        • immutable.TreeMap -- 実装するクラス immutable.SortedMap.
    • immutable.Map
      • immutable.MapProxy
      • immutable.HashMap -- 実装するクラス immutable.Map キーハッシュを通じて。
      • immutable.IntMap -- 実装するクラス immutable.Map に特化した Int キー。キーの 2 進数に基づくツリーを使用します。
      • immutable.ListMap -- 実装するクラス immutable.Map リストを通じて。
      • immutable.LongMap -- 実装するクラス immutable.Map に特化した Long キー。見る IntMap.
      • 特定の数の要素に対して最適化された追加のクラスがあります。
    • mutable.Map
      • mutable.HashMap -- 実装するクラス mutable.Map キーハッシュを通じて。
      • mutable.ImmutableMapAdaptor -- を実装するクラス mutable.Map 既存のものから immutable.Map.
      • mutable.LinkedHashMap -- ?
      • mutable.ListMap -- 実装するクラス mutable.Map リストを通じて。
      • mutable.MultiMap -- 各キーに対して複数の個別の値を受け入れるクラス。
      • mutable.ObservableMap --A 混入します これを混ぜると、 Map, 、イベントをオブザーバーに公開します。 Publisher インターフェース。
      • mutable.OpenHashMap -- オープン ハッシュ アルゴリズムに基づくクラス。
      • mutable.SynchronizedMap --A 混入します と混合する必要があります Map 同期されたメソッドを備えたバージョンを提供します。
      • mutable.MapProxy.

シーケンス

  • Seq -- 要素のシーケンス。明確に定義されたサイズと要素の繰り返しを前提としています。伸びる PartialFunction 同じように。
    • IndexedSeq -- O(1) 要素アクセスと O(1) 長さ計算をサポートするシーケンス。
      • IndexedSeqView
      • immutable.PagedSeq -- の実装 IndexedSeq ここで、要素はコンストラクターを介して渡された関数によってオンデマンドで生成されます。
      • immutable.IndexedSeq
        • immutable.Range -- 区切られた整数のシーケンス。下端は閉じ、上限は開き、ステップが付いています。
          • immutable.Range.Inclusive --A Range ハイエンドもクローズしました。
          • immutable.Range.ByOne --A 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-ベースの配列のような構造。「クラス」に注意してください Array ジャワのものです Array, 、これはクラスというよりもメモリ格納メソッドです。
        • mutable.ResizableArray -- サイズ変更可能な配列に基づくクラスによって使用される内部クラス。
        • mutable.PriorityQueue, mutable.SynchronizedPriorityQueue -- 優先順位付きキューを実装するクラス -- 要素がキューから取り出されるキュー。 Ordering 最初にキューイングの順序が最後になります。
        • mutable.PriorityQueueProxy -- 要約 Proxy のために PriorityQueue.
    • 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 --A Proxy のために 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 --A Proxy のために mutable.Stack..
    • mutable.Seq
      • mutable.Buffer -- 新しいメンバーを追加、先頭に追加、または挿入することによって変更できる要素のシーケンス。
        • mutable.ArrayBuffer -- の実装 mutable.Buffer 追加、更新、およびランダム アクセス操作の償却時間が一定であるクラス。次のようないくつかの特殊なサブクラスがあります。 NodeBuffer.
        • mutable.BufferProxy, mutable.SynchronizedBuffer.
        • mutable.ListBuffer -- リストに基づいたバッファ。他のほとんどの操作は線形であり、一定時間の追加と先頭を提供します。
        • mutable.ObservableBuffer --A 混入します に混合すると、 Buffer, 、を通じて通知イベントを提供します。 Publisher インターフェース。
        • mutable.IndexedSeq -- 上で見たとおり。
        • mutable.LinearSeq -- 上で見たとおり。

セット

  • Set -- セットは、任意のオブジェクトを最大 1 つ含むコレクションです。
    • BitSet -- ビットセットとして保存された整数のセット。
      • immutable.BitSet
      • mutable.BitSet
    • SortedSet -- 要素が順序付けされたセット。
      • immutable.SortedSet
        • immutable.TreeSet -- の実装 SortedSet 木をベースにしています。
    • SetProxy --A Proxy のために Set.
    • immutable.Set
      • immutable.HashSet -- の実装 Set 要素のハッシュに基づいています。
      • immutable.ListSet -- の実装 Set リストに基づいて。
      • 0 ～ 4 要素のセットに最適化された実装を提供する追加のセット クラスが存在します。
      • immutable.SetProxy --A Proxy 不変のもののために Set.
    • mutable.Set
      • mutable.HashSet -- の実装 Set 要素のハッシュに基づいています。
      • mutable.ImmutableSetAdaptor -- ミュータブルを実装するクラス Set 不変のものから Set.
      • LinkedHashSet -- の実装 Set リストに基づいて。
      • ObservableSet --A 混入します と混合すると、 Set, 、を通じて通知イベントを提供します。 Publisher インターフェース。
      • SetProxy --A Proxy のために Set.
      • SynchronizedSet --A 混入します と混合すると、 Set, 、を通じて通知イベントを提供します。 Publisher インターフェース。
  • Like クラスが存在する理由 (例:横断可能のような)

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

  • コンパニオンメソッドの目的 (例:リスト.コンパニオン)

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

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

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

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

これらの暗黙的メソッドは、コレクションのメソッドを親クラスで定義しながらも、同じ型のコレクションを返すことができるようにするために存在します。たとえば、 map メソッドが定義されている TraversableLike, 、ただし、 List を取得します List 戻る。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top