Scala 2.8 breakOut

225

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 me breakOutllama como argumento para mi List?

oxbow_lakes
fuente
13
La respuesta trivial es, no es un argumento para List, sino para map.
Daniel C. Sobral

Respuestas:

325

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 su función y la segunda es implícita. Si no proporciona esa información implícita, Scala elegirá la más específica disponible.

Acerca de breakOut

Entonces, ¿para qué sirve breakOut? Considere el ejemplo dado para la pregunta: toma una lista de cadenas, transforma cada cadena en una tupla (Int, String)y luego produce una Map. La forma más obvia de hacerlo sería producir una List[(Int, String)]colección intermedia y luego convertirla.

Dado que maputiliza a Builderpara producir la colección resultante, ¿no sería posible omitir el intermediario Listy recopilar los resultados directamente en a Map? Evidentemente, sí, lo es. Para ello, sin embargo, tenemos que pasar una correcta CanBuildFroma map, y eso es exactamente lo que breakOuthace.

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 breakOutestá parametrizado y que devuelve una instancia de CanBuildFrom. Como sucede, los tipos From, Ty Toya se han inferido, porque sabemos que mapestá 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 breakOutsí mismo. Es de tipo CanBuildFrom[Nothing,T,To]. Ya conocemos todos estos tipos, por lo que podemos determinar que necesitamos un tipo implícito CanBuildFrom[Nothing,(Int,String),Map[Int,String]]. ¿Pero hay tal definición?

Veamos la CanBuildFromdefinición de:

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

Entonces, CanBuildFromes contra-variante en su primer parámetro de tipo. Debido a que Nothinges una clase inferior (es decir, es una subclase de todo), eso significa que cualquier clase se puede usar en lugar de Nothing.

Dado que existe un generador de este tipo, Scala puede usarlo para producir el resultado deseado.

Sobre constructores

Una gran cantidad de métodos de la biblioteca de colecciones de Scala consiste en tomar la colección original, procesarla de alguna manera (en el caso de maptransformar 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 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 del constructor. Por lo tanto, un Listconstructor devolverá a List, un Mapconstructor devolverá a Map, y así sucesivamente. La implementación del mapmétodo no tiene que preocuparse por el tipo de resultado: el constructor se encarga de ello.

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

La magia de producir lo mejor posible Builderde los tipos conocidos de la expresión se realiza a través de este CanBuildFromimplícito.

Acerca de CanBuildFrom

Para explicar mejor lo que está sucediendo, daré un ejemplo donde la colección que se está mapeando es un en Maplugar de un List. Regresaré a Listmás tarde. Por ahora, considere estas dos expresiones:

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

El primero devuelve ay Mapel segundo devuelve un Iterable. La magia de devolver una colección adecuada es obra de CanBuildFrom. Consideremos mapnuevamente la definición de para entenderla.

El método mapse hereda de TraversableLike. Se parametriza en By That, y utiliza los parámetros de tipo Ay Repr, que parametrizan la clase. Veamos ambas definiciones juntas:

La clase TraversableLikese 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 Ay de dónde Reprviene, consideremos la definición de Mapsí mismo:

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

Porque TraversableLikees heredado por todos los rasgos que se extienden Map, Ay Reprpodría heredarse de cualquiera de ellos. Sin embargo, el último obtiene la preferencia. Entonces, siguiendo la definición de lo inmutable Mapy todos los rasgos que lo conectan 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]toda la cadena, encontramos que los tipos pasados TraversableLikey, 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 Alo 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 primero mapes Map[Int,Int], y el segundo es Iterable[String]. Mirando mapla definición de, 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 objeto Map:

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

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

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

Estas definiciones proporcionan fábricas para parametrizadas CanBuildFrom.

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

Volver a la pregunta

Vamos a ver el código de la pregunta, List'sy map' s definición (de nuevo) para ver cómo se infieren 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 Ay Reprdefinidos en TraversableLikeson:

A = String
Repr = List[String]

El tipo para (x => (x.length, x))es (String) => (Int, String), entonces el tipo de Bes:

B = (Int, String)

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

val map : Map[Int,String] =

Entonces,

That = Map[Int, String]

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

Daniel C. Sobral
fuente
61
Daniel, puedo repasar los tipos en tu respuesta, pero una vez que llego al final, siento que no he obtenido un alto nivel de comprensión. ¿Qué es breakOut? ¿De dónde viene el nombre "breakOut" (de qué estoy saliendo)? ¿Por qué es necesario en este caso para obtener un Mapa? ¿Seguramente hay alguna manera de responder brevemente estas preguntas? (incluso si el largo tipo de escritura sigue siendo necesario para comprender cada detalle)
Seth Tisue
3
@Seth Esa es una preocupación válida, pero no estoy seguro de estar a la altura. El origen de esto se puede encontrar aquí: article.gmane.org/gmane.comp.lang.scala.internals/1812/… . Lo pensaré, pero, en este momento, no puedo pensar en una forma de mejorarlo.
Daniel C. Sobral
2
¿Hay alguna manera de evitar especificar el tipo de resultado completo de Map [Int, String] y en su lugar poder escribir algo como: 'val map = List ("London", "Paris"). Map (x => (x. length, x)) (breakOut [... Map]) '
IttayD
99
@SethTisue De mi lectura de esta explicación, parece que breakOut es necesario para "romper" el requisito que su constructor necesita construir a partir de una Lista [String]. El compilador quiere un CanBuildFrom [List [String], (Int, String), Map [Int, String]], que no puede proporcionar. La función breakOut hace esto al golpear el primer parámetro de tipo en CanBuildFrom al establecerlo en Nothing. Ahora solo tiene que proporcionar un CanBuildFrom [Nothing, (Int, String), Map [Int, String]]. Esto es fácil porque lo proporciona la clase Map.
Mark
2
@ Mark Cuando encontré breakOut, el problema que vi abordar era la forma en que las mónadas insisten en mapear (a través de bind / flatMap) a su propio tipo. Le permite a uno "romper" una cadena de mapeo usando una mónada en un tipo de mónada diferente. Sin embargo, no tengo idea de si eso es lo que Adriaan Moors (el autor) estaba pensando al respecto.
Ed Staub
86

Me gustaría construir sobre la respuesta de Daniel. Fue muy exhaustivo, pero como se señaló en los comentarios, no explica qué hace la ruptura.

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

Le da al compilador una sugerencia sobre qué constructor elegir implícitamente (esencialmente le permite al compilador elegir qué fábrica cree que se ajusta 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 tipo de retorno es elegido implícitamente por el compilador para que coincida mejor con el tipo esperado. Dependiendo de cómo declare la variable receptora, obtendrá resultados diferentes.

Lo siguiente sería una forma equivalente de especificar un constructor. Tenga en cuenta que en este caso, el compilador inferirá 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)
Austen Holmes
fuente
1
Me pregunto por qué se llama " breakOut"? Estoy pensando que algo como converto buildADifferentTypeOfCollection(pero más corto) podría haber sido más fácil de recordar.
KajMagnus
8

La respuesta de Daniel Sobral es excelente, y debe leerse junto con Architecture of Scala Collections (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 pasar a otro :

¿Salir de qué tipo en qué tipo? Veamos la mapfunción Seqcomo 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 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 CanBuildFrom[Seq[_], B, Seq[B]]fábrica de constructores implícita disponible, pero NO hay una fábrica de constructores desde Seq hasta Map).

Para compilar, necesitamos de alguna manera breakOutel requisito de tipo , y poder construir un generador que produzca un Mapa para que la mapfunción lo use.

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

Nothinges 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 breakOutes capaz de proporcionar el tipo requerido de CanBuildFrom[Seq[(String, Int)], (String, Int), Map[String, Int]], mientras que el compilador puede encontrar una fábrica de tipo de generador implícito CanBuildFrom[Map[_, _], (A, B), Map[A, B]], en lugar de CanBuildFrom[Nothing, T, To], para que breakOut lo use para crear el generador real.

Tenga en cuenta que CanBuildFrom[Map[_, _], (A, B), Map[A, B]]se define en el Mapa, y simplemente inicia un MapBuilderque utiliza un Mapa subyacente.

Espero que esto aclare las cosas.

Dzhu
fuente
4

Un ejemplo simple para entender lo que breakOuthace:

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
fuente
Gracias por el ejemplo! Tampoco val seq:Seq[Int] = set.map(_ % 2).toVectorle dará los valores repetidos ya que Setse conservaron para map.
Matthew Pickering
@MatthewPickering correcto! set.map(_ % 2)crea un Set(1, 0)primero, que luego se convierte en a Vector(1, 0).
fdietze