CanBuildFromのインスタンスはどこから湧いてくるのか

Scalaユーザの皆様は、普段からコレクションライブラリの高階関数を使われていることと思います。特に、mapやflatMapは必須の高階関数といっても良いでしょう。

さて、話は少し変わりますが、Scala 2.8以降のコレクションライブラリでは、map,flatMapなどに対して、implicitな引数 bf: CanBuildFrom がくっついています。たとえば、List[+A]#mapのシグニチャは

def map[B, That] (f: (A) ⇒ B)(implicit bf: CanBuildFrom[List[A], B, That]): That

となっています。ここで、通常のケースではimplicit paramater bfの存在を意識しなくても意図通りに動作するようにmapメソッド(正確には、意図通りにmap

メソッドが動作するように、bfに対して適切なCanBuildFromのインスタンスが渡される)は設計されており、bfに一体何が渡されるのかを知らなくても心配する

必要はありません。

とはいえ、このbfに対して、一体どういうプロセスで、どのようなインスタンスが渡されるのか、不思議に思ったことは無いでしょうか？私は不思議に思ったので調べてみました。この記事では、その調査の結果わかったことについて述べます。

と、その前にまずCanBuildFromの意味についておさらいしておきましょう。CanBuildFromはscala.collection.genericパッケージに定義されているトレイトで、次のように定義されています。

trait CanBuildFrom[-From, -Elem, +To] {

def apply(from: From): Builder[Elem, To]

// ここはとりあえず無視 def apply(): Builder[Elem, To]

}

定義としては非常に単純なトレイトですが、その意味は少しややこしいです。文章にすると、次のようになります。

CanBuildFromは、型パラメータFrom, Elem, Toを取り、Fromに与えられた型のコレクションfromから、「要素型ElemのコレクションToを構築する

ためのビルダー(Builder[Elem, To])」を生成するメソッド(applyメソッド)を提供するトレイトです。

…。例を出して説明しましょう。たとえば、CanBuildFromの型パラメータに実際の型を与えた結果できた、次のような型があったとします。

CanBuildFrom[List[A], B, List[B]]

すると、CanBuildFrom[List[A], B, List[B]]#applyのシグニチャは次のような形になります。

def apply(from: List[A]): Builder[B, List[B]]

このapplyは、元のコレクションfromを引数として取り、「型Bの情報を元にList[B]のインスタンスを生成するビルダ(Builder[B, List[B]])」を返します。ここで、Builder[...]というのはList[B]のインスタンスをうまく構築してくれる何かのインスタンスの型と考えれば十分で、本題では無い為、説明は省きます(Builderの説明に関しては、この文書が参考になるでしょう。

ここまでごちゃごちゃ書きましたが、簡潔に一文で述べると、CanBuildFromというのは、「From型のコレクションを元に、要素型ElemであるTo型のコレクションを生成するビルダ」を生成するためのファクトリということになります。ここまでがCanBuildFromのおさらいです。

さて、

implicit bf: CanBuildFrom[...]

に当てはまるインスタンスがいったいどこから湧いてくるのか、という本題に戻ります。bfに代入可能なimplicitなインスタンスが無いとそもそもmapメソッドが呼び出せませんから、どこかにそのような定義があるはずです。

答えを先に言ってしまうと、「個々のコレクション(クラス/トレイト)のコンパニオンオブジェクトの下に定義されている」というのが正解です(例外がいくつかありますが)。

たとえば、scala.collection.immutable.List[+A]のコンパニオンオブジェクトscala.collection.immutable.List(ややこしいですね)のAPIリファレンスを見てみると、

implicit def canBuildFrom[A] : CanBuildFrom[Coll, A, List[A]]

という定義があります。Collは

type Coll = List[_]

としてListの中で定義されているので、実際には

implicit def canBuildFrom[A] : CanBuildFrom[List[_], A, List[A]]

という定義になります。このような形の定義は見慣れないかもしれませんが、これは、「任意の型Aに対して、implicitなCanBuildFrom[List[_], A, List[A]]のインスタンスを生成できる」ことを意味しています。

これを踏まえて、

scala> List(1).map{x => x * 2}

res0: List[Int] = List(2)

という呼び出しの裏でどういう現象が起きているのかを考えてみましょう。

まず、mapのレシーバはList(1)ですから、その型はList[Int]です。また、mapに渡される関数の返り値型は、型推論アルゴリズムによってIntと推論されます。この状態で、mapの呼び出しが実際にどうなっているのかを型パラメータを当てはめて確かめてみることにします。

List[+A]#mapのシグニチャは

def map[B, That] (f: (A) ⇒ B)(implicit bf: CanBuildFrom[List[A], B, That]): That

で、A = List[Int]、 B = Int が確定しているため、

List(1).map{x => x * 2}

という呼び出しは、実際には

List(1).map[Int, That](f: Int => Int)(implicit bf: CanBuildFrom[List[Int], Int, That]): That

となります。ここで、Thatが未確定ですが、型推論アルゴリズムは、

bf: CanBuildFrom[List[Int], Int, That]

と互換性のあるimplicitな定義

implicit def canBuildFrom[A] : CanBuildFrom[List[_], A, List[A]]

をまず見つけます。その上で、canBuildFrom[A]の A = Int, That = List[Int] と推論し、canBuildFrom[Int]の呼び出し結果のインスタンスを引数としてbfに渡します。

このように、Scala 2.8以降のコレクションライブラリの裏では、なにげないmapの呼び出しの裏でさえ、色々な事が行われています。

ただし、再度言いますが、mapを呼び出すだけのユーザは普段からこのことを意識する必要はありません。一方、既存のコレクションに対してPimp my libraryパターンでメソッドを追加したり、新たなコレクションを既存のコレクションの継承階層に追加する人は、このような事を知っておかなければ、思わぬところでつまずく可能性があります。