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

2023-10-05 22:41:36

質問

に続いて私の息もつかせぬ混乱を説明する良い資料がありますか？ Scala 2.8 のコレクションライブラリが構造化されました。以下がどのように組み合わされているのか、いくつかの情報を見つけたいと思っています。

コレクションクラス/トレイトそのもの（例えば List , Iterable )
なぜ のように クラスが存在するのか（例 TraversableLike )
コンパニオンメソッドは何のためにあるのか（例えば List.companion )
どのように私は何を知っている implicit オブジェクトがスコープ内にあることを知るには

どのように解決するのですか？

はじめに

そこには 2.8コレクションウォークスルー Martin Odersky によるものがあり、おそらく最初に参照すべきものでしょう。また、このページにはアーキテクチャのメモで補足されており、自分のコレクションをデザインしたい人には特に興味深い内容となっています。

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

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

論文から一部引用し、私の考えを補足します。Decodified.com の Matthias が作成した画像もありますし、オリジナルの SVG ファイルは以下の場所にあります。ここにあります。 .

コレクションクラス/トレイトそのもの

コレクションには実際には3つの階層があります。1つは変更可能なコレクションのためのもの、1つは不変のコレクションのためのもの、そして1つはコレクションについて何も仮定しないものです。

また、Scala 2.9で導入された並列、直列、多分並列のコレクションという区別があります。それらについては次のセクションで説明します。このセクションで説明する階層は は非並列コレクションに限定されます。 .

次の図は，Scala 2.8で導入された非特異的な階層を表しています．

表示されている要素は全てtraitです．他の2つの階層には、特質を直接継承するクラスと、特質を継承するために として見ることができます。 として見ることができるクラスもあります。これらのグラフの凡例は、グラフの後にあります。

不変階層のグラフ．

変更可能な階層のグラフ。

凡例です。

画像を見ることができない人のために、コレクションの階層を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 を返します。

主な特徴

多くの実装クラスやサブストレートがありますが、階層にはいくつかの基本的な特質があり、それぞれがより多くのメソッドやより具体的な保証を提供する一方で、それらを実装できるクラスの数は少なくなっています。

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

Trait TraversableOnce（トラバーサブルワンス

この trait は trait Traversable と似ていますが、使用できるのは 一度だけ . つまり TraversableOnce があります。 は使用不能にします。

この制限により、同じメソッドをコレクションと Iterator . このため、コレクションで動作するメソッドが Iterator を使わずに Iterator -を受け入れるように書き直せば、どんなコレクションでも実際に動作させることができます。 TraversableOnce .

なぜなら TraversableOnce はコレクションとイテレータを統合しているため、コレクションのみを扱うこれまでのグラフには登場しません。

トラバーサブル特性

の先頭で コレクション の階層にあるのが trait Traversable . その唯一の抽象的な操作は

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

この操作は、コレクションのすべての要素を走査し、与えられた操作fを各要素に適用することを意味する。を適用します。適用はその副作用のためだけに行われます。実際、fのどのような関数結果もによって破棄されます。

可逆的なオブジェクトは有限でも無限でも構いません。無限探索可能なオブジェクトの例としては、自然数のストリーム自然数 Stream.from(0) . メソッド hasDefiniteSize は、コレクションが無限大になる可能性があるかどうかを無限かどうかを示します。もし hasDefiniteSize が真を返した場合、コレクションは確実に有限である。もし偽を返したら、コレクションはコレクションはまだ十分に練られていないため、無限か有限のどちらかです。

の観点から効率的に実装できるメソッドを定義したクラスです。 foreach (40個以上)である。

特徴的なイテラブル

このトライットは抽象的なメソッド iterator を宣言し、コレクションの全要素を一つずつ取り出すイテレータを返します。このメソッドは 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 -- An Iterable の Tuple2 であり、キー（タプルの最初の要素）を指定して値（タプルの2番目の要素）を取得するメソッドも提供します。拡張 PartialFunction も拡張しています。
- MapProxy -- A Proxy に対して Map .
- DefaultMap -- の一部を実装した trait です。 Map の抽象的なメソッドのいくつかを実装しています。
- SortedMap -- A Map で、キーがソートされているもの。
  - immutable.SortMap
    - immutable.TreeMap -- を実装したクラスです。 immutable.SortedMap .
- immutable.Map
  - immutable.MapProxy
  - immutable.HashMap -- を実装したクラスです。 immutable.Map を実装したクラスです。
  - immutable.IntMap -- を実装したクラスです。 immutable.Map に特化した Int キーを使用する。キーの二進数に基づいたツリーを使用します。
  - 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 -に基づく配列のような構造体。なお、"class" Array はJavaの 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 (First-In, First-Out) オペレーションに最適化されたデータ構造です。
      - mutable.QueueProxy -- A Proxy に対して mutable.Queue .
- SeqProxy , SeqView , SeqForwarder
- immutable.Seq
  - immutable.Queue -- FIFO最適化（First-In, First-Out）されたデータ構造を実装したクラスです。両者に共通のスーパークラスはありません。 mutable と immutable キューを使用します。
  - immutable.Stack -- LIFO最適化（Last-In, First-Out）データ構造を実装したクラスです。両者に共通のスーパークラスはありません。 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 -- mutableを実装したクラス Set を実装したクラスです。 Set .
  - LinkedHashSet -- の実装です。 Set を実装したものです。
  - ObservableSet -- A ミキシン と混在させると Set で、通知イベントを提供します。 Publisher インターフェースを提供します。
  - SetProxy -- A Proxy に対して Set .
  - SynchronizedSet -- A ミキシン と混在させると Set で、通知イベントを提供します。 Publisher インターフェースを提供します。

Likeクラスの存在理由 (例: TraversableLike)

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

コンパニオンメソッドが何のためにあるか（例：List.companion)

クラスのビルダー、つまり、以下のようなメソッドで使用できる方法で、そのクラスのインスタンスを作成する方法を知っているオブジェクトです。 map のようなメソッドで使用できるように、そのクラスのインスタンスを作成する方法を知っているオブジェクトです。残念ながら，ScalaではクラスXからオブジェクトXに辿り着く方法はありません． companion というメソッドが定義されており，このメソッドはクラスXのコンパニオンオブジェクトを返します．

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

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

あなたはそれを気にする必要はありません。暗黙のオブジェクトは、どのように動作させるかを考える必要がないように、正確には暗黙のオブジェクトです。

これらの暗黙の了解は、コレクションに対するメソッドが親クラスで定義されていても、同じ型のコレクションを返すことを可能にするために存在します。例えば map メソッドは TraversableLike で定義されていますが、もし List に使うと List を返します。