scala traversable collection




Scala 2.8 breakOut (3)

Daniel Sobralの答えは素晴らしく、 Scala CollectionsのArchitecture(ScalaのProgrammingの第25章)と一緒に読まれるべきです。

私はちょうどそれがbreakOutと呼ばれる理由を詳しく説明したいとbreakOutます:

breakOutと呼ばれるのはなぜですか?

私たちはあるタイプから別のタイプへと脱出したいからです。

どんなタイプからどんなタイプに飛び出しますか? 例としてSeqmap関数を見てみましょう:

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)]コレクションを生成し、それを変換することです。

そのmapBuilderを使用して結果のコレクションを生成すると、中間Listをスキップしてその結果をMap直接収集することはできませんか? 明らかに、はい、そうです。 しかし、これを行うには、適切なCanBuildFrommapに渡す必要があります。これはまさに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インスタンスを返すことに注意してください。 それが起こると、 FromTTo型は、 mapCanBuildFrom[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)

最初のMapMapを返し、2番目のMapIterable返します。 フィッティングコレクションを返すという魔法はCanBuildFromの仕事です。 それを理解するためにmapの定義をもう一度考えてみましょう。

メソッドmapTraversableLikeから継承されます。 これはBThatでパラメータ化され、クラスをパラメータ化する型パラメータAReprを使用します。 両方の定義を一緒に見てみましょう:

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 

AReprがどこから来たのかを理解するために、 Map自体の定義を考えてみましょう:

trait Map[A, +B] 
extends Iterable[(A, B)] with Map[A, B] with MapLike[A, B, Map[A, B]]

TraversableLikeMapを拡張するすべての形質によって継承されるため、 AReprはそれらのいずれかから継承できます。 しかし、最後のものは好みを得る。 したがって、不変の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

質問に戻る

どのように型が推定されるかを見るために、質問のコード、 Listmapの定義を見てみましょう:

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定義されたタイプAReprは次のとおりです。

A = String
Repr = List[String]

(x => (x.length, x))(String) => (Int, String)なので、 Bの型は:

B = (Int, String)

最後の未知の型です。 Thatmapの結果の型です。我々はすでにそれを持っています:

val map : Map[Int,String] =

そう、

That = Map[Int, String]

つまり、 breakOutは必ずCanBuildFrom[List[String], (Int, String), Map[Int, String]]型またはサブタイプを返す必要があります。





scala-collections