wake-up-neo.com

Scala 2.8 breakOut

In Scala 2.8 befindet sich 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 breakOut als Argument für mein List aufgerufen?

223
oxbow_lakes

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. Der erste ist Ihre Funktion und der zweite ist ein impliziter. Wenn Sie diesen impliziten Wert nicht angeben, wählt Scala) den spezifischsten verfügbaren Wert aus.

Über breakOut

Also, was ist der Zweck von breakOut? Betrachten Sie das für die Frage gegebene Beispiel: Sie nehmen eine Liste von Zeichenfolgen, transformieren jede Zeichenfolge in ein Tupel (Int, String) Und erzeugen daraus ein Map. Der naheliegendste Weg, dies zu tun, besteht darin, eine zwischengeschaltete List[(Int, String)]-Auflistung zu erstellen und diese anschließend zu konvertieren.

Angesichts der Tatsache, dass map eine Builder verwendet, um die resultierende Sammlung zu erstellen, wäre es nicht möglich, den Vermittler List zu überspringen und die Ergebnisse direkt in einer Map? Offensichtlich ist es das. Dazu müssen wir jedoch ein richtiges CanBuildFrom an map übergeben, und genau das tut breakOut.

Schauen wir uns nun die Definition von breakOut an:

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 parametrisiert ist und eine Instanz von CanBuildFrom zurückgibt. Zufällig wurden die Typen From, T und To bereits abgeleitet, da wir wissen, dass mapCanBuildFrom[List[String], (Int, String), Map[Int, String]] erwartet. Deshalb:

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

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

Schauen wir uns die Definition von CanBuildFrom an:

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

Also ist CanBuildFrom für seinen ersten Typparameter eine Gegenvariante. Da Nothing eine untergeordnete Klasse ist (dh eine Unterklasse von allem), bedeutet dies, dass jede Klasse an Ort und Stelle verwendet werden kann von Nothing.

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

Über Builder

Viele Methoden aus der Collections-Bibliothek von Scala bestehen darin, die ursprüngliche Collection zu übernehmen, sie irgendwie zu verarbeiten (im Fall von map, jedes Element zu transformieren) und die Ergebnisse in einer neuen Collection 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 Operationen unterstützt: Anhängen von Elementen, und Zurücksenden der resultierenden Sammlung. Der Typ dieser resultierenden Auflistung hängt vom Typ des Builders ab. Ein Builder List gibt also einen Builder List zurück, ein Builder Map gibt einen Builder Map zurück, und so weiter. Die Implementierung der map -Methode muss sich nicht mit der Art des Ergebnisses befassen: Der Builder kümmert sich darum.

Andererseits bedeutet das, dass map diesen Builder irgendwie empfangen muss. Das Problem beim Entwerfen von Scala 2.8 Sammlungen war, wie man den bestmöglichen Builder auswählt. Wenn ich zum Beispiel Map('a' -> 1).map(_.swap) schreibe, möchte ich eine Map(1 -> 'a') zurückbekommen kann eine Map('a' -> 1).map(_._1) kein Map zurückgeben (es gibt ein Iterable zurück).

Die Magie, aus den bekannten Ausdruckstypen das bestmögliche Builder zu erzeugen, wird durch dieses CanBuildFrom implizit ausgeführt.

Über CanBuildFrom

Um besser zu erklären, was los ist, werde ich ein Beispiel geben, in dem die zuzuordnende Sammlung ein Map anstelle eines List ist. Ich gehe später zurück zu List. Betrachten Sie vorerst diese beiden Ausdrücke:

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

Der erste gibt ein Map und der zweite ein Iterable zurück. Die Magie der Rückgabe einer passenden Sammlung ist die Arbeit von CanBuildFrom. Betrachten wir die Definition von map noch einmal, um sie zu verstehen.

Die Methode map wird von TraversableLike geerbt. Es wird auf B und That parametrisiert und verwendet die Typparameter A und Repr, die die Klasse parametrisieren. 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, woher A und Repr kommen, betrachten wir die Definition von Map selbst:

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

Da TraversableLike von allen Merkmalen geerbt wird, die Map erweitern, können A und Repr von jedem von ihnen geerbt werden. Der Letzte bekommt allerdings die Vorliebe. Nach der Definition des unveränderlichen Map und aller Merkmale, die es mit TraversableLike verbinden, 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

Übergeben Sie die Typparameter von Map[Int, String] In der gesamten Kette, stellen wir fest, dass die an TraversableLike übergebenen und daher von map verwendeten Typen wie folgt lauten :

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 verwende die doppelte Klammer, um zu betonen, dass ein Tupel empfangen wird, da dies die Art von A ist, wie wir gesehen haben.

Betrachten wir anhand dieser Informationen die anderen Typen.

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

map (_._2):
B = String

Wir können sehen, dass der vom ersten map zurückgegebene Typ Map[Int,Int] Und der zweite Iterable[String] Ist. Anhand der Definition von map ist leicht zu erkennen, 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, dessen Klasse um Map erweitert ist:

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

Diese Definitionen stellen Fabriken für parametrisierte CanBuildFrom bereit.

Scala wählt das spezifischste verfügbare Implizit aus. Im ersten Fall war es das erste CanBuildFrom. Im zweiten Fall wurde der zweite CanBuildFrom gewählt, da der erste nicht übereinstimmte.

Zurück zur Frage

Schauen wir uns den Code für die Frage an, die Definition von List und map (noch einmal), 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]. Die Typen A und Repr, die für TraversableLike definiert wurden, sind also:

A = String
Repr = List[String]

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

B = (Int, String)

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

val map : Map[Int,String] =

So,

That = Map[Int, String]

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

323

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

Entnommen aus Betreff: Unterstützung für explizite Builder (2009-10-23):

Es gibt dem Compiler einen Vorschlag, welchen Builder er implizit auswählen soll (im Grunde erlaubt es dem Compiler zu wählen, welche Factory seiner Meinung nach am besten zur Situation passt.)

Beispiel:

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 sehen, dass der Rückgabetyp implizit vom Compiler so ausgewählt wird, dass er dem erwarteten Typ am besten entspricht. Je nachdem, wie Sie die Empfangsvariable 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)
86
Austen Holmes

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 erläutern, warum es breakOut heißt:

Warum heißt es breakOut?

Weil wir wollen von einem Typ in einen anderen ausbrechen:

Aus welchem ​​Typ in welchen Typ ausbrechen? Schauen wir uns die map -Funktion für Seq als Beispiel an:

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

Wenn Sie eine Map direkt aus dem Mapping über die Elemente einer Sequenz erstellen möchten, z. B .:

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 gibt eine implizite Builder-Factory CanBuildFrom[Seq[_], B, Seq[B]], Aber es gibt [~ # ~] keine [~ # ~ ] Builder Factory von Seq nach Map).

Zum Kompilieren müssen wir irgendwie breakOut der Typanforderung und fähig sein Erstellen eines Builders, der eine Map für die zu verwendende Funktion map 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()
    }

Nothing ist eine Unterklasse aller Klassen, sodass jede Builder-Factory anstelle von implicit b: CanBuildFrom[Nothing, T, To] eingesetzt werden kann. 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 wird kompiliert, weil breakOut den erforderlichen Typ von CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]] bereitstellen kann, während der Compiler eine implizite Builder-Factory des Typs CanBuildFrom[Map[_, _], (A, B), Map[A, B]] finden kann von CanBuildFrom[Nothing, T, To], damit breakOut den eigentlichen Builder erstellt.

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

Hoffe das klärt die Dinge auf.

7
Dzhu

Ein einfaches Beispiel, um 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]
4
man