Scala 2.8 breakOut

225

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

Qu'est-ce qui se passe ici? Pourquoi est breakOut-il appelé comme argument pour mon List?

oxbow_lakes
la source
13
La réponse triviale étant, ce n'est pas un argument pour List, mais pour map.
Daniel C.Sobral

Réponses:

325

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 implicitement, Scala choisira celui le plus spécifique disponible.

À 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 produisez-en une Map. La façon la plus évidente de le faire serait de produire une List[(Int, String)]collection intermédiaire , puis de la convertir.

Étant donné que maputilise un Builderpour produire la collection résultante, ne serait-il pas possible de sauter l'intermédiaire Listet de collecter les résultats directement dans un Map? Évidemment, oui. Pour ce faire, cependant, nous devons passer un bon CanBuildFromà map, et c'est exactement ce qui breakOutfait.

Examinons donc 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 qu'il breakOutest paramétré et qu'il renvoie une instance de CanBuildFrom. En l'occurrence, les types From, Tet Toont déjà été déduits, parce que nous savons que cela mapattend CanBuildFrom[List[String], (Int, String), Map[Int, String]]. Par conséquent:

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

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

Regardons la CanBuildFromdéfinition de:

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

Il en CanBuildFromest de même de la contre-variante sur son premier paramètre de type. Parce que Nothingc'est une classe inférieure (c'est-à-dire, c'est une sous-classe de tout), cela signifie que n'importe quelle classe peut être utilisée à la place de Nothing.

Puisqu'un tel générateur existe, Scala peut l'utiliser pour produire la sortie souhaitée.

À propos des constructeurs

De nombreuses méthodes de la bibliothèque de collections de Scala consistent à prendre la collection d'origine, à la traiter d'une manière ou d'une autre (dans le cas de map, transformer chaque élément) et à stocker les résultats dans une nouvelle collection.

Pour maximiser la réutilisation du code, ce stockage des résultats se fait via un générateur ( scala.collection.mutable.Builder), qui prend essentiellement en charge deux opérations: l'ajout d'éléments et le retour de la collection résultante. Le type de cette collection résultante dépendra du type du générateur. Ainsi, un Listgénérateur renverra un List, un Mapgénérateur renverra un Map, et ainsi de suite. La mise en œuvre de la mapméthode n'a pas à se préoccuper du type de résultat: le constructeur s'en charge.

D'un autre côté, cela signifie qu'il mapfaut en quelque sorte recevoir ce constructeur. Le problème rencontré lors de la conception des collections Scala 2.8 était de savoir comment choisir le meilleur constructeur possible. Par exemple, si je devais écrire Map('a' -> 1).map(_.swap), j'aimerais récupérer Map(1 -> 'a'). En revanche, un Map('a' -> 1).map(_._1)ne peut pas retourner un Map(il renvoie un Iterable).

La magie de produire le meilleur possible à Builderpartir des types d'expression connus s'exerce à travers cet CanBuildFromimplicite.

À propos CanBuildFrom

Pour mieux expliquer ce qui se passe, je vais donner un exemple où la collection en cours de mappage est un Mapau lieu d'un List. J'y reviendrai plus Listtard. Pour l'instant, considérons ces deux expressions:

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

Le premier retourne un Mapet le second retourne un Iterable. La magie du retour d'une collection appropriée est l'œuvre de CanBuildFrom. Examinons mapà nouveau la définition de pour la comprendre.

La méthode mapest héritée de TraversableLike. Il est paramétré sur Bet That, et utilise les paramètres de type Aet Repr, qui paramètrent la classe. Voyons ensemble les deux définitions:

La classe TraversableLikeest 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 d'où Aet d' où nous Reprvenons, considérons la définition de Maplui-même:

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

Parce que TraversableLikeest héritée par tous les traits qui se prolongent Map, Aet Reprpourrait être hérité de l' un d'eux. Le dernier a cependant la préférence. Donc, suivant la définition de l'immuable Mapet de 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 Map[Int, String]tout au long de la chaîne, nous constatons que les types passés à TraversableLike, et donc utilisés par map, sont:

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 qu'il s'agit d'un tuple reçu, car c'est le type de celui Aque nous avons vu.

Avec ces informations, considérons les autres types.

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

map (_._2):
B = String

Nous pouvons voir que le type retourné par le premier mapest Map[Int,Int], et le second est Iterable[String]. En regardant mapla définition de, 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 quelques déclarations implicites les fournissant. Sur l'objet Map:

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

Et sur objet Iterable, dont la classe est étendue par Map:

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

Ces définitions fournissent des usines pour paramétré CanBuildFrom.

Scala choisira l'implicite disponible le plus spécifique. Dans le premier cas, c'était le premier CanBuildFrom. Dans le second cas, le premier ne correspondant pas, il a choisi le second CanBuildFrom.

Retour à la question

Voyons le code de la définition de la question Listet mapde (encore) pour voir comment les types sont inférés:

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], donc les types Aet Reprdéfinis sur TraversableLikesont:

A = String
Repr = List[String]

Le type de (x => (x.length, x))est (String) => (Int, String)donc le type de Best:

B = (Int, String)

Le dernier type inconnu Thatest le type du résultat de map, et nous l'avons déjà aussi:

val map : Map[Int,String] =

Alors,

That = Map[Int, String]

Cela signifie qu'il breakOutdoit nécessairement renvoyer un type ou un sous-type de CanBuildFrom[List[String], (Int, String), Map[Int, String]].

Daniel C. Sobral
la source
61
Daniel, je peux parcourir les types dans votre réponse, mais une fois que j'arrive à la fin, je sens que je n'ai pas acquis une compréhension de haut niveau. Qu'est - ce que breakOut? D'où vient le nom "breakOut" (de quoi suis-je en train de sortir)? Pourquoi est-il nécessaire dans ce cas pour sortir une carte? Y a-t-il sûrement un moyen de répondre brièvement à ces questions? (même si la longue fouille de caractères reste nécessaire pour saisir chaque détail)
Seth Tisue
3
@Seth C'est une préoccupation valable, mais je ne suis pas sûr d'être à la hauteur. L'origine de ceci peut être trouvée ici: article.gmane.org/gmane.comp.lang.scala.internals/1812/… . J'y penserai, mais, pour le moment, je ne vois pas grand-chose pour l'améliorer.
Daniel C.Sobral
2
Existe-t-il un moyen d'éviter de spécifier le type de résultat entier de Map [Int, String] et de pouvoir écrire quelque chose comme: 'val map = List ("London", "Paris"). Map (x => (x. longueur, x)) (breakOut [... Carte]) '
IttayD
9
@SethTisue D'après ma lecture de cette explication, il semble que breakOut soit nécessaire pour "sortir" de l'exigence que votre générateur doit construire à partir d'une List [String]. Le compilateur veut un CanBuildFrom [List [String], (Int, String), Map [Int, String]], que vous ne pouvez pas fournir. La fonction breakOut le fait en encombrant le premier paramètre de type dans CanBuildFrom en le définissant sur Nothing. Il ne vous reste plus qu'à fournir un CanBuildFrom [Nothing, (Int, String), Map [Int, String]]. C'est facile car il est fourni par la classe Map.
Mark
2
@Mark Quand j'ai trouvé breakOut, le problème que je l'ai vu résoudre était la façon dont les monades insistent pour mapper (via bind / flatMap) à leur propre type. Il permet de «sortir» d'une chaîne de mappage en utilisant une monade dans un type de monade différent. Je ne sais pas du tout si c'est ce que pensait Adriaan Moors (l'auteur)!
Ed Staub
86

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

Tiré de Re: Support for explicit Builders (2009-10-23), voici ce que je pense que la répartition fait:

Il donne au compilateur une suggestion quant au constructeur à choisir implicitement (il permet essentiellement au compilateur de choisir quelle usine, selon lui, convient le mieux à la situation.)

Par exemple, consultez les informations suivantes:

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 que le type de retour est implicitement choisi 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 dans ce cas, le compilateur déduira le type attendu en fonction du type du générateur:

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
la source
1
Je me demande pourquoi il s'appelle " breakOut"? Je pense que quelque chose comme convertou buildADifferentTypeOfCollection(mais plus court) aurait été plus facile à retenir.
KajMagnus
8

La réponse de Daniel Sobral est excellente et doit être lue conjointement avec Architecture of Scala Collections (Chapitre 25 de Programmation en Scala).

Je voulais juste expliquer pourquoi on l'appelle breakOut:

Pourquoi est-il appelé breakOut?

Parce que nous voulons sortir d'un type et en un autre :

Sortez de quel type en quel type? Regardons la mapfonction Seqcomme un exemple:

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

Si nous voulions construire une carte directement à partir du mappage sur les éléments d'une séquence tels que:

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

Le compilateur se plaindrait:

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

La raison étant que Seq ne sait que construire une autre Seq (c'est-à-dire qu'il existe une CanBuildFrom[Seq[_], B, Seq[B]]fabrique de constructeur implicite disponible, mais il n'y a PAS de fabrique de constructeur de Seq à Map).

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

Comme Daniel l'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()
    }

Nothingest une sous-classe de toutes les classes, donc toute fabrique de constructeur peut être remplacée à 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 compilerait, car breakOutest capable de fournir le type requis de CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]], tandis que le compilateur est capable de trouver une fabrique de générateur implicite de type CanBuildFrom[Map[_, _], (A, B), Map[A, B]], à la place de CanBuildFrom[Nothing, T, To], pour breakOut à utiliser pour créer le générateur réel.

Notez que cela CanBuildFrom[Map[_, _], (A, B), Map[A, B]]est défini dans Map, et lance simplement un MapBuilderqui utilise une Map sous-jacente.

Espérons que cela arrange les choses.

Dzhu
la source
4

Un exemple simple pour comprendre ce que breakOutfait:

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
la source
Merci pour l'exemple! En outre , val seq:Seq[Int] = set.map(_ % 2).toVectorvous ne donnera pas les valeurs répétées comme Seta été conservé pour la map.
Matthew Pickering
@MatthewPickering correct! set.map(_ % 2)crée une Set(1, 0)première, qui est ensuite convertie en Vector(1, 0).
fdietze