Scala 2.8 breakOut

225

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

Mir wurde gesagt, dass dies zu folgenden Ergebnissen führt:

> 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 geht hier vor sich? Warum wird breakOutich als Argument für mich gerufen List?

oxbow_lakes
quelle
13
Die triviale Antwort lautet: Es ist kein Argument dafür List, sondern für map.
Daniel C. Sobral

Antworten:

325

Die Antwort findet sich in der Definition von map:

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

Beachten Sie, dass es zwei Parameter hat. Das erste ist Ihre Funktion und das zweite ist implizit. Wenn Sie dieses Implizit nicht angeben, wählt Scala das spezifischste aus verfügbare aus.

Über breakOut

Also, was ist der Zweck von breakOut? Betrachten Sie das Beispiel für die Frage: Sie nehmen eine Liste von Zeichenfolgen, wandeln jede Zeichenfolge in ein Tupel um (Int, String)und erstellen dann eineMap Out. Der naheliegendste Weg, dies zu tun, wäre, eine Zwischensammlung zu erstellen List[(Int, String)]und diese dann zu konvertieren.

Wäre es angesichts der mapVerwendung von a Builderzur Erstellung der resultierenden Sammlung nicht möglich, den Vermittler zu überspringen Listund die Ergebnisse direkt in a zu sammeln Map? Offensichtlich ja. Dazu müssen wir jedoch ein Eigenes CanBuildFroman übergebenmap , und das ist genau das, was der breakOutFall ist.

Schauen wir uns also die Definition von an 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 dies breakOutparametrisiert ist und eine Instanz von zurückgibt CanBuildFrom. Wie es passiert, die Typen From, Tund Tohaben bereits geschlossen worden, weil wir wissen , dass maperwartet wird CanBuildFrom[List[String], (Int, String), Map[Int, String]]. Deshalb:

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

Lassen Sie uns abschließend das von sich breakOutselbst empfangene Implizit untersuchen . Es ist vom TypCanBuildFrom[Nothing,T,To] . Wir kennen bereits alle diese Typen, sodass wir feststellen können, dass wir einen impliziten Typ benötigen CanBuildFrom[Nothing,(Int,String),Map[Int,String]]. Aber gibt es eine solche Definition?

Schauen wir uns die CanBuildFromDefinition an:

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

So CanBuildFromist Gegenvariante auf seinem ersten Typparameter. Da Nothinges sich um eine unterste Klasse handelt (dh um eine Unterklasse von allem), bedeutet dies, dass jede Klasse anstelle von verwendet werden kannNothing .

Da es einen solchen Builder gibt, kann Scala damit die gewünschte Ausgabe erzeugen.

Über Bauherren

Viele Methoden aus der Sammlungsbibliothek von Scala bestehen darin, die ursprüngliche Sammlung zu übernehmen und sie irgendwie zu verarbeiten (im Fall von map Transformation jedes Elements) und die Ergebnisse in einer neuen Sammlung zu speichern.

Um die Wiederverwendung von Code zu maximieren, erfolgt diese Speicherung der Ergebnisse über einen Builder ( scala.collection.mutable.Builder), der grundsätzlich zwei Vorgänge unterstützt: Anhängen von Elementen und Zurückgeben der resultierenden Auflistung. Der Typ dieser resultierenden Sammlung hängt vom Typ des Builders ab. Ein ListBuilder gibt also a zurück List, ein MapBuilder gibt a zurückMap und so weiter. Die Implementierung der mapMethode muss sich nicht mit der Art des Ergebnisses befassen: Der Builder kümmert sich darum.

Auf der anderen Seite bedeutet das map, dass dieser Builder irgendwie empfangen werden muss. Das Problem beim Entwerfen von Scala 2.8-Sammlungen bestand darin, den bestmöglichen Builder auszuwählen. Wenn ich zum Beispiel schreiben würde Map('a' -> 1).map(_.swap), würde ich gerne eine Rückerstattung bekommen Map(1 -> 'a'). Auf der anderen Seite Map('a' -> 1).map(_._1)kann a a nicht zurückgeben Map(es gibt ein zurückIterable ).

Die Magie, Builderaus den bekannten Ausdruckstypen das bestmögliche zu erzeugen, wird durch dieses CanBuildFromImplizit ausgeführt.

Über CanBuildFrom

Um besser zu erklären, was los ist, gebe ich ein Beispiel, in dem die zugeordnete Sammlung eine Mapanstelle einer ist List. Ich werde Listspäter darauf zurückkommen . Betrachten Sie zunächst diese beiden Ausdrücke:

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

Der erste gibt a zurück Mapund der zweite gibt a zurück Iterable. Die Magie der Rückgabe einer passenden Sammlung liegt in der Arbeit von CanBuildFrom. Betrachten wir die Definition von noch mapeinmal, um sie zu verstehen.

Die Methode mapwird von geerbt TraversableLike. Es wird auf Bund parametrisiert und Thatverwendet die Typparameter Aund Repr, die die Klasse parametrisieren. Sehen wir uns beide Definitionen zusammen an:

Die Klasse TraversableLikeist 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, woher Aund woher sie Reprkommen, betrachten wir die Definition von sich Mapselbst:

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

Weil TraversableLikees von allen Merkmalen geerbt wird, die sich erstrecken Map, Aund Reprvon jedem von ihnen geerbt werden könnte. Der letzte bekommt jedoch die Präferenz. Nach der Definition des Unveränderlichen Mapund aller Merkmale, mit denen es verbunden ist TraversableLike, haben wir also:

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 Typparameter Map[Int, String]entlang der gesamten Kette übergeben, stellen wir fest, dass die Typen, die an übergeben TraversableLikewerden und daher von verwendet werden map, folgende sind:

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

Zurück zum Beispiel: Die erste Karte empfängt eine Funktion vom Typ ((Int, String)) => (Int, Int)und die zweite Karte empfängt eine Funktion vom Typ ((Int, String)) => String. Ich benutze die doppelte Klammer, um zu betonen, dass es sich um ein empfangenes Tupel handelt, Awie wir es gesehen haben.

Betrachten wir mit diesen Informationen die anderen Typen.

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

map (_._2):
B = String

Wir können sehen , dass der Typ von der ersten zurück mapist Map[Int,Int], und das zweite ist Iterable[String]. Wenn man sich mapdie Definition ansieht, ist leicht zu erkennen, dass dies die Werte von sindThat . Aber woher kommen sie?

Wenn wir uns die Begleitobjekte der beteiligten Klassen ansehen, 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, dessen Klasse erweitert wird durch Map:

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

Diese Definitionen bieten Fabriken zur Parametrisierung CanBuildFrom.

Scala wählt das spezifischste verfügbare Implizit aus. 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

Sehen wir uns den Code für die Frage, Listdie mapDefinition von 'und ' (noch einmal) an, um 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")ist List[String], also sind die Typen Aund Reprdefiniert auf TraversableLike:

A = String
Repr = List[String]

Der Typ für (x => (x.length, x))ist (String) => (Int, String), also ist der Typ von B:

B = (Int, String)

Der letzte unbekannte Typ Thatist der Typ des Ergebnisses von map, und das haben wir auch schon:

val map : Map[Int,String] =

So,

That = Map[Int, String]

Das bedeutet breakOut, dass unbedingt ein Typ oder Subtyp von zurückgegeben werden muss CanBuildFrom[List[String], (Int, String), Map[Int, String]].

Daniel C. Sobral
quelle
61
Daniel, ich kann die Typen in deiner Antwort durchgehen, aber wenn ich am Ende angekommen bin, habe ich das Gefühl, dass ich kein Verständnis auf hohem Niveau gewonnen habe. Was ist breakOut? Woher kommt der Name "breakOut" (woraus breche ich aus)? Warum wird es in diesem Fall benötigt, um eine Karte herauszuholen? Gibt es sicherlich eine Möglichkeit, diese Fragen kurz zu beantworten? (Auch wenn das langwierige Typ-Groveln notwendig bleibt, um jedes Detail zu erfassen)
Seth Tisue
3
@ Seth Das ist ein berechtigtes Anliegen, aber ich bin nicht sicher, ob ich der Aufgabe gewachsen bin. Der Ursprung davon kann hier gefunden werden: article.gmane.org/gmane.comp.lang.scala.internals/1812/… . Ich werde darüber nachdenken, aber im Moment kann ich mir keine Möglichkeit vorstellen, es zu verbessern.
Daniel C. Sobral
2
Gibt es eine Möglichkeit, die Angabe des gesamten Ergebnistyps von Map [Int, String] zu vermeiden und stattdessen Folgendes schreiben zu können: 'val map = List ("London", "Paris"). Map (x => (x). Länge, x)) (breakOut [... Map]) '
IttayD
9
@SethTisue Aus meiner Lektüre dieser Erklärung geht hervor, dass breakOut notwendig ist, um die Anforderung zu "brechen", die Ihr Builder aus einer Liste [String] erstellen muss. Der Compiler möchte ein CanBuildFrom [List [String], (Int, String), Map [Int, String]], das Sie nicht bereitstellen können. Die breakOut-Funktion erledigt dies, indem sie den ersten Typparameter in CanBuildFrom blockiert, indem sie ihn auf Nothing setzt. Jetzt müssen Sie nur noch ein CanBuildFrom [Nothing, (Int, String), Map [Int, String]] bereitstellen. Dies ist einfach, da es von der Map-Klasse bereitgestellt wird.
Mark
2
@Mark Als ich breakOut fand, war das Problem, das ich sah, die Art und Weise, wie Monaden darauf bestehen, (über bind / flatMap) ihrem eigenen Typ zuzuordnen. Es erlaubt einem, aus einer Mapping-Kette mit einer Monade in einen anderen Monadentyp "auszubrechen". Ich habe keine Ahnung, ob Adriaan Moors (der Autor) so darüber nachdachte!
Ed Staub
86

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 bewirkt.

Entnommen aus Re: Unterstützung für explizite Builder (23.10.2009) , glaube ich, dass Breakout Folgendes tut:

Es gibt dem Compiler einen Vorschlag, welchen Builder er implizit auswählen soll (im Wesentlichen kann der Compiler auswählen, welche Factory seiner Meinung nach am besten zur Situation passt.)

Siehe zum Beispiel Folgendes:

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 können sehen, dass der Rückgabetyp vom Compiler implizit so ausgewählt wird, dass er dem erwarteten Typ am besten entspricht. Je nachdem, wie Sie die empfangende Variable deklarieren, erhalten Sie unterschiedliche Ergebnisse.

Das Folgende wäre eine äquivalente Möglichkeit, einen Builder anzugeben. Beachten Sie in diesem Fall, dass der Compiler den erwarteten Typ basierend auf dem Typ des Builders ableitet:

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)
Austen Holmes
quelle
1
Ich frage mich, warum es " breakOut" heißt? Ich denke, etwas wie convertoder buildADifferentTypeOfCollection(aber kürzer) könnte leichter zu merken gewesen sein.
KajMagnus
8

Daniel Sobrals Antwort ist großartig und sollte zusammen mit Architecture of Scala Collections (Kapitel 25 der Programmierung in Scala) gelesen werden .

Ich wollte nur näher erläutern, warum es heißt breakOut :

Warum heißt es breakOut ?

Weil wir von einem Typ in einen anderen ausbrechen wollen :

Aus welchem ​​Typ in welchen Typ ausbrechen? Schauen wir uns die mapFunktion Seqals Beispiel an:

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

Wenn wir eine Map direkt aus der Zuordnung über die Elemente einer Sequenz erstellen möchten, wie z.

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

Der Compiler würde sich beschweren:

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 erstellt (dh es ist eine implizite CanBuildFrom[Seq[_], B, Seq[B]]Builder-Factory verfügbar, aber es gibt KEINE Builder-Factory von Seq bis Map).

Um zu kompilieren, müssen wir irgendwie breakOutdie Typanforderung erfüllen und in der Lage sein, einen Builder zu erstellen, der eine Map für die mapzu verwendende Funktion erstellt.

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

Nothingist eine Unterklasse aller Klassen, sodass jede Builder-Fabrik anstelle von ersetzt werden kann implicit b: CanBuildFrom[Nothing, T, To]. Wenn wir die breakOut-Funktion verwendet haben, um den impliziten Parameter bereitzustellen:

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

Es würde kompilieren, weil breakOutes in der Lage ist, den erforderlichen Typ von bereitzustellen CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]], während der Compiler in der Lage ist, eine implizite Builder-Factory vom Typ CanBuildFrom[Map[_, _], (A, B), Map[A, B]]anstelle von zu findenCanBuildFrom[Nothing, T, To] breakOut finden kann, um den tatsächlichen Builder zu erstellen.

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

Hoffe das klärt die Dinge auf.

Dzhu
quelle
4

Ein einfaches Beispiel, um zu verstehen, was breakOutbedeutet:

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]
fdietze
quelle
Danke für das Beispiel! Außerdem erhalten val seq:Seq[Int] = set.map(_ % 2).toVectorSie nicht die wiederholten Werte, da die Setfür die beibehalten wurden map.
Matthew Pickering
@MatthewPickering richtig! set.map(_ % 2)erstellt eine Set(1, 0)erste, die dann in eine konvertiert wird Vector(1, 0).
fdietze