La deforestazione in collezioni Scala

Question

Dalla progettazione delle collezioni di Scala capisco che qualcosa di simile:

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

Non si costruisce un datastructure intermedio: il nuovo set è costruito come il BitSet viene iterato rispetto all'uso di un cantiere. In questo caso, infatti, è ovvio dato che un insieme di stringhe non ha senso.

E le mappe dalle liste? Sono abbastanza sicuro che il seguente costruisce 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) 

vale a dire l'elenco List((1,foo), (2,foo), (3,foo)). Se no, allora come? Ora, per quanto riguarda i seguenti?

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) 

Questa volta, da quello che mi sembra di capire dal tipo di ++:

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

ho penso potrebbe essere il caso che la mappa è costruito al volo, e che nessun la lista intermedia è costruita

È il caso? Se sì, è questo il modo canonico per garantire la deforestazione o esiste una sintassi più semplice?

Answer 1

È possibile utilizzare breakOut per garantire che non venga creata alcuna raccolta intermedia. Per esempio:

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

Si può leggere di più su di esso here.

UPDATE:

Se si legge la definizione di breakOut, si noterà che è fondamentalmente un modo per creare un oggetto di tipo previsto CanBuildFrom e passando in modo esplicito al metodo. breakOut ti impedisce semplicemente di digitare il seguente codice.

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

Esempio 1) Corretto, non c'è nessuna lista intermedia

2) Sì, si ottiene un elenco itermediate.

3) Ancora una volta, si ottiene una lista intermedia da ciò che si ha tra parentesi. Non c'è "magia" in corso. Se hai qualcosa tra parentesi, viene valutato prima.

Non sono sicuro di cosa intenda per "deforestazione" qui: secondo Wikipedia significa eliminare le strutture ad albero. Se intendi eliminare gli elenchi intermedi, devi utilizzare una vista . Si veda ad esempio qui: summing a transformation of a list of numbers in scala

Quindi, senza risultati intermedi, i tuoi esempi sarebbe (è necessaria toSet perché altrimenti si dispone di un 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")) 

C'è anche un metodo force per eseguire le operazioni di trasformazione, ma questo sembra avere la brutta abitudine di restituirti un tipo più generale (forse qualcuno può commentare con un motivo):

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