Scala 2.8 breakout

Question

In Scala 2.8 gibt es ein Objekt in 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() 
} 

Ich habe gesagt, dass dies zu:

> 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) 

Was ist hier los? Warum heißt breakOutals Argument zu meinem List?

Answer 1

ist die Antwort auf die Definition von map gefunden:

def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That 

Beachten Sie, dass es zwei Parameter. Der erste ist Ihre Funktion und der zweite ist ein impliziter. Wenn Sie das nicht implizit angeben, wählt Scala das am häufigsten verfügbare spezifische.

Über breakOut

Also, was ist der Zweck der breakOut? Betrachten Sie das Beispiel, das für die Frage angegeben wurde. Sie nehmen eine Liste von Zeichenfolgen, wandeln jede Zeichenfolge in ein Tupel (Int, String) um und erstellen dann eine Map daraus. Der naheliegendste Weg, um das zu tun, würde eine Vermittler List[(Int, String)] Ansammlung produzieren und sie dann umwandeln.

Da map verwendet eine Builder die resultierende Sammlung zu produzieren, wäre es nicht möglich sein, den Vermittler List zu überspringen und die Ergebnisse direkt in ein Map sammeln? Offensichtlich, ja, ist es. Um dies zu tun, müssen wir jedoch eine ordnungsgemäße CanBuildFrom zu map übergeben, und das ist genau das, was breakOut tut.

Schauen wir uns also bei der Definition von 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() 
    } 

Beachten Sie, dass breakOut parametriert, und dass es gibt eine Instanz von CanBuildFrom. Wie es passiert, die Typen From, T und To wurden bereits abgeleitet, weil wir wissen, dass mapCanBuildFrom[List[String], (Int, String), Map[Int, String]] erwartet wird. Deshalb:

From = List[String] 
T = (Int, String) 
To = Map[Int, String] 

Zum Schluss wollen wir die von breakOut selbst erhalten implizit untersuchen. Es ist vom Typ CanBuildFrom[Nothing,T,To]. Wir kennen bereits alle diese Typen, so können wir feststellen, dass wir ein implizites vom Typ CanBuildFrom[Nothing,(Int,String),Map[Int,String]] benötigen. Aber gibt es eine solche Definition?

Schauen wir uns CanBuildFrom ‚s Definition:

trait CanBuildFrom[-From, -Elem, +To] 
extends AnyRef 

So CanBuildFrom ist kontravarianten auf seiner ersten Typ-Parameter. Weil Nothing eine untere Klasse ist (dh, es ist eine Unterklasse von allem), bedeutet das, dass eine beliebige Klasse anstelle von Nothing verwendet werden kann.

Da ein solcher Builder existiert, kann Scala ihn verwenden, um die gewünschte Ausgabe zu erzeugen.

Über Builders

Viele Methoden aus Scala die Sammlungen Bibliothek besteht der ursprünglichen Sammlung von Nahme, Bearbeitung es irgendwie (im Fall von map, Transformieren jedes Element), und Speichern der Ergebnisse in einer neuen Kollektion .

Code-Wiederverwendung zu maximieren, diese Speicherung der Ergebnisse wird durch einenbuilder getan (scala.collection.mutable.Builder), die im Wesentlichen zwei Operationen unterstützt: Anhänge von Elementen und die resultierende Sammlung zurück. Der Typ dieser resultierenden Sammlung hängt vom Typ des Builders ab. So wird ein List Builder einen List zurückgeben, ein Map Builder wird einen Map zurückgeben, und so weiter. Die Implementierung der map Methode muss sich nicht mit der Art des Ergebnisses befassen: der Builder kümmert sich darum.

Auf der anderen Seite bedeutet das, dass map diesen Builder irgendwie erhalten muss. Das Problem bei der Entwicklung von Scala 2.8 Collections bestand darin, wie der bestmögliche Builder ausgewählt werden sollte. Zum Beispiel, wenn ich Map('a' -> 1).map(_.swap) schreiben würde, würde ich gerne eine Map(1 -> 'a') zurück bekommen. Auf der anderen Seite kann Map('a' -> 1).map(_._1) keine Map zurückgeben (es gibt eine Iterable zurück).

Die Magie der Herstellung der bestmöglichen Builder aus den bekannten Typen des Ausdrucks wird durch diese CanBuildFrom implizit durchgeführt.

Über CanBuildFrom

besser zu erklären, was los ist, werde ich ein Beispiel geben, wo die Sammlung abgebildet wird ein Map ist anstelle eines List. Ich gehe später zu List zurück. Denn jetzt, betrachten Sie diese beiden Ausdrücke:

Map(1 -> "one", 2 -> "two") map Function.tupled(_ -> _.length) 
Map(1 -> "one", 2 -> "two") map (_._2) 

Die ersten kehrt ein Map und die zweite kehrt ein Iterable. Die Magie einer passenden Kollektion ist die Arbeit von CanBuildFrom. Betrachten wir die Definition von map erneut, um es zu verstehen.

Die Methode map wurde von TraversableLike übernommen. Es ist unter B und That parametrisiert und verwendet die Typparameter A und Repr, die die Klasse parametrieren. Lassen Sie uns beide Definitionen zusammen sehen:

Die Klasse TraversableLike ist definiert als:

trait TraversableLike[+A, +Repr] 
extends HasNewBuilder[A, Repr] with AnyRef 

def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That 

Um zu verstehen, wo A und Repr kommen, wollen wir die Definition von Map selbst betrachten:

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

Weil TraversableLike wird von allen Merkmalen vererbt, die Map, A und Repr von jedem von ihnen vererbt werden können. Der Letzte bekommt jedoch die Vorliebe.Also, nach der Definition des unveränderlichen Map und alle Eigenschaften, die es zu TraversableLike verbinden, haben wir:

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 

Wenn Sie die Parameter des Typs von Map[Int, String] den ganzen Weg hinunter die Kette passieren, so finden wir, dass die Typen bestanden zu TraversableLike, und somit verwendet wird, durch map sind:

A = (Int,String) 
Repr = Map[Int, String] 

zurück zum Beispiel gehen, wird die erste Karte eine Funktion vom Typ ((Int, String)) => (Int, Int) und die zweite Karte empfangen ist eine Funktion des Typs ((Int, String)) => String empfängt. Ich verwende die doppelte Klammer, um zu betonen, dass es ein Tupel ist, das empfangen wird, wie es der Typ von A ist, wie wir sahen.

Mit dieser Information, betrachten wir die anderen Arten.

map Function.tupled(_ -> _.length): 
B = (Int, Int) 

map (_._2): 
B = String 

Wir können sehen, dass die Art von der ersten map zurückgekehrt ist Map[Int,Int], und das zweite ist Iterable[String]. Betrachtet man die map Definition, ist es leicht zu sehen, dass dies die Werte von That sind. Aber woher kommen sie?

Wenn wir in die Begleitobjekte der beteiligten Klassen schauen, sehen wir einige implizite Deklarationen, die sie bereitstellen. Auf Objekt Map:

implicit def canBuildFrom [A, B] : CanBuildFrom[Map, (A, B), Map[A, B]] 

Und auf Objekt Iterable, deren Klasse von Map erweitert:

implicit def canBuildFrom [A] : CanBuildFrom[Iterable, A, Iterable[A]] 

Diese Definitionen liefern Fabriken für parametrisierte CanBuildFrom.

Scala wählt das spezifischste implizite zur Verfügung. Im ersten Fall war es der erste CanBuildFrom. Im zweiten Fall, da der erste nicht übereinstimmte, wählte er den zweiten CanBuildFrom.

Zurück zur Frage

Lasst uns den Code für die Frage sehen, List 's und map' s Definition (wieder) zu sehen, wie die Typen abgeleitet werden:

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 

Der Typ von List("London", "Paris")List[String] ist, so dass die Typen und ARepr definiert auf TraversableLike sind:

A = String 
Repr = List[String] 

Der Typ für (x => (x.length, x)) ist (String) => (Int, String), so dass die Art der B ist:

B = (Int, String) 

Die letzte unbekannte Art, That ist die Art des Ergebnisses der map, und wir haben bereits, dass auch:

val map : Map[Int,String] = 

So

That = Map[Int, String] 

Das bedeutet, dass breakOut notwendigerweise einen Typ oder Subtyp von CanBuildFrom[List[String], (Int, String), Map[Int, String]] zurückgeben muss.

Answer 2

Ich möchte auf Daniels Antwort aufbauen. Es war sehr gründlich, aber wie in den Kommentaren erwähnt, erklärt es nicht, was Breakout tut.

Entnommen Re: Support for explicit Builders (2009-10-23), hier ist das, was ich glaube, Breakout tut:

Sie den Compiler einen Vorschlag darüber, welche Builder implizit (im Wesentlichen erlaubt, sie zu wählen gibt den Compiler zu wählen ., welche Fabrik es denkt, paßt die Situation am besten)

Zum Beispiel finden Sie in den folgenden:

scala> import scala.collection.generic._ 
import scala.collection.generic._ 

scala> import scala.collection._ 
import scala.collection._ 

scala> import scala.collection.mutable._ 
import scala.collection.mutable._ 

scala> 

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() 
    | } 
breakOut: [From, T, To] 
    | (implicit b: scala.collection.generic.CanBuildFrom[Nothing,T,To]) 
    | java.lang.Object with 
    | scala.collection.generic.CanBuildFrom[From,T,To] 

scala> val l = List(1, 2, 3) 
l: List[Int] = List(1, 2, 3) 

scala> val imp = l.map(_ + 1)(breakOut) 
imp: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 3, 4) 

scala> val arr: Array[Int] = l.map(_ + 1)(breakOut) 
imp: Array[Int] = Array(2, 3, 4) 

scala> val stream: Stream[Int] = l.map(_ + 1)(breakOut) 
stream: Stream[Int] = Stream(2, ?) 

scala> val seq: Seq[Int] = l.map(_ + 1)(breakOut) 
seq: scala.collection.mutable.Seq[Int] = ArrayBuffer(2, 3, 4) 

scala> val set: Set[Int] = l.map(_ + 1)(breakOut) 
seq: scala.collection.mutable.Set[Int] = Set(2, 4, 3) 

scala> val hashSet: HashSet[Int] = l.map(_ + 1)(breakOut) 
seq: scala.collection.mutable.HashSet[Int] = Set(2, 4, 3) 

Sie den Rückgabetyp wird vom Compiler implizit gewählt sehen um dem erwarteten Typ am besten zu entsprechen. Je nachdem, wie Sie die empfangende Variable deklarieren, erhalten Sie unterschiedliche Ergebnisse.

Das folgende wäre eine äquivalente Art, einen Builder anzugeben. Beachten Sie in diesem Fall wird folgern, der Compiler den erwarteten Typ basierend auf der Art des Erbauers:

scala> def buildWith[From, T, To](b : Builder[T, To]) = 
    | new CanBuildFrom[From, T, To] { 
    |  def apply(from: From) = b ; def apply() = b 
    | } 
buildWith: [From, T, To] 
    | (b: scala.collection.mutable.Builder[T,To]) 
    | java.lang.Object with 
    | scala.collection.generic.CanBuildFrom[From,T,To] 

scala> val a = l.map(_ + 1)(buildWith(Array.newBuilder[Int])) 
a: Array[Int] = Array(2, 3, 4) 

Answer 3

Ein einfaches Beispiel zu verstehen, was breakOut tut:

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] 

Answer 4

Daniel Sobral Antwort ist groß, und sollte lesen Sie zusammen mit Architecture of Scala Collections (Kapitel 25 der Programmierung in Scala).

Ich wollte nur auf auszuarbeiten, warum es breakOut genannt wird:

Warum es breakOut genannt wird?

Da wir aus einem Typ zum Pause wollen und in eine andere:

Pause aus, welche Art in welcher Art? Schauen wir uns die map Funktion auf Seq als Beispiel:

val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length)) 

Der Compiler würde sich beschweren:

Seq.map[B, That](f: (A) -> B)(implicit bf: CanBuildFrom[Seq[A], B, That]): That 

Wenn wir eine Karte direkt von Mapping über die Elemente einer Sequenz wie bauen wollte:

error: type mismatch; 
found : Seq[(String, Int)] 
required: Map[String,Int] 

Der Grund dafür ist, dass Seq nur weiß, wie man eine andere Seq zu bauen (dh es gibt einen impliziten CanBuildFrom[Seq[_], B, Seq[B]] builder Fabrik verfügbar, aber es gibt NO Erbauerfabrik von Seq zur Karte).

Um zu kompilieren müssen wir irgendwie breakOut der Typ Anforderung, und in der Lage sein, einen Baumeister zu konstruieren, die eine Karte für die map Funktion verwenden produziert.

Wie Daniel erklärt hat, hat breakout die folgende Signatur:

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 eine Unterklasse aller Klassen ist, so dass jede builder Fabrik kann anstelle von implicit b: CanBuildFrom[Nothing, T, To] ersetzt werden. Wenn wir die breakout-Funktion verwendet, um den impliziten Parameter zur Verfügung zu stellen:

val x: Map[String, Int] = Seq("A", "BB", "CCC").map(s => (s, s.length))(collection.breakOut) 

Es wäre kompilieren, weil breakOut der Lage ist, die erforderliche Art von CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]] zu schaffen, während der Compiler eine implizite builder Fabrik des Typs zu finden ist in der Lage CanBuildFrom[Map[_, _], (A, B), Map[A, B]], anstelle von CanBuildFrom[Nothing, T, To], für breakOut zu verwenden, um den tatsächlichen Builder zu erstellen.

Beachten Sie, dass CanBuildFrom[Map[_, _], (A, B), Map[A, B]] in Map definiert ist und einfach eine MapBuilder initiiert, die eine zugrunde liegende Map verwendet.

Hoffe das klärt die Dinge auf.