Scala 2.8 コレクションAPI -- 集合

集合

集合(Set)とは、重複する要素を含まないIterableです。集合に対する演算は、一般的な集合については次の表に要約でき、可変な集合についてはその後の表に要約できます。演算は次のカテゴリに分類できます:

テスト contains, apply, subsetOf。 containsメソッドは集合が与えられた要素を含むか尋ねます。集合のapplyメソッドはcontainsであり、 set(elem)はset contains elemと同じです。結果として集合は、自身が含む要素に対しては真を返すテスト関数として使えます。例えば

val fruit = Set("apple", "orange", "peach", "banana")

fruit: scala.collection.immutable.Set[java.lang.String] =

Set(apple, orange, peach, banana)

scala> fruit("peach")

res0: Boolean = true

scala> fruit("potato")

res1: Boolean = false
追加 +および++は1つまたは複数の要素を集合に追加し、新しい集合を返します。
削除 -, --は1つまたは複数の要素を集合から削除し、新しい集合を返します。
集合演算 和・積・差。これらの演算は2通りの形式があります: アルファベットによるものと記号によるものです。アルファベットによるものはintersect, union,およびdiffであり、記号によるものは&, |, および&~です。さらに言えばunionおよび|が引数として集合を取るのに対してTraversableを取る点を除けば、SetがTraversableから継承した++はunionや|のさらなる別名として考えられます。

クラスSet内の演算
何であるか	何をするか
テスト:
`xs contains x`	`x`が`xs`の要素であるか調べる。
`xs(x)`	`xs contains x`と同じ。
`xs subsetOf ys`	`xs`が`ys`の部分集合であるか調べる。
追加:
`xs + x`	`xs`の全ての要素と`x`を含む集合。
`xs + (x, y, z)`	`xs`の全ての要素と与えられた追加の要素を含む集合。
`xs ++ ys`	`xs`の全ての要素と`ys`の全ての要素を含む集合。
削除:
`xs - x`	`x`以外の`xs`の全ての要素を含む集合。
`xs - (x, y, z)`	与えられた要素以外の`xs`の全ての要素を含む集合。
`xs -- ys`	`ys`の全ての要素以外の`xs`の全ての要素を含む集合。
`xs.empty`	`xs`と同じクラスの空集合。
二項演算:
`xs & ys`	`xs`と`ys`の集合積。
`xs intersect ys`	`xs & ys`と同じ。
`xs \| ys`	`xs`と`ys`の集合和。
`xs union ys`	`xs \| ys`と同じ。
`xs &~ ys`	`xs`と`ys`の集合差。
`xs diff ys`	`xs &~ ys`と同じ。

可変な集合はこの表に要約できるように、要素を追加・削除・更新するメソッドをさらに提供します。

クラスmutable.Set内の演算
何であるか	何をするか
追加:
`xs += x`	`xs`に要素`x`を副作用として追加し、`xs`自身を返す。
`xs += (x, y, z)`	`xs`に与えられた要素を副作用として追加し、`xs`自身を返す。
`xs ++= ys`	`xs`に`ys`の全ての要素を副作用として追加し、`xs`自身を返す。
`xs add x`	`xs`に要素`x`を追加し、`x`が集合に含まれていなかったなら`true`、含まれていたなら`false`を返す。
削除:
`xs -= x`	`xs`から要素`x`を副作用として取り除き、`xs`自身を返す。
`xs -= (x, y, z)`	`xs`から与えられた要素を副作用として取り除き、`xs`自身を返す。
`xs --= ys`	`xs`から`ys`の全ての要素を副作用として取り除き、`xs`自身を返す。
`xs remove x`	`xs`から要素`x`を取り除き、`x`が集合に含まれていたなら`true`、含まれていなかったなら`false`を返す。
`xs retain p`	述語`p`を満たす`xs`の要素のみを残す。
`xs.clear()`	`xs`から全ての要素`x`を取り除く。
更新:
`xs(x) = b`	(または書き下して`xs.update(x, b)`) もし真偽値の引数`b`が`true`であれば`x`を`xs`に追加し、そうでなければ`x`を`xs`から取り除く。
複製:
`xs.clone`	`xs`と同じ要素を持つ新しい可変な集合。

不変な集合のように、可変な集合は要素の追加のために+および++演算を提供し、要素の削除のために-および--演算を提供します。しかしそれらは可変な集合では要素のコピーを伴うためあまり使われません。より効率的な代わりとして更新メソッド+=および-=を提供します。演算s += elemは集合sにelemを副作用として追加し、変更した集合を結果として返します。同様にs -= elemは集合からelemを削除し、変更した集合を結果として返します。 +=および-=と関連して、一括演算である++=および--=もあり、トラバーサブルまたはイテレータの全ての要素を追加または削除します。

メソッド名として+=および-=を選んだ結果、可変な集合と不変な集合でよく似たコードが動作します。まず不変な集合sを使った以下のREPLでの対話を考えます:

scala> var s = Set(1, 2, 3)

s: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> s += 4

scala> s -= 2

scala> s

res2: scala.collection.immutable.Set[Int] = Set(1, 3, 4)

ここでimmutable.Set型のvarに対して+=および-=を使いました。 s += 4のような式はs = s + 4の略です。そのため、これは追加メソッド+を集合sに対して呼び出し、その結果を変数sに代入します。ここで可変な集合による似たインタラクションを考えます。

scala> val s = collection.mutable.Set(1, 2, 3)

s: scala.collection.mutable.Set[Int] = Set(1, 2, 3)

scala> s += 4

res3: s.type = Set(1, 4, 2, 3)

scala> s -= 2

res4: s.type = Set(1, 4, 3)

最終的な効果は前のインタラクションととても似ています。まずSet(1, 2, 3)から始めてSet(1, 3, 4)を得ました。しかし、文としては以前と似ていても、これらは違うことをしています。 s += 4は可変な集合sの+=メソッドを呼び出し、集合を直接変えています。同様にs -= 2は同じ集合の-=メソッドを呼び出します。

2つのインタラクションを比較すると重要な原則が現れます。多くの場合、valで保持している可変なコレクションはvarで保持している不変なコレクションで置き替えられ、その逆も成り立ちます。これはコレクションを直接更新したのか新しいコレクションを作ったのか分かるような別の参照が無いかぎり成り立ちます。

可変な集合は+=および-=の変種としてaddおよびremoveを提供します。違いとしてはaddおよびremoveは演算が効果があったか示すBooleanの結果を返します。

可変な集合の現在のデフォルト実装は要素の格納にハッシュテーブルを使います。不変な集合のデフォルト実装は集合の要素数に合わせた表現を使います。空の要素はシングルトンオブジェクトで表わされます。大きさが4までの集合は全ての要素をフィールドとして保持する1つのオブジェクトとして表わされます。それ以上の大きさでは、不変な集合はハッシュトライで実装されます。

このような表現方法の選択の結果、小さな(4ぐらいまでの)集合であれば、不変な集合は可変な集合よりもよりコンパクトで効率的です。そのため、もし集合のサイズが小さいと期待できるなら不変にしてみてください。

集合の子トレイトとしてSortedSetおよびBitSetの2つがあります。それらに関しては独立したページで説明します。

続いては:

集合