Geek Answers Handbook

Deforestation in Scala collections

From the design of Scala collections, I understand that something like:

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

does not create an intermediate data structure: a new set is created when the bitset is executed using Builder. In fact, this is obvious in this case, since the bitset of strings does not make sense.

What about cards from lists? I am sure that the following is building an interim list:

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

namely a list List((1,foo), (2,foo), (3,foo)). If not, how? Now, what about the next one?

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)

This time, from what I seem to understand from type ++:

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

I think it may be that the map is built on the fly and that no intermediate list is built.

This is true? If so, is this a canonical way to ensure deforestation, or is there a simpler syntax?

+5
2

breakOut, . :

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

.

UPDATE:

breakOut, , CanBuildFrom . breakOut .

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

1) ,

2) , itermediate.

3) , , . "". -, .

, "" : , . , . . : scala

,

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

(toSet , IterableView[String,Iterable[_]])

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

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

force , , , (, - ):

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

More articles:


All Articles