breakOutを説明してみる

## breakOutとは

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

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

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

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

## まずはmapを

見てみます。

```scala: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が定義されています。

```scala: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]だと思えばいいです。

```scala: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は、

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

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

```scala: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`を呼び、

```scala: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
scala> Seq.newBuilder[Int]
res1: scala.collection.mutable.Builder[Int,Seq[Int]] = ListBuffer()
```

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

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

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

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

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

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

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

そこでbreakOutと。

## breakOutを読んでみる

```scala: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)

```scala: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
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
```