Scala 2.8 breakOut

scala-2.8 scala-collections

Question

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 resulta en:

> 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 a breakOut como un argumento a mi List ?

Answer 1

La respuesta de Daniel Sobral es excelente y debe leerse junto con la Arquitectura de las Colecciones Scala (Capítulo 25 de Programación en Scala).

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

¿Por qué se llama breakOut ?

Porque queremos salir de un tipo y entrar en otro :

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

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

Si quisiéramos construir un mapa directamente a partir de un mapa sobre los elementos de una secuencia como:

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

El compilador 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 disponible, pero NO hay una fábrica de constructores desde Seq hasta Map).

Para compilar, necesitamos breakOut de alguna breakOut del requisito de tipo , y poder construir un generador que produzca un Mapa para que lo use la función de map .

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 constructores puede sustituirse en lugar de implicit b: CanBuildFrom[Nothing, T, To] . Si usamos 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 compilaría, porque breakOut puede proporcionar el tipo requerido de CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]] , mientras que el compilador es capaz de encontrar una fábrica de constructores implícita del tipo CanBuildFrom[Map[_, _], (A, B), Map[A, B]] , en lugar de CanBuildFrom[Nothing, T, To] , para que breakOut lo use para crear el constructor real.

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

Espero que esto aclare las cosas.

Answer 2

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. La primera es tu función y la segunda es una implícita. Si no proporciona eso 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. Toma una lista de cadenas, transforma cada cadena en una tupla (Int, String) y luego genera un Map partir de ella. La forma más obvia de hacerlo sería producir una recopilación de la List[(Int, String)] intermedia List[(Int, String)] y luego convertirla.

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

Veamos, entonces, 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 . A medida que sucede, los tipos From , T y To ya se han deducido, porque sabemos que el map espera 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 de tipo CanBuildFrom[Nothing,T,To] . Ya conocemos todos estos tipos, por lo que podemos determinar que necesitamos un tipo implícito de tipo CanBuildFrom[Nothing,(Int,String),Map[Int,String]] . Pero ¿existe tal definición?

Veamos la definición de CanBuildFrom :

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

Entonces, CanBuildFrom es contra-variante en su primer parámetro de tipo. Debido a que 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 la salida deseada.

Sobre los constructores

Muchos de los 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 del código, este almacenamiento de resultados se realiza a través de un constructor ( 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 del constructor. Por lo tanto, un constructor de listas devolverá una List , un constructor de Map devolverá un Map , y así sucesivamente. La implementación del método de map no tiene por qué preocuparse por el tipo de resultado: el constructor se encarga de ello.

Por otro lado, eso significa que el map debe 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 escribiera Map(''a'' -> 1).map(_.swap) , me gustaría recuperar 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 . Volveré a la 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 apropiada es el trabajo de CanBuildFrom . Consideremos de nuevo la definición de map para entenderlo.

El map método 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 comprender de dónde provienen 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 se extienden a Map , A y Repr podrían ser heredados de cualquiera de ellos. Sin embargo, el último obtiene la preferencia. Entonces, siguiendo la definición del Map inmutable y todos los rasgos que lo conectan con 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 map , son:

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

Volviendo al ejemplo, el primer mapa recibe una función de tipo ((Int, String)) => (Int, Int) y el segundo mapa recibe una función de tipo ((Int, String)) => String . Utilizo el paréntesis doble para enfatizar que se está recibiendo una tupla, ya que ese es el tipo de A que 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 algunas declaraciones implícitas que los proporcionan. En el Map objetos:

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á el implícito más específico disponible. 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 para la pregunta, la List y la definición del 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 del resultado del map , y ya tenemos eso 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]] .

Answer 3

Me gustaría construir sobre la respuesta de Daniel. Fue muy minucioso, pero como se señala en los comentarios, no explica lo que hace la ruptura.

Tomado de article.gmane.org/gmane.comp.lang.scala.internals/1812/… (2009-10-23), esto es lo que creo que hace el desglose:

Le da al compilador una sugerencia sobre qué Generador elegir implícitamente (esencialmente le permite al compilador elegir qué fábrica cree que se adapta mejor a la situación).

Por ejemplo, vea 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 compilador elige implícitamente el tipo de retorno para que coincida mejor con el tipo esperado. Dependiendo de cómo declare la variable receptora, obtendrá diferentes resultados.

La siguiente sería una forma equivalente de especificar un constructor. Tenga en cuenta que, en este caso, el compilador deducirá el tipo esperado en función del tipo del 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)

Answer 4

Un ejemplo simple 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]