Scala 2.8 Breakout

Question

Scala 2.8, il y a un objet dans 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() 
} 

On m'a dit que cela se traduit par:

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

ce qui se passe ici? Pourquoi breakOut est-il appelé comme argument à List?

Answer 1

La réponse se trouve sur la définition de map:

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

Notez qu'il a deux paramètres. Le premier est votre fonction et le second est implicite. Si vous ne fournissez pas cela implicite, Scala choisira le le plus spécifique disponible.

A propos breakOut

Alors, quel est le but de breakOut? Considérez l'exemple donné pour la question, vous prenez une liste de chaînes, transformez chaque chaîne en un tuple (Int, String), puis en produire un Map. La façon la plus évidente de le faire produirait une collection intermédiaire List[(Int, String)], puis de le convertir.

Étant donné que map utilise un Builder pour produire la collection résultante, ne serait-il possible de sauter l'intermédiaire List et recueillir les résultats directement dans un Map? Évidemment, oui, ça l'est. Pour ce faire, cependant, nous devons passer un vrai CanBuildFrom à map, et c'est exactement ce que fait breakOut.

Let look, puis, à la définition de 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() 
    } 

Notez que breakOut est paramétrées, et qu'il renvoie une instance de CanBuildFrom. En l'occurrence, les types From, T et To ont déjà été déduits, car nous savons que map attend CanBuildFrom[List[String], (Int, String), Map[Int, String]]. Par conséquent:

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

Pour conclure, nous allons examiner l'implicite reçue par breakOut lui-même. Il est de type CanBuildFrom[Nothing,T,To]. Nous connaissons déjà tous ces types, donc nous pouvons déterminer que nous avons besoin d'un implicite de type CanBuildFrom[Nothing,(Int,String),Map[Int,String]]. Mais y a-t-il une telle définition?

Regardons à la définition de CanBuildFrom:

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

donc CanBuildFrom est contre-variante de son premier paramètre de type. Parce que Nothing est une classe de fond (c'est-à-dire qu'il s'agit d'une sous-classe de tout), cela signifie une classe peut être utilisée à la place de Nothing.

Étant donné qu'un tel constructeur existe, Scala peut l'utiliser pour produire la sortie désirée.

A propos constructeurs

Beaucoup de méthodes de la bibliothèque de collections de Scala consiste à prendre la collection originale, le traitement de quelque sorte (dans le cas de map, transformant chaque élément), et stocker les résultats dans une nouvelle collection .

Afin d'optimiser la réutilisation du code, cette mémorisation des résultats se fait à travers un adjuvant (scala.collection.mutable.Builder), qui supporte essentiellement deux opérations: les éléments annexées, et en retournant la collection résultante. Le type de cette collection résultante dépendra du type du constructeur. Ainsi, un générateur List renverra un List, un générateur Map renverra un Map, et ainsi de suite. L'implémentation de la méthode map ne doit pas se préoccuper du type de résultat: le constructeur s'en charge. D'autre part, cela signifie que map doit recevoir ce constructeur d'une manière ou d'une autre. Le problème rencontré lors de la conception de Scala 2.8 Collections était de savoir comment choisir le meilleur constructeur possible. Par exemple, si je devais écrire Map('a' -> 1).map(_.swap), j'aimerais obtenir un Map(1 -> 'a') de retour. D'un autre côté, un Map('a' -> 1).map(_._1) ne peut pas renvoyer un Map (il renvoie un Iterable).

La magie de la production du meilleur Builder possible à partir des types connus de l'expression est réalisée à travers ce CanBuildFrom implicite.

A propos CanBuildFrom

Pour mieux expliquer ce qui se passe, je vais vous donner un exemple où la collection est un cartographié Map au lieu d'un List. Je vais revenir à List plus tard. Pour l'instant, considérer ces deux expressions:

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

Les premiers retours d'un Map et le second renvoie un Iterable. La magie du retour d'une collection d'essayage est l'œuvre de CanBuildFrom. Considérons à nouveau la définition de map pour le comprendre. La méthode map est héritée de TraversableLike. Il est paramétré sur B et That, et utilise les paramètres de type A et Repr, qui paramétrent la classe. Voyons voir les deux définitions ensemble:

La classe TraversableLike est définie comme:

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

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

Pour comprendre où A et Repr viennent, nous allons examiner la définition de Map lui-même:

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

Parce que TraversableLike est hérité par tous les traits qui s'étendent Map, A et Repr pourrait être hérité de l'un d'eux. Le dernier a la préférence, cependant.Ainsi, après la définition de l'immuable Map et tous les traits qui le relient à TraversableLike, nous avons:

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 

Si vous passez les paramètres de type de Map[Int, String] tout le long de la chaîne, nous constatons que les types passés à TraversableLike, et, par conséquent, utilisé par map, sont les suivants:

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

pour revenir à l'exemple, la première carte reçoit une fonction de type ((Int, String)) => (Int, Int) et la seconde carte reçoit une fonction de type ((Int, String)) => String. J'utilise la double parenthèse pour souligner que c'est un tuple reçu, car c'est le type de A comme nous l'avons vu.

Avec cette information, considérons les autres types.

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

map (_._2): 
B = String 

Nous pouvons voir que le type retourné par la première map est Map[Int,Int], et le second est Iterable[String]. En regardant la définition de map, il est facile de voir que ce sont les valeurs de That. Mais d'où viennent-ils?

Si nous regardons à l'intérieur des objets compagnons des classes impliquées, nous voyons des déclarations implicites les fournissant. Sur objet Map:

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

Et sur l'objet Iterable, dont la classe est prolongée par Map:

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

Ces définitions fournissent des usines pour paramétrés CanBuildFrom. Scala choisira l'implicite le plus spécifique disponible.

Dans le premier cas, c'était le premier CanBuildFrom. Dans le second cas, comme le premier ne correspond pas, il a choisi le second CanBuildFrom.

Retour à la question

Voyons voir le code de la question, List 's et map' définition de (nouveau) pour voir comment les types sont inférées:

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 

Le type de List("London", "Paris") est List[String], de sorte que les types A et Repr définis sur TraversableLike sont:

A = String 
Repr = List[String] 

Le type de (x => (x.length, x)) est (String) => (Int, String), de sorte que le type de B est:

B = (Int, String) 

Le dernier type inconnu, That est le type du résultat de map, et nous avons déjà ainsi:

val map : Map[Int,String] = 

Ainsi,

That = Map[Int, String] 

Cela signifie que breakOut doit nécessairement renvoyer un type ou un sous-type de CanBuildFrom[List[String], (Int, String), Map[Int, String]].

Answer 2

Je voudrais construire sur la réponse de Daniel. C'était très complet, mais comme indiqué dans les commentaires, cela n'explique pas ce que fait l'évasion.

Extrait de Re: Support for explicit Builders (2009-10-23), voici ce que je crois en petits groupes fait:

Il donne le compilateur une suggestion à laquelle Builder de choisir implicitement (essentiellement, il permet au compilateur de choisir . quelle usine il pense correspond à la situation mieux)

par exemple, voir ce qui suit:

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) 

Vous pouvez voir le type de retour est choisi implicitement par le compilateur pour correspondre au mieux au type attendu. Selon la façon dont vous déclarez la variable de réception, vous obtenez des résultats différents.

Ce qui suit serait une manière équivalente de spécifier un générateur. Notez que dans ce cas, le compilateur déduire le type attendu en fonction du type du constructeur:

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

Un exemple simple pour comprendre ce que breakOut fait:

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

La réponse de Daniel Sobral est grande, et devrait être lire ensemble avec Architecture of Scala Collections (Chapitre 25 de la programmation en Scala).

Je voulais juste expliquer pourquoi il est appelé breakOut:

Pourquoi est-il appelé breakOut?

Parce que nous voulons pause hors d'un type et dans un autre:

Pause de quel type dans quel type? Permet de regarder la fonction map sur Seq comme exemple:

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

Si nous voulions construire une carte directement de la cartographie sur les éléments d'une séquence telle que:

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

Le compilateur se plaindraient:

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

La raison étant que Seq sait comment construire une autre Seq (autrement dit, il est un constructeur implicite CanBuildFrom[Seq[_], B, Seq[B]] usine disponible, mais il y a NO usine de constructeur de Seq à la carte).

Pour compiler, nous devons en quelque sorte breakOut de l'exigence de type, et être en mesure de construire un constructeur qui produit une carte pour la fonction map à utiliser.

Comme Daniel a expliqué, Breakout a la signature suivante:

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 est une sous-classe de toutes les classes, de sorte que toute usine de constructeur peut être substitué à la place de implicit b: CanBuildFrom[Nothing, T, To]. Si nous avons utilisé la fonction Breakout pour fournir le paramètre implicite:

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

Il rassemblerait, parce que breakOut est en mesure de fournir le type requis de CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]], alors que le compilateur est en mesure de trouver une usine de constructeur implicite de type CanBuildFrom[Map[_, _], (A, B), Map[A, B]], à la place de CanBuildFrom[Nothing, T, To], pour breakOut à utiliser pour créer le constructeur réel.

Notez que CanBuildFrom[Map[_, _], (A, B), Map[A, B]] est défini dans Map et initie simplement un MapBuilder qui utilise une carte sous-jacente.

Espérons que cela éclaircit les choses.