|
|
|
共通する演算の摘出 | 目次 |
| package scala.collection | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| class TraversableLike[+Elem, +Repr] { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def newBuilder: Builder[Elem, Repr] // 後述する | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def foreach[U](f: Elem => U) // 後述する | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ... | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def filter(p: Elem => Boolean): Repr = { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| val b = newBuilder | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| foreach { elem => if (p(elem)) b += elem } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| b.result | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
コレクションライブラリ再設計の主な設計目標は自然な型と実装コード共有の最大化を同時に実現することだった。特に、Scala のコレクションは「戻り値同型」の原則 ("same-result-type" principle) を採用しており、コレクションの変換メソッドは、できる限り同じ型のコレクションを返すようにしている。例えば、filter 演算は全てのコレクション型において、同じコレクション型のインスタンスを返すべきだ。List に filter を適用すれば List を返すし、Map は Map を返す、という具合だ。これから、これがどう実現されているのかを見てみようと思う。
Scala コレクションライブラリは、いわゆる実装トレイト (implementation trait) を用いてジェネリックなビルダとコレクションの探索を実装することで、「戻り値同型」の原則を実現しながらもコードの重複を避けている。これらのトレイトは語尾に Like が付くように命名されており、例えば、 IndexedSeqLike は IndexedSeq の実装トレイトであり、同様に TraversableLike は Traversable の実装トレイトだ。Traversable や IndexedSeq のようなコレクションクラスはこれらのトレイトから全ての具象メソッド (concrete method) の実装を継承している。普通のコレクションには一つの型パラメータがあるが、実装トレイトには二つの型パラメータがある。実装トレイトはコレクションの要素型についてパラメータ化するだけではなく、コレクションの表現型 (representation type)、つまり Seq[I] や List[T] のような実際のコレクションの型そのものをパラメータ化する。例えば、ここに TraversableLike トレイトのヘッダを示す:
| trait TraversableLike[+Elem, +Repr] { ... } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
型パラメータの Elem は Traversable の要素型 (element type) を表し、型パラメータの Repr はその表現 (representation) を表す。Repr には制限が無い。特に、Repr は Traversable の子クラスではない型にインスタンス化される可能性がある。これにより、コレクション階層の外部にある String や Array もコレクションの実装トレイトにある全ての演算を利用することができる。
filter を例にとると、この演算は TraversableLike トレイト内で一度だけ全てのコレクションに対して実装されている。大まかなコードの概要は上記の TraversableLike クラスの概要にて示されている。このトレイトは、後に具象コレクションクラスで実装される newBuilder と foreach という二つの抽象メソッドを宣言する。filter 演算は、これらのメソッドを使って全てのコレクションに対して同様に実装されている。まず、newBuilder を用いて表現型 Repr の新しいビルダが構築される。次に、foreach を用いて現コレクション内の全ての要素が探索される。要素 x が与えられた条件関数 p を満たせば（つまり、p(x) が true を返せば）、その要素はビルダに追加される。最後に、ビルダの result メソッドを呼び出すことで、ビルダの中に収集された要素は Repr コレクション型のインスタンスとして返される。
コレクションの map 演算はもう少し複雑だ。 例えば、f が String から Int への関数で、xs が List[String] だとすると、xs map f は List[Int] を返さなくてはならない。同様に、ys が Array[String] ならば、ys map f は Array[Int] を返さなくてはならない。問題は、map メソッドの定義をリストと配列で重複させずに、どうこれを実現させるかということだ。TraversableLike クラスの例で見た newBuilder/foreach フレームワークは、コレクションと同じ型の新しいインスタンスしか生成できないため不十分だ。map は、型コンストラクタ (type constructor) は同じでも、要素型が異なりうるコレクションの新しいインスタンスが必要になるからだ。
さらに、map のような関数の戻り値は、型コンストラクタさえも自明でない形で他の引数の型に依存する可能性がある。以下に具体例で説明する:
| scala> import collection.immutable.BitSet | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| import collection.immutable.BitSet | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| scala> val bits = BitSet(1, 2, 3) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| bits: scala.collection.immutable.BitSet = BitSet(1, 2, 3) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| scala> bits map (_ * 2) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res13: scala.collection.immutable.BitSet = BitSet(2, 4, 6) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| scala> bits map (_.toFloat) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res14: scala.collection.immutable.Set[Float] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| = Set(1.0, 2.0, 3.0) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
あるビット集合について二倍にする関数 _ * 2 を map すると、もう一つのビット集合が得られる。しかし、同じビット集合について関数 (_.toFloat) を map すると、戻り値は一般集合の Set[Float] となる。もちろん、ビット集合は Float でなく Int を含むため、ビット集合ではありえない。
map の戻り値の形が渡された関数の形に依存することに注意してほしい。関数引数の戻り値が再び Int である場合は map 戻り値の形も BitSet だが、関数引数の型がそれ以外の場合は map の戻り値の型はただの Set となる。このような型の柔軟性が Scala でどのように実現されているのかを見てみよう。
この BitSet の問題は単発のものではない。ここに、マップに対して関数を map するインタプリタとのやりとりによる具体例を二つ示す:
| scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => (y, x) } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res3: scala.collection.immutable.Map[Int,java.lang.String] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| = Map(1 -> a, 2 -> b) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => y } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| res4: scala.collection.immutable.Iterable[Int] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| = List(1, 2) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
最初の関数はキー/値ペアの二つの引数を交換する。この転換の戻り値は再びマップだが、逆方向を向いている。事実、最初の式は元のマップが可逆 (invertible) である場合、逆写像 (inverse mapping) を表す。 しかし、第二の関数はキー/値ペアを、単一の整数（値成分）に写像する。この場合、戻り値から Map を形成することはできないが、その親トレイトである Iterable を形成することができる。
なぜ map を同じ種類のコレクションを返すように制限しないのかと疑問に思うかもしれない。例えば、ビット集合の map は「 Int を取り Int を返す」の関数のみを受け入れ、マップは「ペアを取りペアを返す」関数のみを受け入れるということだ。このような制限はオブジェクト指向のモデリングという視点から望ましくないだけでなく、リスコフの置換原則 (Liskov substitution principle) に反するため違法である。全ての Map は Iterable である。 そのため、Iterable について合法な全ての演算は Map についても合法でなくてはならない。
Scala はこの問題をオーバーロードを用いて解決するが、これは（十分に柔軟ではないため） Java から継承した単純な形のオーバーロードではなく、暗黙のパラメータ (implicit parameter) により提供される体系的な形のオーバーロードだ。
| def map[B, That](p: Elem => B) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (implicit bf: CanBuildFrom[B, That, This]): That = { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| val b = bf(this) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| for (x <- this) b += f(x) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| b.result | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
上記のコードは TraversableLike トレイトの map の実装を示す。TraversableLike クラスの例で見た filter の例に似ている。主な違いは、filter が TraversableLike クラスの抽象メソッドである newBuilder メソッドを用いた所に、 map は、暗黙のパラメータとして渡される CanBuildFrom 型のビルダファクトリ (builder factory) を使っていることだ。
| package scala.collection.generic | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| trait CanBuildFrom[-From, -Elem, +To] { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| // 新しいビルダを作成する | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| def apply(from: From): Builder[Elem, To] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
上記のコードは、ビルダファクトリを表す CanBuildFrom トレイトの定義を示す。構築されるコレクションの要素型を示す Elem、構築するコレクションの型の To、そしてこのビルダファクトリが適用される型を示す From の三つの型パラメータを持つ。適切な暗黙のビルダファクトリを定義することによって、型の振る舞いを必要に応じて適応させることができる仕組みだ。BitSet クラスを例にとる。このコンパニオンオブジェクトは CanBuildFrom[BitSet, Int, BitSet] 型のビルダファクトリを含む。これは、BitSet について演算をするとき、構築されるコレクションの要素型が Int である限りもう一つの BitSet が構築されるということを意味する。そうでない場合は、いつでも別の暗黙のビルダファクトリに後退することができ、この場合は mutable.Set のコンパニオンオブジェクトによって実装されるものになる。このビルダファクトリは、ジェネリックな型パラメータ A を取るより一般的な型だ:
| CanBuildFrom[Set[_], A, Set[A]] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
これは、存在型 (existential type) Set[_] によって表現された任意の Set についての演算は、要素型 A が何であろうとも、Set を再び構築することができることを意味する。このように二つの暗黙の CanBuildFrom のインスタンスがある場合、最も特定されており適切なものを選ぶという Scala の暗黙のパラメータ解決 (implicit resolution) の規則に頼ることができる。
暗黙のパラメータ解決は map のようなトリッキーなコレクション演算の正しい静的型を提供することが分かった。しかし、動的型についはどうだろう。具体的には、Iterable を静的型とするリストの値があったとして、その値についてなんらかの関数を map したとする:
| scala> val xs: Iterable[Int] = List(1, 2, 3) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| xs: Iterable[Int] = List(1, 2, 3) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| scala> val ys = xs map (x => x * x) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ys: Iterable[Int] = List(1, 4, 9) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
上記の ys の静的型は、期待どおり Iterable だ。しかし、動的型は List のままであり、そうであるべきだ。この振る舞いはもう一段階の抽象化によって実現されている。CanBuildFrom の apply メソッドに元のコレクションが引数として渡されているのだ。ジェネリックな Traversable のためのビルダファクトリの多く（末端クラスのためのビルダファクトリ以外は全て）は、これをコレクションの genericBuilder メソッドに委譲する。genericBuilder メソッドは、自身が定義されているコレクションのビルダを呼び出す。つまり、Scala は静的な暗黙のパラメータ解決を用いて map の型制限を解決するが、この制限に最適な動的型は仮想ディスパッチ (virtual dispatch) によって選択されている。
続いては、新しいコレクションの参入
|
|
|
共通する演算の摘出 | 目次 |