Scala 2.8 breakOut

En Scala 2.8 , hay un objeto en 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() } 

Me han dicho que esto da como resultado:

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

¿Que esta pasando aqui? ¿Por qué se llama breakOut como argumento a mi List ?

La respuesta se encuentra en la definición de map :

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

Tenga en cuenta que tiene dos parámetros. El primero es tu función y el segundo es un implícito. Si no proporciona ese implícito, Scala elegirá el más específico disponible.

Acerca de breakOut

Entonces, ¿cuál es el propósito de breakOut ? Considere el ejemplo dado para la pregunta, usted toma una lista de cadenas, transforma cada cadena en una tupla (Int, String) , y luego produce un Map fuera de ella. La forma más obvia de hacerlo sería producir una colección intermedia List[(Int, String)] y luego convertirla.

Dado que el map usa un Builder para producir la colección resultante, ¿no sería posible omitir la List intermedia y recoger los resultados directamente en un Map ? Evidentemente, sí, lo es. Para hacerlo, sin embargo, tenemos que pasar un CanBuildFrom apropiado al map , y eso es exactamente lo que hace breakOut .

Veamos, entonces, en la definición 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() } 

Tenga en cuenta que breakOut está parametrizado y que devuelve una instancia de CanBuildFrom . From casualidad que los tipos From , T y To ya se han inferido, porque sabemos que el map está esperando CanBuildFrom[List[String], (Int, String), Map[Int, String]] . Por lo tanto:

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

Para concluir, examinemos lo implícito recibido por breakOut . Es del tipo CanBuildFrom[Nothing,T,To] . Ya conocemos todos estos tipos, por lo que podemos determinar que necesitamos un tipo implícito de CanBuildFrom[Nothing,(Int,String),Map[Int,String]] . ¿Pero hay tal definición?

Veamos la definición de CanBuildFrom :

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

Entonces CanBuildFrom es CanBuildFrom en su primer parámetro de tipo. Como Nothing es una clase inferior (es decir, es una subclase de todo), eso significa que cualquier clase puede usarse en lugar de Nothing .

Dado que existe tal constructor, Scala puede usarlo para producir el resultado deseado.

Acerca de los constructores

Muchos métodos de la biblioteca de colecciones de Scala consisten en tomar la colección original, procesarla de alguna manera (en el caso del map , transformar cada elemento) y almacenar los resultados en una nueva colección.

Para maximizar la reutilización de código, este almacenamiento de resultados se realiza a través de un generador ( scala.collection.mutable.Builder ), que básicamente admite dos operaciones: agregar elementos y devolver la colección resultante. El tipo de esta colección resultante dependerá del tipo de constructor. Por lo tanto, un generador de listas devolverá una List , un constructor de Map devolverá un Map , y así sucesivamente. La implementación del método del map no necesita preocuparse por el tipo de resultado: el constructor se ocupa de él.

Por otro lado, eso significa que el map necesita recibir este constructor de alguna manera. El problema al diseñar Scala 2.8 Collections fue cómo elegir el mejor constructor posible. Por ejemplo, si tuviera que escribir Map('a' -> 1).map(_.swap) , me gustaría obtener un Map(1 -> 'a') . Por otro lado, un Map('a' -> 1).map(_._1) no puede devolver un Map (devuelve un Iterable ).

La magia de producir el mejor Builder posible a partir de los tipos conocidos de la expresión se realiza a través de este CanBuildFrom implícito.

Acerca de CanBuildFrom

Para explicar mejor lo que está pasando, daré un ejemplo donde la colección que se está mapeando es un Map lugar de una List . Regresaré a List más tarde. Por ahora, considera estas dos expresiones:

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

El primero devuelve un Map y el segundo devuelve un Iterable . La magia de devolver una colección adecuada es obra de CanBuildFrom . Consideremos nuevamente la definición de map para entenderlo.

El map métodos se hereda de TraversableLike . Está parametrizado en B y That , y utiliza los parámetros de tipo A y Repr , que parametrizan la clase. Veamos ambas definiciones juntas:

La clase TraversableLike se define como:

 trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with AnyRef def map[B, That](f : (A) => B)(implicit bf : CanBuildFrom[Repr, B, That]) : That 

Para entender de dónde vienen A y Repr , consideremos la definición de Map sí:

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

Debido a que TraversableLike es heredado por todos los rasgos que extienden Map , A y Repr podrían heredarse de cualquiera de ellos. El último tiene la preferencia, sin embargo. Entonces, siguiendo la definición del Map inmutable y todos los rasgos que lo conectan a TraversableLike , tenemos:

 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 pasa los parámetros de tipo de Map[Int, String] lo largo de toda la cadena, encontramos que los tipos pasados ​​a TraversableLike , y, por lo tanto, utilizados por el map , son:

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

Volviendo al ejemplo, el primer mapa está recibiendo una función de tipo ((Int, String)) => (Int, Int) y el segundo mapa está recibiendo una función de tipo ((Int, String)) => String . Utilizo el doble paréntesis para enfatizar que se está recibiendo una tupla, ya que ese es el tipo de A como vimos.

Con esa información, consideremos los otros tipos.

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

Podemos ver que el tipo devuelto por el primer map es Map[Int,Int] , y el segundo es Iterable[String] . Mirando la definición del map , es fácil ver que estos son los valores de That . ¿Pero de dónde vienen?

Si miramos dentro de los objetos complementarios de las clases involucradas, vemos que algunas declaraciones implícitas las proporcionan. En el Map objeto:

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

Y en el objeto Iterable , cuya clase se extiende por Map :

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

Estas definiciones proporcionan fábricas para CanBuildFrom parametrizado.

Scala elegirá la disponible implícita más específica. En el primer caso, fue el primer CanBuildFrom . En el segundo caso, como el primero no coincidía, eligió el segundo CanBuildFrom .

Volver a la pregunta

Veamos el código de la pregunta, la definición de la List y el map (nuevamente) para ver cómo se deducen los tipos:

 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 

El tipo de List("London", "Paris") es List[String] , por lo que los tipos A y Repr definidos en TraversableLike son:

 A = String Repr = List[String] 

El tipo para (x => (x.length, x)) es (String) => (Int, String) , por lo que el tipo de B es:

 B = (Int, String) 

El último tipo desconocido, That es el tipo de resultado del map , y ya lo tenemos también:

 val map : Map[Int,String] = 

Asi que,

 That = Map[Int, String] 

Eso significa que breakOut debe, necesariamente, devolver un tipo o subtipo de CanBuildFrom[List[String], (Int, String), Map[Int, String]] .

Me gustaría construir sobre la respuesta de Daniel. Fue muy minucioso, pero como se señaló en los comentarios, no explica qué es lo que ocurre.

Tomado de Re: Apoyo para Constructores explícitos (2009-10-23), esto es lo que creo que la ruptura hace:

Le da al comstackdor una sugerencia sobre qué generador elegir de forma implícita (esencialmente le permite al comstackdor elegir qué fábrica cree que se ajusta mejor a la situación).

Por ejemplo, mira lo siguiente:

 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) 

Puede ver que el tipo de devolución es elegido implícitamente por el comstackdor para que coincida mejor con el tipo esperado. Dependiendo de cómo declare la variable de recepción, obtendrá diferentes resultados.

La siguiente sería una forma equivalente de especificar un constructor. Tenga en cuenta que, en este caso, el comstackdor deducirá el tipo esperado según el tipo de constructor:

 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) 

La respuesta de Daniel Sobral es excelente, y debe leerse junto con Architecture of Scala Collections (Capítulo 25 de Progtwigción en Scala).

Solo quería explicar por qué se llama breakOut :

¿Por qué se llama breakOut ?

Porque queremos romper de un tipo a otro :

¿Salir de qué tipo en qué tipo? Veamos la función de map en Seq como un ejemplo:

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

Si quisiéramos construir un Mapa directamente desde el mapeo sobre los elementos de una secuencia como:

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

El comstackdor se quejaría:

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

La razón es que Seq solo sabe cómo construir otra Seq (es decir, hay una fábrica de constructores CanBuildFrom[Seq[_], B, Seq[B]] implícita, pero NO hay una fábrica de constructores desde Seq a Map).

Para comstackr, necesitamos breakOut de alguna breakOut el requisito de tipo , y ser capaces de construir un constructor que produzca un mapa para la función de map a usar.

Como Daniel ha explicado, breakOut tiene la siguiente firma:

 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 es una subclase de todas las clases, por lo que cualquier fábrica de generador puede sustituirse en lugar de implicit b: CanBuildFrom[Nothing, T, To] . Si utilizamos la función breakOut para proporcionar el parámetro implícito:

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

Se comstackría, porque breakOut puede proporcionar el tipo requerido de CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]] , mientras que el comstackdor puede encontrar una fábrica de constructores implícita. de tipo CanBuildFrom[Map[_, _], (A, B), Map[A, B]] , en lugar de CanBuildFrom[Nothing, T, To] , para que BreakOut use para crear el constructor real.

Tenga en cuenta que CanBuildFrom[Map[_, _], (A, B), Map[A, B]] está definido en Mapa, y simplemente inicia un MapBuilder que utiliza un Mapa subyacente.

Espero que esto aclare las cosas.

Un simple ejemplo para entender lo que hace breakOut :

 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]