Scala 2.8 コレクション API -- ビュー

コレクションには新たなコレクションを構築するメソッドがたくさんある。例えば map、filter、++ などがある。これらのメソッドは一つ以上のコレクションをレシーバとして取り、戻り値として別のコレクションを生成するため変換演算子 (transformer) と呼ばれる。

変換演算子を実装するには主に二つの方法がある。正格 (strict) 法は変換演算子の戻り値として全ての要素を含む新たなコレクションを返す。非正格法、もしくは遅延 (lazy) 法と呼ばれる方法は、結果のコレクションの代理のみを構築して返し、実際の要素は必用に応じて構築される。

非正格な変換演算子の具体例として、以下の遅延 map 演算の実装を見てほしい:

def lazyMap[T, U](coll: Iterable[T], f: T => U) = new Iterable[T] {

def iterator = coll.iterator map f

}

lazyMap は、渡されたコレクション coll の全要素を総なめすることなく新しい Iterable を構築していることに注意してほしい。代わりに、渡された関数の f が新しいコレクションの iterator に必要に応じて適用される。

全ての変換演算子を遅延実装している Stream を除いて、Scala のコレクションは全ての変換演算子をデフォルトで正格法で実装している。しかし、コレクションのビューにより、体系的に全てのコレクションを遅延したものに変え、また逆に戻すことができる。ビュー (view) は特殊なコレクションの一種で、何らかのコレクションに基づいているが全ての変換演算子を遅延実装してる。

あるコレクションからそのビューへと移行するには、そのコレクションに対して view メソッドを呼び出す。xs というコレクションがあるとすると、xs.view は変換演算子が遅延実装されている以外は同一のコレクションだ。ビューから正格なコレクションに戻るには force メソッドを使う。

具体例を見てみよう。二つの関数を続けて写像したい Int型のベクトルがあるとする。

scala> val v = Vector(1 to 10: _*)

v: scala.collection.immutable.Vector[Int] =

Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> v map (_ + 1) map (_ * 2)

res5: scala.collection.immutable.Vector[Int] =

Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

最後の文において、式 v map (_ + 1) は新たなベクトルを構築し、それは第二の map (_ * 2) の呼び出しによって三つ目のベクトルに変換される。多くの状況において、最初の map への呼び出しで中間結果のためだけのベクトルが構築されるのは無駄にしかならない。上記の例では、(_ + 1) と (_ * 2) の二つの関数を合成して map を一回だけ実行したほうが速くなるだろう。両方の関数が一ヶ所にあるならば手で合成することも可能だろう。しかし、しばしばデータ構造への連続した変換はプログラム内の別々のモジュールによって実行される。もしそうならば、これらの変換を融合することはモジュール性を犠牲してしまう。中間結果を回避する、より汎用性のある方法は、ベクトルをまずビューに変え全ての変換をビューに適用した後、ビューからベクトルに逆変換することだ:

scala> (v.view map (_ + 1) map (_ * 2)).force

res12: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

scala> val vv = v.view

vv: scala.collection.SeqView[Int,Vector[Int]] =

SeqView(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

v.view を適用することで遅延評価される Seq である SeqView が得られる。SeqView には二つの型パラメータがある。第一の Int はビューの要素の型を示す。第二の Vector[Int] は view を逆変換する時の型コンストラクタを示す。

scala> vv map (_ + 1)

res13: scala.collection.SeqView[Int,Seq[_]] = SeqViewM(...)

map の戻り値は、SeqViewM(...) と表示された値だ。この値は本質的に、ベクトル v に対して関数 (_ + 1) を使って map を適用する必要があるということを記録するラッパーだ。しかし、ビューが強制実行 (force) されるまでは map 演算は適用されない。SeqView の後ろに付けられた「M」は、ビューが map 演算を表すことを示す。他の文字は別の遅延された演算を示す。例えば、「S」は遅延した slice 演算を示し、「R」は遅延した reverse 演算を示す。先ほどの結果に、次の map を適用しよう。

scala> res13 map (_ * 2)

res14: scala.collection.SeqView[Int,Seq[_]] = SeqViewMM(...)

今度は二回の map 演算を含む SeqView が得られるため、「M」も二回表示される: SeqViewMM(...)。最後に、先ほどの結果を逆変換すると:

scala> res14.force

res15: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

格納されていた両方の関数は強制実行 (force) の一部として適用され、新しいベクトルが構築される。これにより、中間結果のデータ構造は必要なくなった。

一つ注意してほしいのは、最終結果の静的型が Vector ではなく Seq であるということだ。型をさかのぼってみると、最初の遅延 map が適用された時点で既に戻り値の静的型が SeqViewM[Int, Seq[_]] 型であったことが分かる。つまり、ビューが特定の列型である Vector に適応されたという「知識」が失われたということだ。ビューの実装には多量のコードを要するものがあるため、Scala コレクションライブラリは汎用コレクション型にのみビューを提供するが、特定の実装にはビューは提供されないのだ⁵。

ビューを使うことを考慮する二つの理由がある。第一は、パフォーマンスだ。コレクションをビューに切り替えることで中間結果の構築を避けれることを既に説明した。このような節約は時として大切な結果をもたらす。もう一つの具体例として、単語のリストから回文を探す問題を考える。回文とは前後のどちらから読んでも同じ語句だ。必要な定義を以下に示す:

def isPalindrome(x: String) = x == x.reverse

def findPalidrome(s: Seq[String]) = s find isPalindrome

ここで非常に長い words という列があり、列の最初の百万語の中から単一の回文を探したいと仮定する。findPalidrome の定義を再利用できるだろうか。当然、以下のように書くことはできる:

findPalindrome(words take 1000000)

これは、列の中から最初の百万語を選択するのと、単一の回文を探すという二つの側面をきれいに分担する。しかし、たとえ列の最初の語が回文であったとしても、百万語から成る中間結果の列を常に構築してしまうという欠点がある。つまり、999999語が中間結果にコピーされ、その後検査もされないということが起こりえる。ここで多くのプログラマは諦めて、先頭 n個の部分列に対して検索を行う特殊なバージョンの回文検索を書いてしまう。ビューがあれば、あなたはそんな事をしなくても済む。こう書けばいいからだ:

findPalindrome(words.view take 1000000)

関心事の分業を保ちつつも、これは百万要素の列の代わりに軽量なビューオブジェクトのみを構築する。これにより、パフォーマンスとモジュール性の択一をしなくても済む。

次の事例として、可変列に対するビューを見てみたい。可変列のビューにいくつかの変換関数を適用することで、元の列内の要素を選択的に更新する制限枠として機能することができる。ここに配列 arr があると仮定する:

scala> val arr = (0 to 9).toArray

arr: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

その配列への制限枠を作るのに、arr のビューのスライスを作ることができる:

scala> val subarr = arr.view.slice(3, 6)

subarr: scala.collection.mutable.IndexedSeqView[

Int,Array[Int]] = IndexedSeqViewS(...)

これにより、配列 arr の 3〜5 の位置を参照するビュー subarr が得られる。ビューは要素をコピーせず、参照のみを提供する。ここで、列の要素を変更するメソッドがあると仮定する。例えば、以下の negate メソッドは、与えれれた整数列の全ての要素の符号を反転する。

scala> def negate(xs: collection.mutable.Seq[Int]) =

for (i <- 0 until xs.length) xs(i) = -xs(i)

negate: (xs: scala.collection.mutable.Seq[Int])Unit

配列 arr の 3〜5 の位置の要素の符号を反転したいとする。これに negate が使えるだろうか。ビューを使えば、簡単にできる:

scala> negate(subarr)

scala> arr

res4: Array[Int] = Array(0, 1, 2, -3, -4, -5, 6, 7, 8, 9)

何が起こったかと言うと、negate は subarr内の全ての要素を変更したが、実際にはそれは arr の要素のスライスだったというわけだ。ここでも、ビューがモジュール性を保つのに役立っているのが分かるだろう。上記のコードは、メソッドをどの添字の範囲に適用するのかという問題と、どのメソッドを適用するのかという問題を見事に切り離している。

これだけ粋なビューの使用例を見た後だと、なぜ正格コレクションがあるのか疑問に思うかもしれない。理由の一つとして、性能を比較すると遅延コレクションが常に正格コレクションに勝るとは限らないというものがある。コレクションのサイズが小さい場合、ビュー内でクロージャを作成し適用するためのオーバーヘッドが中間結果のためのデータ構造を回避するコストを上回ってしまうことが多いのだ。恐らくより重要な理由として、遅延した演算が副作用を伴う場合、ビューの評価が非常に混乱したものとなってしまうというものがある。

Scala 2.8 以前で多くのユーザが陥った失敗例を以下に示す。これらのバージョンでは Range 型が遅延評価されたため、実質的にビューのように振舞った。多くの人が以下のようにして複数の actor を作成しようとした:

val actors = for (i <- 1 to 10) yield actor { ... }

actor メソッドと後続の中括弧に囲まれたコードは actor を作成し始動するべきだが、驚いた事にどの actor も実行されていなかった。なぜ何も起こらなかったのかは、for 式が map の適用と等価であることを思い出せば説明がつく:

val actors = (1 to 10) map (i => actor { ... })

(1 to 10) により生成された範囲はビューのように振舞ったため、map の戻り値もビューとなった。つまり、どの要素も計算されず、結果的にどの actor も作成されなかったのだ! 範囲の式全体を強制実行すれば actor は作成されただろうが、actor を作動させるためにそれが必要なことは全く明白では無い。

このような不意打ちを避けるため、Scala 2.8 ではより規則的なルールを採用する。ストリームを除く、全てのコレクションは正格評価される。正格コレクションから遅延コレクションに移行する唯一の方法は view メソッドによる。戻る唯一の方法は force による。よって、Scala 2.8 では先程の actors の定義は期待した通りに 10個の actor を作成し始動する。以前のような、予期しない振る舞いをさせるには、明示的に view メソッドを呼び出す必要がある。

val actors = for (i <- (1 to 10).view) yield actor { ... }

まとめると、ビューは効率性の問題とモジュール性の問題を仲裁する強力な道具だ。しかし、遅延評価の面倒に巻き込まれないためには、ビューの使用は二つのシナリオに限るべきだ。一つは、ビューの適用を副作用を伴わない純粋関数型のコードに限ること。もしくは、明示的に全ての変更が行われる可変コレクションに適用することだ。避けたほうがいいのは、ビューと新たなコレクションを作成しつつ副作用を伴う演算を混合することだ。