test


Scala 2.8 コレクション


Scala 2.8 Collections
Martithe classdersky, EPFL
2010 年 7 月 20 日

1 はじめに


Scala 2.8 は、コレクションライブラリを大きく再設計しています。このペーパーはそれらの API とアーキテクチャを記述しています。

謝辞

複数の人により、コレクション設計は重要な方法を使って具体化されました。 新しいライブラリはそういった貢献なしでは存在しません。 Matthias Zenger は Scalaのマップ、バッファと他の型の最初のコレクションライブラリを書きました。 彼の設計結果の多くが、再設計から生き残りました。 そのいくつかは一般化され、彼がしたミュータブル、イミュータブルなコレクションパッケージへの分割のようなことは、今はシーケンスを含めてあらゆる種類のコレクションに等しく適用されています。 Sean McDirmid はオリジナルのコレクションライブラリにprojection(投影)を加えました。 ビューという名前の下に再設計時に取り上げられた概念です。 Adriaan Moors は、Scala 中の高位種型(highter-kinded types)を開発しました。その役割は、はじめに予期されたよりも最終的には小さくなったにせよ、コレクション再設計に主要なモチベーションを与えました。Adriaan ははじめて、Scala コレクションの基本的な抽象化であるビルダー(builder)の探求もしました。 David McIver は暗黙のパラメータとしてのビルダーのアイデアを私に与え、Iterable の一般化として Traversable (渡り歩き可能) を提案しました。 Miles Sabin は、Java コレクションと Scala コレクション間を変換する、双方向性のラッパーに貢献しました。 Phil Bagwell 、Gilles Dubochet 、Burak Emir 、Stepan Koltsov 、Stehane Micheloud 、Tony Morris 、Jorge Ortiz 、Paul Phillips 、David Pollak 、Tiark Rompf 、Lex Spoon と他の多くの人たちは、特定のコレクションクラスに貢献したか、あるいは改良のために重要な提案をしました。


2 概要 (Overview)


すべてのコレクションクラスは 今は パッケージ scala.collection に置かれています。 このパッケージは 3 つのサブパッケージを持っています。: ミュータブル、イミュータブル、ジェネリックです。 たいていのコレクションは、更新可能性に応じて、3 つの形で存在します。

パッケージ scala.collection.immutable 中のコレクションは、全ての人に対してイミュータブルであることが保証されています。 それは、同じコレクション値に何度アクセスしても、常に同じ要素のコレクションがもたらされることを意味します。

パッケージ scala.collection.mutable 中のコレクションが、コレクションの中を変える操作をいくつか持っていることはご存じでしょう。


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


図 1 : コレクション基底クラス

パッケージ scala.collection 中のコレクションは、ミュータブルであるか、あるいはイミュータブルのどちらかです。 たとえば、collection.Vector[T] は collection.immutable.Vector[T] と collection.mutable.Vector[T] の両方のスーパークラスです。 一般に、パッケージ scala.collection 中のルートコレクションは、イミュータブルコレクションと同じインターフェースを定義し、パッケージ scala.collection.mutable 中のミュータブルなコレクションは通常、このイミュータブルなインターフェースにいくつかの破壊的な更新操作を加えます。 ルートコレクションとイミュータブルコレクションの違いは、イミュータブルコレクションのユーザーには、だれもコレクションを変更できないという保証があるのに対して、ルートコレクションのユーザーは、たとえ自分では何も変更しなくても、他の人による変更を仮定する必要があるということです。

ジェネリックパッケージは、種々のコレクション実装に対する基本的な構成要素を含んでいます。 コレクションクラスは通常、ジェネリッククラス中の操作のいくつかを後で実装します。 他方、コレクションフレームワークのユーザーは、例外的な状況においてのみジェネリッククラスを参照する必要があります。


3 Scala コレクション API (The Scala Collections API)


最も重要なコレクション基底クラスを図 1 に示します。 それらすべてのクラスが共有する、多くの共通点があります。 クラス名の後にその構成要素を書くことで、どのようなコレクションのインスタンスでも形づくれます。
例:
   Traversable(1, 2, 3)
   Iterable("x", "y", "z")
   Map("x" -> 24, "y" -> 25, "z" -> 26)
   Set(Color.red, Color.green, Color.blue)
   SortedSet("hello", "world")
   Buffer(x, y, z)
   Vector(1.0, 2.0)
   LinearSeq(a, b, c)

同じことが特定のコレクション実装にも当てはまります。 たとえば、

   List(1, 2, 3)
   HashMap("x" -> 24, "y" -> 25, "z" -> 26)

これらすべてのコレクションは、上に書いたと同じ方法で toString を使って印字します。 すべてのコレクションは、それら自身の型の Traversable によって提供される API をサポートします。 たとえば、リスト上の map を使った関数のマッピングは、再び List をもたらしますが、セット上のそのマッピングは再びセットをもたらします。他についても同様です。 すべてのコレクションクラスについて、品質も均一になるように体系化されています。 これ以上のことは セクション 3.6 に書いてあります。

前に述べたように、図 1 中の大部分のクラスには、3 つの異体があります。 基本、ミュータブル、そしてイミュータブルです。 唯一の例外は、常にミュータブルなコレクションを記述する Buffer トレイトです。

以下では、これらのクラスを 1 つずつレビューします。


3.1 トレイト Traversable (Trait Traversable)


この階層構造のトップは、トレイト Traversable です。 その唯一の抽象操作は次です

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


この操作は、コレクションのすべての要素をトラバースし(渡り歩き)、与えられた操作 f を各要素に適用します。 適用により副作用だけが生じます。 実際、f のどのような関数結果も foreach によって捨てられます。

トラバース可能なオブジェクトは、有限、あるいは無限であり得ます。トラバース可能な無限オブジェクトの例は、自然数 Stream.from(0) のストリームです。 メソッド hasDefiniteSize はコレクションが無限である可能性を示します。 もし hasDefiniteSize が true を返すなら、コレクションは確かに有限です。 もしそれが false を返すなら、コレクションはまだ完全には精緻化されておらず、無限あるいは有限であることを示します。

トラバース可能なコレクション xs 上で定義された他の操作は、図 2 と 3 で定義されています。


3.2 トレイト Iterable (Trait Iterable)


図 1 中のトップの次のトレイトは Iterable です。 このトレイトは、抽象メソッド iterator を宣言し、それはコレクションのすべての要素を 1 つずつもたらすイテレータを返します。 Iterable 中の foreach メソッドは、iterator を使って実装されています。 Iterable のサブクラスは、効率の点から、しばしば foreach を直接の実装でオーバライドします。

クラス Iterable も、少し使用頻度の低いメソッドを Traversable へ加えます。 それは、イテレータが利用可能である場合に限り、効率的に実装されます。 それらは図 4 に要約されています。

Iterable の後に、それを継承する 3 つの基底クラスがあります。Seq、Set と Map です。

それら 3 つとも apply メソッド をもち、PartialFunction トレイトを実装していますが、apply の意味は各場合で異なります。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

xs.isEmpty :: コレクションが空であるかどうかテストします。

xs.nonEmpt :: コレクションが要素を含むかどうかテストします。

xs.size :: コレクション中の要素の数。

xs ++ ys :: xs と ys 両方の要素からなるコレクション。ys はトラバース可能なオブジェクトあるいはイテレータで構いません。

xs map f :: xs 中のすべての要素に関数 f を適用して得られるコレクション。

xs flatMap f :: xs 中のすべての要素にコレクション値関数 f を適用し、その結果を集めて連結して得られるコレクション。

xs filter p :: 述語関数 p を満たす、xs の要素からなるコレクション。

xs filterNot p :: 述語関数 p を満たさない、xs の要素からなるコレクション。

xs partition p :: xs を 2 つのコレクションからなるペアに分ける。: 一方は述語関数 p を満たすものからなり、他方は満たさないものからなるコレクション。

xs groupBy f :: 判別関数 f に応じて xs を複数のコレクションからなるマップに分け入れる。

xs forall p :: xs の全ての要素が述語関数 p を満たすかどうかを示す boolean値

xs exists p :: xs 中の要素に、述語関数 p を満たすものがあるかどうかを示す boolean値

xs count p :: 述語関数 p を満たす、xs 中の要素の数

xs find p :: 述語関数 p を満たす、xs 中の最初の要素を含む Option あるいは、そのようなものがなければ None。

(z /: xs)(op) :: xs の 連続する要素に二項演算 op を適用する。(訳注:先頭値 z との演算からはじめて)左から右へ進む。

(xs :\ z)(op) :: xs の 連続する要素に二項演算 op を適用する。(訳注:先頭値 z との演算からはじめて)右から左へ進む。

xs.foldLeft(z)(op) :: (z /: xs)(op) と同じ。

xs.foldRight(z)(op) :: (xs :\ z)(op) と同じ。

xs reduceLeft op :: 空でないコレクション xs の連続した要素に二項演算 op を適用する。左から右へ進む。

xs reduceRight op :: 空でないコレクション xs の連続した要素に二項演算 op を適用する。右から左へ進む。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 2 : Traversable コレクション上の操作 I



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

xs.head :: コレクションの最初の要素(あるいは、もし順序が定義されてないなら、任意の 1 つの要素)。

xs.tail :: xs.head を除く、コレクションの残り。

xs.last :: コレクションの最後の要素(あるいは、もし順序が定義されてないなら、任意の 1 つの要素)。

xs.init :: xs.last を除く、コレクションの残り。

xs take n :: xs の最初の n 個の要素からなるコレクション(あるいは、もし順序が定義されてないなら、任意の n 個の要素)。

xs drop n :: xs take n を除く、コレクションの残り。

xs splitAt n :: コレクションのペア(xs take n, xs drop n)。

xs slice (from, to) :: xs の、あるインデクス範囲中の要素からなるコレクション(from から to まで、to を除く)。

xs takeWhile p :: xs の先頭から始めてそのすべてが述語関数 p を満たす最長範囲の要素からなるコレクション。

xs dropWhile p :: xs の先頭から始めてそのすべてが述語関数 p を満たす最長範囲の要素を除く、コレクション。

xs span p :: コレクションの対 (xs takeWhilep , xs.dropWhilep)。

xs copyToBuffer buf :: このコレクションのすべての要素をバッファ buf へコピーします。

xs copyToArray (arr, start, len) :: このコレクションの要素を配列 arr にコピーします。

xs.toArray :: このコレクションを配列に変換します。

xs.toList :: このコレクションをリストに変換します。

xs.toIterable :: このコレクションを Iterable のインスタンスへ変換します。

xs.toSeq ;; このコレクションを Seq のインスタンスに変換します。

xs.toStream :: このコレクションを遅延計算されるストリームへ変換します。

xs mkString sep :: xs のすべての要素をセパレータ sep を挟んで並べた表示用文字列を作ります(メソッドは他のオーバーロードされた異体にもあります)。

xs addString (b, sep) :: StringBuilder b に文字列を付加します。それは、xs のすべての要素をセパレータ sep を挟んて並べた表示用文字列を作ります(メソッドは他のオーバーロードされた異体にもあります)。

xs.view :: xs 上のビュー(*3)を作り出します。

xs view (from, to) :: xs のインデクス範囲中の要素を表現するビューを作り出します。


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 3 : Traversable コレクション上の操作 II

(*3) 訳注 ビュー(view) については ttp://eed3si9n.github.com/scala-collections-doc-ja/collections_42.html 参照

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xs.iterator :: xs 中のすべての要素をもたらすイテレータ。foreach と同じ順番で要素をくまなくトラバースし(渡り歩き)ます。

xs takeRight n :: xs の最後の n 個の要素(あるいは、もし順序が定義されていないなら、任意の n 個の要素)からなるコレクション

xs dropRight n :: xs takeRight n を除く、コレクションの残り。

xs sameElements ys :: xs と ys が、同じ要素の同じ順からなるかテストします。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 4 : Iterable コレクション上の操作


3.3 トレイト Seq、Vector、LinearSeq と Buffer


シーケンス上の操作は図 5 に要約されています。Seq に対して、apply 操作はインデクス付けを意味します。; ですから、シーケンスは Int からそれらの要素型への部分関数です。 シーケンスの要素は、ゼロからシーケンスの長さ-1 まででインデックス付けられます。 シーケンスも Iterable に他のメソッドを加えます。: zip、zipAll と zipWithIndex の 3 つのメソッドは、2 つのシーケンスの対応する要素を結合することで、ペアのシーケンスを作り出します。 indexOf、lastIndexof、indexWhere、lastIndexWhere を含む他のメソッドのセットは、与えられた要素の最初あるいは最後の位置を検索するか、あるいは、与えられたプロパティを持つ要素を検索します。 startsWith と endsWith メソッドは、シーケンスが、与えられた接頭(前方)/接尾シーケンスで開始/終了するかどうかテストします。 メソッド reverse、patch と padTo によって新しいシーケンスが作り出されます。 メソッド union、 intersection と diff は、順序づけられたマルチ集合として見たシーケンスに作用します。 メソッド removeDuplicates は、シーケンスから重複要素を取り除きます。

もしシーケンスがミュータブルなら、update メソッドが追加で提供されます。それにより、seq(idx) = elem のような構文を使ってシーケンス要素の更新ができます。 Seq クラスは、それぞれ 2 つのサブクラス、LinearSeq と Vector を持っています。 これらは新しい操作を加えません。しかし、それぞれ異なるパフォーマンス特性を持ちます。: 線形シーケンスは効率的な head と tail を持っており、ベクトルは効率的な apply、length と (もしミュータブルなら) update 操作を持っています。 よく使われる線形シーケンスは、scala.collection.immutable.List と scala.collection.immutable.Stream です。 よく使われるベクトルは、scala.Array と scala.collection.mutable.ArrayBuffer です(我々は、イミュータブルベクトルのいっそう洗練された実装がライブラリへ統合されるのを待っています)。

シーケンスのもう 1 つのサブカテゴリは Buffers です。 Buffers は常にミュータブルです。 それらは既存の要素の更新だけではなく、要素の挿入、除去、バッファ最後への新しい要素の効率的な追加等ができます。バッファによってサポートされた主要な新しいメソッドは、最後尾への要素追加に対する buf += elem と buf ++= elems 、先頭への要素追加 elem +: buf と elems ++: buf、要素挿入 insert と insertAll、要素除去 remove と -= です。これらの操作は図 6 に要約されています。

よく使われるバッファの 2 つ実装は、scala.collection.mutable.ListBuffer と scala.collection.mutable.ArrayBuffers です。 名前が暗示するように、ListBuffer は List の助けを借りて、その要素の List への効率的な変換をサポートするのに対して、ArrayBuffer は配列の助けを借りて、素早く配列に変換できます。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

xs.length :: シーケンスの長さ(size と同じ)。

xs.lengthCompare ys :: もし xs が ys より短かければ -1、長ければ +1、同じ長さなら 0 を返します。 たとえシーケンスの 1 つが無限であっても、動作します。

xs(i) (あるいは、書き出すと、xs apply i) :: xs のインデックス i の要素。

xs.indices :: xs の インデックス範囲。0 から xs.length - 1 まで。

xs isDefinedAt i :: i が xs.indices に含まれるかどうかテストします。

xs zip ys :: xs と ys の対応する要素のペアからなるシーケンス。

xs zipAll (ys, x, y) :: xs と ys の対応する要素のペアのシーケンス。短い方のシーケンスに、要素 x あるいは y を付加して、長い方のシーケンスと長さを合わせる。

xs.zipWithIndex :: xs のインデックス範囲の、要素のペアからなるシーケンス。

xs segmentLength (p, i) :: xs(i) から始まる、その全てが述語関数 p を満たす xs の要素の、最長セグメントの長さ。

xs prefixLength p :: xs の先頭から始めて、その全てが述語関数 p を満たす最長セグメントの長さ。

xs indexWhere p :: xs 中の要素で、述語関数 p を最初に満たす要素のインデックス(いくつかの異体あり)。

xs indexOf x :: xs 中の要素で、x と等しい最初の要素のインデックス(いくつかの異体あり)。

xs.reverse :: xs の逆順の要素をもつシーケンス。

xs.reverseIterator :: xs のすべての要素を逆順でもたらすイテレータ。

xs startsWith ys :: xs がシーケンス ys を接頭(前方)に含むかどうかテストします。(いくつかの異体あり).

xs contains x :: xs に x と等しい要素があるかどうかテストします。

xs intersect ys :: シーケンス xs と ys の共通部(マルチ集合)。xs 中の要素の順序は維持されます。

xs diff ys :: シーケンス xs と ys の差異(マルチ集合)。xs 中の要素の順序は維持されます。

xs union ys :: xs と ys のマルチ集合和。xs ++ ys と同じ。

xs.removeDuplicates :: 重複した要素を含まない xs の部分シーケンス。

xs patch (i, ys, r) :: xs の、i 番目から r 個の要素を パッチ ys で置き換えます。

xs padTo (len, x) :: xs に、長さ len になるまで値 x を追加して得られるシーケンス。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 5 : Seq コレクションの上の操作

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

buf += x :: 要素 x をバッファに追加し、その結果の buf 自身を返します。。

buf += (x, y, z) :: 与えられた要素をバッファに追加します。

buf ++= xs :: xs 中のすべての要素をバッファに追加します。

x +: buf :: 要素 x をバッファの先頭に追加します。

xs +: buf :: xs 中のすべての要素をバッファの先頭に追加します。

buf insert (i, x) :: 要素 x をバッファのインデックス i に挿入します。

buf insertAll (i, xs) :: xs 中のすべての要素をバッファのインデックス i に挿入します。

buf -= x :: 要素 x をバッファから取り除きます。

buf remove i :: インデックス i の要素をバッファから取り除きます。

buf remove (i, n) :: インデックス i から始まる n 個の要素をバッファから取り除きます。

buf trimStart n :: 最初の n 個の要素をバッファから取り除きます。

buf trimEnd n :: 最後の n 個の要素をバッファから取り除きます。

buf.clear() :: すべての要素をバッファから取り除きます。

buf.clone :: buf と同じ要素をもつ新しいバッファ。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 6 : バッファの上の操作


3.4 Set トレイト (The Set traits)


セットは重複要素を含まない Iterables です。 セット上の操作は、一般のセットについては図 7 に要約されており、ミュータブルセットについては図 8 に要約されています。

contains メソッドは、与えられた要素をセットが含むかどうかを尋ねます。セットの apply メソッド は contains と同じであり、従って set(elem) は set contqains elem と同じです。 これは、セットが、セットが含む要素に対して true を返すテスト関数としても使えることを意味します。

どのようにしてセットに要素を付け加えたり、あるいは要素を取り除くのでしょうか? それはセットがミュータブルであるか、イミュータブルかによります。 イミュータブルセットについては、メソッド + と - があります。 操作 s + elem は、セットのすべての要素と共にすべての elem を含む新しいセットを返します。同様に s - elem は、elem を除く、セット s のすべての要素を含む新しいセットを返します。 これらの操作はミュータブルなセットにも機能します。しかし、それらはあまり頻繁には使われません。なぜなら、セット s のコピーが伴うからです。もっと効率的な代替物として、ミュータブルが異体クラスにメソッド += と -= を提供します。 操作 s += elem は、副作用としてセット s に elem を加え、その結果のセットを返します。 同じく、s -= elem は セットから elem を取り除き、その結果のセットを返します。

すべての操作は 1 つ以上のキーを、セットに加えるか、あるいは取り除くことができます。たとえば、:

   Set(1, 2) == Set() + (1, 2)


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xs contains x, xs(x) :: x が xs の要素であるかどうかテストします。

xs + x :: xs のすべての要素と x とからなるセット。

xs + (x, y, z) :: xs のすべての要素と与えられた要素とからなるセット。

xs ++ ys :: ys のすべての要素とxs のすべての要素とからなるセット。

xs - x :: x 以外の、xs のすべての要素からなるセット。

xs - (x, y, z) :: 与えられた要素以外の、xs のその他すべての要素を含むセット。

xs - ys :: ys の要素以外の、xs のその他すべての要素を含むセット。

xs & ys, xs intersect ys :: xs と ys の積セット。

xs | ys, xs union ys :: xs と ys の和セット。

xs &~ ys, xs diff ys :: xs と ys の差セット。

xs subsetof ys :: xs が ys のサブセットであるかどうかテストします。

xs.empty :: xs と同じクラスの空セット。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 7 : セット上の操作

   Set(1, 2) - (1, 2) == Set()

結局、ミュータブルセットに対して多数の操作 ++、-、あるいは ++=、-= があり、それらの右側の引数---トラバース可能なコレクション---中のすべての要素を付け加えたり、取り除いたりします。 次は、これら操作の典型的な使用例です。

   // イミュータブルセットについて
   var cities = immutable.Set[String]()
   cities = cities + "Paris" + "Dakar"
   cities = cities + ("London", "Moscow", "New York")
   cities = cities - "Dakar"
   cities = cities ++ cities // まだ同じ

   // ミュータブルセットについて
   val mcities = mutable.Set[String]()
   mcities += "Paris" += "Dakar"
   mcities = mcities + "Paris" + "Dakar" // 可能だが、2 回のクローンあり
   mcities += ("London", "Moscow", "New York")
   mcities -= "Dakar"
   mcities -= cities // 空きのセットになる。


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

xs += x :: 副作用として、要素 x を セット xs に付け加え、xs 自身を返す。

xs += (x, y, z) :: 副作用として、与えられた要素を セット xs に付け加え、xs 自身を返す。

xs ++= ys :: 副作用として、ys 中のすべての要素を セット xs に付け加え、xs 自身を返す。

xs -= x :: 副作用として、要素 x をセット xs から取り去り、xs 自身を返す。

xs -= (x, y, z) :: 副作用として、与えられた要素をセット xs から取り去り、xs 自身を返す。

xs -= ys :: 副作用として、ys 中のすべての要素をセット xs から取り去り、xs 自身を返す。

xs add x :: 要素 x を セット xs に付け加え、もしセットが x を前に含んでいなかったのなら true を返し、そうでなかったのなら false を返す。

xs remove x :: 要素 x を セット xs から取り去り、もしセットが x をはじめから含んでいたなら true を返し、そうでなかったのなら false を返す。

xs(x) = b :: (あるいは、書き出して、xs.update(x、b))。もし boolean 引数 b が true なら xs に x を付け加え、そうでなければ xs から x を取り去ります。

xs retain p :: 述語関数 p を満たす xs 中の要素だけを保持します。

xs.clear() :: xs からすべての要素を取り去ります。

xs.clone :: xs と同じ要素をもつ新しいミュータブルなセット。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 8 : ミュータブルセット上の操作

これらの操作のほかに、既存セットとの積、和、あるいは差によっても新しいセットができます。 これらの操作は 2 つの異なる形で存在します。: アルファベット形とシンボル形です。 アルファベットバージョンは、union、intersect、diff であり、一方、シンボルバージョンは、|、& 、&~ です。 実際、++ が Traversavle 引数をとり、他方、union と | がセットを引数にとる点を除き、++ は、union あるいは | の他のエイリアスとみることができます。

ミュータブルセットは += と -= の異体として add と remove も提供します。 その違いは、add と remove が、操作がセットに影響を与えたことを示す Boolean 値を返すことです。

Two subtraits of sets are SortedSet and BitSet. A SortedSet is a set that produces its elements (using iterator or foreach in a given ordering (which can be freely chosen). Sorted sets also support ranges of all elements that lie between a pair of given elements in the ordering. The result of such a range is again a sorted set .

SortedSet と BitSet は、セットの 2 つのサブトレイトです。 SortedSet は、与えられた順(自由に選択可)で iterator あるいは foreach を使って、その要素を作り出すセットです。 ソートされたセットは、与えられた順序付き要素対のその順通りの、間にあるすべての要素からなるレンジ(範囲)もサポートします。 得られるそのようなレンジは、再びソートされたセットです。

Bitsets are sets of non-negative integer elements that are implemented in one or more words of packed bits. They support the same operations as normal sets, but consume less space, if the range of possible element values is small (Logically, bitsets should be sorted, but this has not yet been implemented) .

Bitsets はパックされたビットの 1 つ以上の語で実装される、非負整数要素のセットです。 それらは、通常のセットと同じ操作をサポートしますが、もし可能な要素値の範囲が狭ければ、より少ないメモリを消費します(論理的には、bitsets はソートされるべきですが、しかしそれはまだ実装されていません)。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ms get k :: マップ ms 中のキー k に付随する値の Option。もしなければ None。

ms(k) :: (あるいは、書き上だすと、ms apply k) マップ ms 中のキー k に付随する値。もしなければ例外発生。

ms getOrElse (k, d) :: マップ ms 中のキー k に付随する値、あるいは、もしなければデフォルト値 d。

ms contains k :: ms がキー k に対するマッピングを含むかどうかテストします。

ms isDefinedAt k :: contains と同じ。

ms + (k -> v) :: ms のすべてのマッピングと、キー k から値 v へのマッピング k -> v からなるマップ。

ms + (k -> v, l -> w) :: ms のすべてのマッピングと、与えられたキー/値ペアからなるマップ。

ms ++ kvs :: ms のすべてのマッピングと、与えられた kvs のキー/値ペアからなるマップ。

ms - k :: キー k の任意のマッピング以外の、ms の他のすべてのマッピングからなるマップ。

ms - (k, l, m) :: 与えられたキーの任意のマッピング以外の、ms の他のすべてのマッピングからなるマップ。

ms - ks :: ks 中のキーをもつマッピング以外の、ms の他のすべてのマッピングからなるマップ。

ms updated (k, v) :: ms + (k -> v)と同じ。

ms.keysIterator :: ms 中の各キーをもたらすイテレータ。

ms.keys :: ms 中の各キーからなるセット。


ms.valuesIterator :: s 中のキーに付随する各値をもたらすイテレータ。

ms.values :: ms 中のキーに付随する各値からなるセット。

ms filterKeys p :: ms 中のそれらマッピングだけからなるマップビュー。ただし、キーは述語関数 p を満たすものとします。

ms mapValues f :: 関数 f を ms 中のキーに付随する各値へ適用して得られるマップビュー。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 9 : マップ上の操作


3.5 Map トレイト (The Map traits)


マップは、(マッピングあるいはアソシエイション(関連)とも呼ばれる)キー/値 ペアの Iterables です。 Scala の Predef クラスは、ペア (key,value) の代わりの構文として、key -> value と書くことができる、暗黙の型変換を提供します。 たとえば、Map("x" -> 24, "y" -> 25, "z" -> 26) は、Map*1 と、より分かり易いこと以外は、全く同じです。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ms(k) = v :: (あるいは、書き出して、ms.update(x、v))。副作用として、キー k から値 v へのマッピングを マップ ms へ付け加えます。k の以前のあらゆるマッピングを上書きします。

ms += (k -> v) :: 副作用として、キー k から値 v へのマッピングを マップ ms へ付け加え、ms 自身を返します。

ms += (k -> v, l -> w) :: 副作用として、与えられたマッピングを マップ ms へ付け加え、ms 自身を返します。

ms ++= kvs :: 副作用として、kvs中のすべてのマッピングを マップ ms へ付け加え、ms 自身を返します。

ms -= k :: 副作用として、キー k のマッピングを ms から取り除き、ms 自身を返します。

ms -= (k, l, m) :: 副作用として、与えられたキーのマッピングを ms から取り除き、ms 自身を返します。

ms -= ks :: 副作用として、ks 中のすべてのキーを ms から取り除き、ms 自身を返します。

ms put (k, v) :: キー k から値 v へのマッピングを ms へ付け加え、以前 k に付随していたすべての値を Option にして返します。

ms remove k :: キー k のあらゆるマッピングを ms から取り除き、以前 k に付随していたすべての値を Option にして返します。

ms getOrElseUpdate (k, d) :: もしキー k がマップ ms で定義されていれば、その付随する値を返します。 そうでなければ、マッピング k -> v で ms を更新し、値 d を返します。

ms retain p :: 述語関数 p を満たすキーをもつ xs 中のマッピングだけを保持します。

ms transform f :: マップ ms 中のすべての付随する値を関数 f で変換します。

ms.clear() :: ms からすべてのマッピングを取り除きます。

ms.clone :: ms と同じマッピングをもつ新しいミュータブルマップ。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 10 : ミュータブルマップ上の操作


マップ上の基本的な操作はセット上のそれに似ています。 それらは、一般的なマップについては図 9 に、ミュータブルマップについては図 10 に要約されています。 contains(包含) に代わる、基本的な lookup(探索) メソッドは次です。

   def get(key): Option[Value]

操作 m get key は、マップが、与えられたキーに対する関連付けを含むかどうかテストします。 もしそうなら、付随する値を Some に入れて返します。 もし(訳註:与えられた)キーがマップ中で 1 つも定義されていないなら、None を返します。 マップも apply メソッド を定義していて、与えられたキーに付随する値を Option 中にラップせずに、直接返します。 もしキーがマップで定義されていないなら、例外が引き起こされます。

マップに対する追加と除去操作は、セットのそれに酷似しています。イミュータブルマップに対しては、新しいマッピングを + で追加でき、- を使ってキーを除去できます。結果はそれぞれ、新しいイミュータブルマップになります。ミュータブルマップに対しては、対応する操作は += と -= です。これら後者の操作は副作用であり、処理結果のマップ自身を返します。
例:
   // イミュータブルマップに対して
   var capitals = immutable.Map[String, String]()
   capitals = capitals + ("France" -> "Paris", "Senegal" -> "Dakar")
   capitals = capitals - "France"

   // ミュータブルマップに対して
   val mcapitals = mutable.Set[String, String]()
   mcapitals += ("France -> "Paris") += ("Senegal" -> "Dakar")
   mcapitals -= "France"
   mcapitals ++= capitals // (変化なし)

これら追加と除去操作にいくつかの異体もサポートされています。 イミュータブルマップは、次の定義の updated をサポートしています。

   def updated (key: Key, value: Value): Map[Key, Value] = this + ((key, value))

すなわち、updated はキー/値の関連付けを、はじめにペアにすることなしにマップに加えます。 これにより、マップが update を直接に実装するなら、数値計算コレクションコードのスピードアップが図られます。

ミュータブルマップは、updated の代わりに、変化演算子として update をサポートしており、次のように定義されています。

   def update(key: Key, value: Value) { this += ((key, value)) }

このメソッドは、updated がイミュータブルコレクションに与えるのと同じ、速度上の利点をミュータブルコレクションに与えます。 さらに加えて、update により、代入に似た構文を使ってコレクションを更新できます。 次は 1 つの例です。

   capitals("Germany") = "Berlin"
   capitals.update("Germany", "Berlin")
   capitals += ("Germany" -> "Berlin")

上記のコードで、1 行目の代入は糖衣構文であり、2 行目の update メソッド呼び出しと全く同じです。 この呼び出しは、最後の行の += 呼び出しと機能的に等価ですが、それより少し高速である可能性があります。

ミュータブルマップは、+= と -= の異体として put と remove も提供します。 違いは、 put と remove が、マップ中で与えられたキーに以前付随していた値からなる Option を返す、あるいは、もしキーが以前は定義されていなかったなら None を返す、ということです。

キー/値のペアのイテレータを与える iterator のほかに、マップではキーと値を個別に検査できます。m.keysIterator は、m 中のすべてのキーのイテレータを作り出し、他方、m.valuesIterator は、すべての値のイテレータを作り出します。 m.keys と m.values を使って、マップのキーと値にセットとしてもアクセスできます。


3.6 等価性 (Equality)


コレクションライブラリは等価性とハッシュ化に、同一の手法を用いています。 アイデアはコレクションをセット、マップとシーケンスに分けることです。 異なるカテゴリのコレクションは常に等しくありません。 たとえば、Set(1, 2, 3) は List(1, 2, 3)に等しくありません。たとえそれらが同じ要素からできていても等価ではありません。 他方、同じカテゴリ中では、それらが同じ要素を持っている場合に限り、その場合には必ず、コレクションは等価です(シーケンスについては、同じ順番の同じ要素)。 たとえば、List(1, 2, 3) == Vector(1, 2, 3) であり、HashSet(1, 2) == Treeset(2,1) です。

等価性では、コレクションのミュータブル、イミュータブルは重要ではありません、ミュータブルなコレクションについては、等価性テストが実行される時の、その時の要素を単純に考えます。 これは、ミュータブルなコレクションが、要素の追加、除去に応じて、異なる時には異なるコレクションと等しいかもしれないことを意味します。 これは、ミュータブルなコレクションをハッシュマップ中のキーとして使用するとき、潜在的な罠となります。

Example :

   val map = HashMap[Array[Int], Int]()
   val xs = Array(1, 2, 3)
   map += (xs -> 6)
   xs(0) = 0
   map(xs)

この例で、最後の行中の選択は、ほとんどの場合失敗します。なぜなら、配列 xs のハッシュコードは後ろから 2 番目の行中で変わっているからです。 このため、ハッシュコードベースの検索は、xs が記憶されたものとは異なる場所を検索します。


3.7 シーケンス生成 (Creating sequences)


コレクションクラスも、まったく新規のコレクション生成に対して、統一的なインターフェースを提供します。: C.empty は、任意のコレクションクラス C に対して、そのクラスの空のコレクションを与えます。 C(x1,...,xn)は、要素 x1,...,xn をもつコレクションを与えます。

例:
   Traversable.empty           // 空きのトラバース可能なオブジェクト
   List.empty                  // 空きのリスト
   Vector(1.0, 2.0)            // 要素 1.0, 2.0 のベクトル
   Set(dog, cat, bird)         // 3 匹の動物からなるセット
   HashSet(dog, cat, bird)     // 同じ動物の ハッシュセット
   Map(a -> 7, 'b' -> 0)       // 文字から整数へのマップ

シーケンスクラスは、さらに、他の生成操作群を提供します。 それらは、図 11 中に要約されています。 concat 操作は、任意数の traversables を 1 つに連結します。 fill と tabulate(一覧) メソッドは、式あるいは一覧関数によって初期化された、与えられた次元の、1 次元あるいは多次元のシーケンスを作り出します。 range メソッドは、一定刻み長の整数シーケンスを作りだします。 iterate メソッドは、スタート要素以降への関数適用の繰り返しで得られるシーケンスを作りだします。


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

S.empty :: 空のシーケンス。

S(x, y, z) :: 要素 x、y、z から成るシーケンス。

S.concat(xs, ys, zs) :: xs、ys、zs の要素を連結して得られるシーケンス。

S.fill(n){e} :: 各要素を式 e によって計算した、長さ n のシーケンス。

S.fill(m, n){e} :: 各要素を式 e によって計算した、m×n 次元の、シーケンスのシーケンス(より高い次元もあります)。

S.tabulate(n){f} :: 各インデックス i の要素を f(i) によって計算した、長さ n のシーケンス。


S.tabulate(m, n){f} :: 各インデックス (i, j)の要素を f(i, j) によって計算した、m×n 次元の、シーケンスのシーケンス(より高い次元もあります)。

S.range(start, end) :: start から end-1 までの整数シーケンス。

S.range(start, end, step) ::
start から end までの、step刻 みで増加する整数からなるシーケンス。 ただし、end 値を含まない。

S.iterate(x, n)(f) :: 要素 x、f(x)、f(f(x)) からなる、長さ n のシーケンス。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
図 11 : 任意のシーケンスコレクションクラス S のインスタンス生成

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2011年03月30日 17:47
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。

*1 "x", 24), ("y", 25), ("z", 26