breakOutを説明してみる

breakOutとは

val xs: Stream[Int] = Seq(1,2,3).map(_ + 1)(collection.breakOut)

toFogeしなくても戻りの型に合わせてくれて、処理効率が良いというものです。

もちろんStreamじゃなくてもVectorでもなんでも使えますし、mapじゃくてもCanBuildFromを使っている関数だったら使えます。

順番にコードを追いながら説明してみます。

まずはmapを

見てみます。

TraversableLike.scala

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    def builder = {
      val b = bf(repr)
      b.sizeHint(this)
      b
    }
    val b = builder
    for (x <- this) b += f(x)
    b.result
  }

CanBuildFromのimplicitで、builderを取得しています。

objectにimplicitが定義されています。

Seq.scala

object Seq extends SeqFactory[Seq] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]
}

ReusableCBFは、都度インスタンスの生成をしないようにするテクニックなので(=:=とかでもやってるアレ)、GenericCanBuildFrom[A]だと思えばいいです。

GenTraversableFactory.scala

class GenericCanBuildFrom[A] extends CanBuildFrom[CC[_], A, CC[A]] {
  def apply(from: Coll) = from.genericBuilder[A]
  def apply() = newBuilder[A]
}

そしてmapで、bf(repr)とあるので、↑の apply(from: Coll) が呼ばれてるわけです。

fromはSeq[Int]でgenericBuilderは、

GenericTraversableTemplate.scala

def genericBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B]

companionはSeqが持っていて、Seqのオブジェクトが入っています。

Seq.scala

trait Seq[+A] extends PartialFunction[Int, A]
                      with Iterable[A]
                      with GenSeq[A]
                      with GenericTraversableTemplate[A, Seq]
                      with SeqLike[A, Seq[A]] {
  override def companion: GenericCompanion[Seq] = Seq

  override def seq: Seq[A] = this
}

companion.newBuilder[A] なので、つまりは Seq.newBuilder[A] が呼ばれます。

Seq.newBuilderはimmutable.Seq.newBuilderを呼び、

immutable.Seq.scala

object Seq extends SeqFactory[Seq] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
  def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer
}

最後にはListBufferを返しています。

実際に実行してみると分かりますね。

scala> Seq.newBuilder[Int]
res1: scala.collection.mutable.Builder[Int,Seq[Int]] = ListBuffer()

再度mapの定義をみてみると

val b = builder (これがListBuffer)
for (x <- this) b += f(x)
b.result

ListBufferのresultはtoListして、immutable.Listを返します。REPLでSeqを作ると型がListになるのは、SeqのBuilderがListBufferだからですね。

scala> Seq(1)
res4: Seq[Int] = List(1)

SeqのBuilderがListBufferということが分かりましたが、Builderは共通のinterfaceを実装しています。

trait Builder[-Elem, +To] extends Growable[Elem] {
  def +=(elem: Elem): this.type
  def result(): To
  ...

ということは、SeqのBuilderでなくStreamのBuilderを使えばtoStreamしなくて済みそうです。

そこでbreakOutと。

breakOutを読んでみる

collection.package.scala

/** Provides a CanBuildFrom instance that builds a specific target collection (`To')
   *  irrespective of the original collection (`From').
   */
  def breakOut[From, T, To](implicit b: CanBuildFrom[Nothing, T, To]): CanBuildFrom[From, T, To] =
    // can't just return b because the argument to apply could be cast to From in b
    new CanBuildFrom[From, T, To] {
      def apply(from: From) = b.apply()
      def apply()           = b.apply()
    }

まずimplicitの CanBuildFrom[Nothing, T, To] を取りますが、

これは、CanBuildFrom[Nothing, Int, Stream[Int]] になるので、StreamのBuilderが取得されます。

なぜNothingでいいのかというと、CanBuildFromの定義が反変になっているからです。

(Scalaの世界では、一番上はAnyで一番下はNothing)

CanBuildFrom.scala

trait CanBuildFrom[-From, -Elem, +To] {
  def apply(from: From): Builder[Elem, To]
  def apply(): Builder[Elem, To]
}

そのbuilderを、新しく作ったCanBuildFromのapplyで使っているわけですね。

これでStreamのbuilderが無事mapに渡されました。

おしまい

おまけ

REPLでCanBuildFromを取得して試してみます。

scala> import scala.collection.generic.CanBuildFrom
import scala.collection.generic.CanBuildFrom

// SeqのBuilderをimplicitで取得してみる
scala> implicitly[CanBuildFrom[Seq[_], Int, Seq[Int]]]
res44: scala.collection.generic.CanBuildFrom[Seq[_],Int,Seq[Int]] = scala.collection.generic.GenTraversableFactory$$anon$1@22657db1

// ListBufferですね
scala> .apply
res45: scala.collection.mutable.Builder[Int,Seq[Int]] = ListBuffer()

// breakOutみたいにすると
scala> implicitly[CanBuildFrom[Nothing, Int, Stream[Int]]]
res46: scala.collection.generic.CanBuildFrom[Nothing,Int,Stream[Int]] = scala.collection.immutable.Stream$StreamCanBuildFrom@4ba32242