La deforestación en colecciones Scala

Question

Desde el diseño de colecciones de Scala entiendo que algo como:

scala> BitSet(1,2,3) map (_ + "a") 
res7: scala.collection.immutable.Set[String] = Set(1a, 2a, 3a) 

no construye una estructura de datos intermedia: El nuevo conjunto se construye como el BitSet se itera sobre el uso de un constructor. De hecho, en ese caso es obvio ya que un conjunto de bits de cadenas no tiene sentido.

¿Qué pasa con los mapas de las listas? Estoy bastante seguro de que el siguiente construye una lista intermedia:

scala> List(1,2,3) map (_ -> "foo") toMap 
res8: scala.collection.immutable.Map[Int,java.lang.String] = 
    Map(1 -> foo, 2 -> foo, 3 -> foo) 

saber, la lista List((1,foo), (2,foo), (3,foo)). Si no, ¿cómo? Ahora, ¿qué hay de lo siguiente?

scala> Map.empty ++ (List(1,2,3) map (_ -> "foo")) 
res10: scala.collection.immutable.Map[Int,java.lang.String] = 
    Map(1 -> foo, 2 -> foo, 3 -> foo) 

Esta vez, por lo que parece entender el tipo de ++:

def ++ [B >: (A, B), That] 
     (that: TraversableOnce[B]) 
     (implicit bf: CanBuildFrom[Map[A, B], B, That]): That 

I piensan que podría darse el caso de que el mapa se construye sobre la marcha, y que ningún lista intermedia está construida.

¿Es el caso? En caso afirmativo, ¿es esta la forma canónica de garantizar la deforestación o existe una sintaxis más directa?

Answer 1

Puede utilizar breakOut para asegurarse de que no se cree ninguna colección intermedia. Por ejemplo:

// creates intermediate list. 
scala> List((3, 4), (9, 11)).map(_.swap).toMap 
res542: scala.collection.immutable.Map[Int,Int] = Map(4 -> 3, 11 -> 9) 

scala> import collection.breakOut 
import collection.breakOut 

// doesn't create an intermediate list. 
scala> List((3, 4), (9, 11)).map(_.swap)(breakOut) : Map[Int, Int] 
res543: Map[Int,Int] = Map(4 -> 3, 11 -> 9) 

Puede leer mas sobre esto here.

ACTUALIZACIÓN:

Si usted lee la definición de breakOut, se dará cuenta que es básicamente una forma de crear un objeto de tipo esperado CanBuildFrom y pasándolo explícitamente al método. breakOut simplemente le ahorra teclear el siguiente texto estándar.

// Observe the error message. This will tell you the type of argument expected. 
scala> List((3, 4), (9, 11)).map(_.swap)('dummy) 
<console>:16: error: type mismatch; 
found : Symbol 
required: scala.collection.generic.CanBuildFrom[List[(Int, Int)],(Int, Int),?] 
       List((3, 4), (9, 11)).map(_.swap)('dummy) 
               ^

// Let's try passing the implicit with required type. 
// (implicitly[T] simply picks up an implicit object of type T from scope.) 
scala> List((3, 4), (9, 11)).map(_.swap)(implicitly[CanBuildFrom[List[(Int, Int)], (Int, Int), Map[Int, Int]]]) 
// Oops! It seems the implicit with required type doesn't exist. 
<console>:16: error: Cannot construct a collection of type Map[Int,Int] with elements of type (Int, Int) based on a coll 
ection of type List[(Int, Int)]. 
       List((3, 4), (9, 11)).map(_.swap)(implicitly[CanBuildFrom[List[(Int, Int)], (Int, Int), Map[Int, Int]]]) 

// Let's create an object of the required type ... 
scala> object Bob extends CanBuildFrom[List[(Int, Int)], (Int, Int), Map[Int, Int]] { 
    | def apply(from: List[(Int, Int)]) = foo.apply 
    | def apply() = foo.apply 
    | private def foo = implicitly[CanBuildFrom[Nothing, (Int, Int), Map[Int, Int]]] 
    | } 
defined module Bob 

// ... and pass it explicitly. 
scala> List((3, 4), (9, 11)).map(_.swap)(Bob) 
res12: Map[Int,Int] = Map(4 -> 3, 11 -> 9) 

// Or let's just have breakOut do all the hard work for us. 
scala> List((3, 4), (9, 11)).map(_.swap)(breakOut) : Map[Int, Int] 
res13: Map[Int,Int] = Map(4 -> 3, 11 -> 9) 

Answer 2

Ejemplo 1) correcta, no hay una lista intermedia

2) Sí, se obtiene una lista itermediate.

3) Nuevamente sí, obtienes una Lista de intermediarios de lo que tienes entre paréntesis. No hay "magia" pasando. Si tiene algo entre paréntesis, se evalúa primero.

No estoy seguro de lo que quiere decir con "deforestación" aquí: según Wikipedia significa eliminar las estructuras de los árboles. Si quiere decir eliminar listas intermedias, debe usar una vista . Véase, por ejemplo aquí: summing a transformation of a list of numbers in scala

Así que sin resultados intermedios, sus ejemplos serían (se requiere toSet porque de lo contrario usted tiene una IterableView[String,Iterable[_]])

BitSet(1,2,3).view.map(_ + "a").toSet 

List(1,2,3).view.map(_ -> "foo").toMap 

Map.empty ++ (List(1,2,3).view.map(_ -> "foo")) 

También hay un método force para ejecutar las operaciones de transformación, pero esto parece tener la mala costumbre de devolverle un tipo más general (quizás alguien pueda comentar con un motivo):

scala> Set(1,2,3).view.map(_ + 1).force 
res23: Iterable[Int] = Set(2, 3, 4)