scala traversable collection
Scala 2.8 breakOut (3)
Daniel Sobralの答えは素晴らしく、 Scala CollectionsのArchitecture（ScalaのProgrammingの第25章）と一緒に読まれるべきです。
私はちょうどそれがbreakOutと呼ばれる理由を詳しく説明したいとbreakOutます：
breakOutと呼ばれるのはなぜですか？
私たちはあるタイプから別のタイプへと脱出したいからです。
どんなタイプからどんなタイプに飛び出しますか？ 例としてSeqのmap関数を見てみましょう：
Seq.map[B, That](f: (A) -> B)(implicit bf: CanBuildFrom[Seq[A], B, That]): That
次のようなシーケンスの要素をマッピングしてMapを直接作成したい場合：
val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))
コンパイラは文句を言うだろう：
error: type mismatch;
found : Seq[(String, Int)]
required: Map[String,Int]
その理由は、Seqが別のSeqを構築する方法しか知っていないからです。つまり、暗黙のCanBuildFrom[Seq[_], B, Seq[B]] Builderファクトリが利用可能ですが、SeqからMapへのBuilderファクトリはありません。
コンパイルするには、型の要件のbreakOutを必要とし、 map関数が使用するMapを生成するBuilderを構築できるようにする必要があります。
Danielが説明したように、breakOutには次のシグネチャがあります。
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()
}
すべてのクラスのサブクラスはNothingので、任意のBuilderファクトリをimplicit b: CanBuildFrom[Nothing, T, To]代わりに使用できます。 breakOut関数を使用して暗黙のパラメーターを指定した場合：
val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))(collection.breakOut)
コンパイラは暗黙的なビルダーファクトリを見つけることができるが、 CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]]はCanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]]の必要な型を提供できるのでコンパイルする。 CanBuildFrom[Nothing, T, To]代わりにCanBuildFrom[Map[_, _], (A, B), Map[A, B]]を使用して、実際のビルダーの作成に使用します。
CanBuildFrom[Map[_, _], (A, B), Map[A, B]]はMapで定義され、基礎となるMapを使用するMapBuilderを開始するだけであることにMapBuilderしてください。
これは物事をクリアすることを願っています。
Scala 2.8では、 scala.collection.package.scalaオブジェクトがあります：
def breakOut[From, T, To](implicit b : CanBuildFrom[Nothing, T, To]) =
new CanBuildFrom[From, T, To] {
def apply(from: From) = b.apply() ; def apply() = b.apply()
}
私はこの結果が次のように伝えられています：
> import scala.collection.breakOut
> val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x))(breakOut)
map: Map[Int,String] = Map(6 -> London, 5 -> Paris)
ここで何が起こっているのですか？ なぜ私のList 引数として breakOutが呼び出されていますか？
breakOut動作を理解するための簡単な例：
scala> import collection.breakOut
import collection.breakOut
scala> val set = Set(1, 2, 3, 4)
set: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)
scala> set.map(_ % 2)
res0: scala.collection.immutable.Set[Int] = Set(1, 0)
scala> val seq:Seq[Int] = set.map(_ % 2)(breakOut)
seq: Seq[Int] = Vector(1, 0, 1, 0) // map created a Seq[Int] instead of the default Set[Int]
答えはmapの定義にありmap ：
def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That
2つのパラメータがあることに注意してください。 最初はあなたの関数であり、第2は暗黙的です。 暗黙的に指定しないと、Scalaは利用可能な最も具体的なものを選択します。
breakOutについて
では、 breakOutの目的はbreakOutですか？ 文字列のリストを取得し、各文字列をタプル(Int, String)に変換してMap生成するという質問に対して与えられた例を考えてみましょう。 これを行う最も明白な方法は、中間のList[(Int, String)]コレクションを生成し、それを変換することです。
そのmapがBuilderを使用して結果のコレクションを生成すると、中間Listをスキップしてその結果をMap直接収集することはできませんか？ 明らかに、はい、そうです。 しかし、これを行うには、適切なCanBuildFromをmapに渡す必要があります。これはまさにbreakOut機能です。
breakOutの定義を見てみましょう：
def breakOut[From, T, To](implicit b : CanBuildFrom[Nothing, T, To]) =
new CanBuildFrom[From, T, To] {
def apply(from: From) = b.apply() ; def apply() = b.apply()
}
breakOutはパラメータ化されており、 CanBuildFromインスタンスを返すことに注意してください。 それが起こると、 From 、 T 、 To型は、 mapがCanBuildFrom[List[String], (Int, String), Map[Int, String]]予期していることを既に知っているので、既に推測されています。 したがって：
From = List[String]
T = (Int, String)
To = Map[Int, String]
結論として、 breakOut自体が受け取った暗黙的な内容を調べてみましょう。 CanBuildFrom[Nothing,T,To]のタイプCanBuildFrom[Nothing,T,To] 。 私たちはすでにこれらのすべての型を知っているので、型CanBuildFrom[Nothing,(Int,String),Map[Int,String]]暗黙の型が必要であると判断できます。 しかし、そのような定義はありますか？
CanBuildFromの定義を見てみましょう：
trait CanBuildFrom[-From, -Elem, +To]
extends AnyRef
したがって、 CanBuildFromは、最初の型パラメータのCanBuildFrom型です。 Nothingはボトムクラス（つまり、すべてのサブクラス）であるため、 Nothing代わりにどのクラスも使用できます。
このようなビルダーが存在するので、Scalaはそれを使用して目的の出力を生成できます。
ビルダーについて
Scalaのコレクションライブラリの多くのメソッドは、元のコレクションを取り出し、何らかの形で処理し（ mapの場合は各要素を変換する）、結果を新しいコレクションに格納することから成ります。
コードの再利用を最大限にするために、この結果の格納はビルダ （ scala.collection.mutable.Builder ）によって行われます。これは基本的に、要素の追加と結果のコレクションの2つの操作をサポートしています。 この結果として得られるコレクションのタイプは、ビルダーのタイプによって異なります。 したがって、 List BuilderはListを返し、 Map BuilderはMapを返します。 mapメソッドの実装は、結果の型に関わる必要はありません。ビルダーがそれを処理します。
一方、 mapはこのビルダーを何とか受け取る必要があることを意味しmap 。 Scala 2.8 Collectionsを設計する際に直面する問題は、可能な限り最良のビルダーを選択する方法でした。 たとえば、 Map('a' -> 1).map(_.swap)と書くと、 Map(1 -> 'a')返したいと思います。 一方、 Map('a' -> 1).map(_._1)はMap （それはIterable返します）を返すことはできません。
既知の型の式から最良のBuilderを生成するという魔法は、このCanBuildFrom暗黙的に実行されます。
CanBuildFromについて
何が起こっているのかを詳しく説明するために、マップされているコレクションがListではなくマップである例を挙げます。 後でListに戻ってきます。 今のところ、次の2つの表現を考えてみましょう。
Map(1 -> "one", 2 -> "two") map Function.tupled(_ -> _.length)
Map(1 -> "one", 2 -> "two") map (_._2)
最初のMapはMapを返し、2番目のMapはIterable返します。 フィッティングコレクションを返すという魔法はCanBuildFromの仕事です。 それを理解するためにmapの定義をもう一度考えてみましょう。
メソッドmapはTraversableLikeから継承されます。 これはBとThatでパラメータ化され、クラスをパラメータ化する型パラメータAとReprを使用します。 両方の定義を一緒に見てみましょう：
TraversableLikeクラスは次のように定義されています。
trait TraversableLike[+A, +Repr]
extends HasNewBuilder[A, Repr] with AnyRef
def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That
AとReprがどこから来たのかを理解するために、 Map自体の定義を考えてみましょう：
trait Map[A, +B]
extends Iterable[(A, B)] with Map[A, B] with MapLike[A, B, Map[A, B]]
TraversableLikeはMapを拡張するすべての形質によって継承されるため、 AとReprはそれらのいずれかから継承できます。 しかし、最後のものは好みを得る。 したがって、不変のMap定義とそれをTraversableLikeに接続するすべての特性に従って、次のようになります。
trait Map[A, +B]
extends Iterable[(A, B)] with Map[A, B] with MapLike[A, B, Map[A, B]]
trait MapLike[A, +B, +This <: MapLike[A, B, This] with Map[A, B]]
extends MapLike[A, B, This]
trait MapLike[A, +B, +This <: MapLike[A, B, This] with Map[A, B]]
extends PartialFunction[A, B] with IterableLike[(A, B), This] with Subtractable[A, This]
trait IterableLike[+A, +Repr]
extends Equals with TraversableLike[A, Repr]
trait TraversableLike[+A, +Repr]
extends HasNewBuilder[A, Repr] with AnyRef
Map[Int, String]の型パラメータをチェーンのTraversableLikeまで渡すと、 TraversableLikeに渡される型がmapによって使用されることがわかります：
A = (Int,String)
Repr = Map[Int, String]
この例に戻って、最初のマップは((Int, String)) => (Int, Int)の型の関数を受け取り、2番目のマップは型((Int, String)) => String関数を受け取ります。 私は二重括弧を使用して、受信したタプルであることを強調します。これは、 AのタイプとAです。
その情報を使って、他のタイプを考えてみましょう。
map Function.tupled(_ -> _.length):
B = (Int, Int)
map (_._2):
B = String
最初のmap返される型がMap[Int,Int]で、2番目がIterable[String]がIterable[String]ます。 mapの定義を見ると、これらがその値であることは容易にわかります。 しかし、彼らはどこから来たのですか？
関係するクラスのコンパニオンオブジェクトを調べると、それらを提供する暗黙の宣言があります。 オブジェクトMap ：
implicit def canBuildFrom [A, B] : CanBuildFrom[Map, (A, B), Map[A, B]]
また、 Iterableオブジェクトでは、 Mapで拡張されたクラスがあります。
implicit def canBuildFrom [A] : CanBuildFrom[Iterable, A, Iterable[A]]
これらの定義は、パラメータ化されたCanBuildFromファクトリを提供します。
Scalaは最も具体的な暗黙的なものを選択します。 最初のケースでは、最初のCanBuildFrom 。 2番目のケースでは、最初のケースと一致しないため、2番目のCanBuildFrom選択しCanBuildFrom 。
質問に戻る
どのように型が推定されるかを見るために、質問のコード、 Listとmapの定義を見てみましょう：
val map : Map[Int,String] = List("London", "Paris").map(x => (x.length, x))(breakOut)
sealed abstract class List[+A]
extends LinearSeq[A] with Product with GenericTraversableTemplate[A, List] with LinearSeqLike[A, List[A]]
trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]]
extends SeqLike[A, Repr]
trait SeqLike[+A, +Repr]
extends IterableLike[A, Repr]
trait IterableLike[+A, +Repr]
extends Equals with TraversableLike[A, Repr]
trait TraversableLike[+A, +Repr]
extends HasNewBuilder[A, Repr] with AnyRef
def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That
List("London", "Paris")のタイプはList[String]なので、 TraversableLike定義されたタイプAとReprは次のとおりです。
A = String
Repr = List[String]
(x => (x.length, x))は(String) => (Int, String)なので、 Bの型は：
B = (Int, String)
最後の未知の型です。 Thatはmapの結果の型です。我々はすでにそれを持っています：
val map : Map[Int,String] =
そう、
That = Map[Int, String]
つまり、 breakOutは必ずCanBuildFrom[List[String], (Int, String), Map[Int, String]]型またはサブタイプを返す必要があります。
