sid-coll-1a

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 中の高階型(higher-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 で定義されています。

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 参照


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.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 です(我々は、イミュータブルベクトルのいっそう洗練された実装がライブラリへ統合されるのを待っています)。

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 の要素の、最長セグメントの長さ。
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 になるまで、xs に値 x を追加して得られるシーケンス。

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

シーケンスのもう 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 は配列の助けを借りて、素早く配列に変換できます。

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 はビットを何ワードかにパックして実装する、非負整数要素のセットです。 それらは、通常のセットと同じ操作をサポートしますが、もし可能な要素値の範囲が狭ければ、
消費メモリはより少なくなります(論理的には、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)


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

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 に入れて返します。 もし key がマップ中で 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年04月13日 20:44
ツールボックス

下から選んでください:

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