Scala for comprehensions and flatMap / map intermediate results

Question

From the first time I read that:

for {
  harpo<-list1 if harpo.length>0
  groucho<-list2
  chico<-list3
} yield (harpo, groucho, chico)

translates to:

list1.filter(_.length>0).flatMap(harpo =>      
      list2.flatMap(groucho=>list3.map((harpo,groucho,_)))
)

I was worried about unnecessary intermediate collections returned by filter, flatMap & map. The first was fixed in Scala 2.8(?) by addition of the withFilter method, and I suspect that there's some magic going on which changes the return type of these methods depending on usage so when used as a parameter to flatMap they return a non-strict collection, but I can't find any proof. Are my suspicions right and it isn't as ineffective as it seems by first glance?

score 5 · Answer 1 · edited May 23 '17 at 12:18

5

This relates to this question. Specifically, the answer by @IODEV shows you how to look at the desugared form:

$ scala -Xprint:typer -e
'val list1 = List("foo", "bar"); val list2 = list1; val list3 = list1;
for (harpo<-list1 if harpo.length>0; groucho <- list2; chico <- list3) 
yield (harpo, groucho, chico)'

(without line breaks)

list1.withFilter(_.length() > 0)
  .flatMap(harpo =>
    list2.flatMap(groucho =>
      list3.map(chico => (harpo, groucho, chico))
    )
  )

I don't see any wasted intermediate collections that you could save, unless you go for a mutable builder and while or foreach calls to fill that builder:

val b = List.newBuilder[(String, String, String)]
for(harpo <- list1 if harpo.length() > 0; groucho <- list2; chico <- list3) {
  b += ((harpo, groucho, chico))
}
b.result()

The question is, does your particular code exhibit a significant performance problem. E.g. your collections are tremendously large. If not, go with the more idiomatic form (for ... yield). Only optimise to a builder with for ... {} when you actually gain something from it.

edited May 23 '17 at 12:18

Community

1
1

answered May 26 '13 at 21:32

0__

66,707
21
171
266

Maybe I should have been more clear. My question is: are the collections returned by list3.map and list2.flatMap in this case strict or not? If they are strict, they are repeatedly built just to be discarded after putting their elements in the parent collection. If I just do `val l = list3.map("brother "+_)` I get a strict collection. A typical C++ pattern in such cases is to use a lazy intermediate type which gets implicitly transformed to a strict type when assigned to a variable of expected return type. I don't know if it's possible in scala, but its type inference still has secrets for me. – Turin May 26 '13 at 23:25
`list2` and `list3` are probably strict (you don't specify their types, but assuming they are of type `List`), thus the inner loops create strict intermediate results. I don't know C++ collections, but I doubt you can nest `flatMaps` in a lazy fashion that eliminates any intermediate collections— __`map`__ and __`filter`__ yes, but not __`flatMap`__. If you want that, use the iteration approach with builder and `foreach`. As I said, don't get trapped with premature optimisations. – 0__ May 27 '13 at 00:16

Scala for comprehensions and flatMap / map intermediate results

1 Answers1