Performance of multiple generators in Scala 'for' expressions?

Question

An example:

for(x <- c1; y <- c2; z <- c3) yield {...}

which can be translated into:

c1.flatMap(x => c2.flatMap(y => c3.map(z => {...})))

or:

for(x <- c1) for (y <- c2) for (z <- c3) yield {...}

Time complexity is O(c1 * c2 * c3) according to the second translation, what if c1, c2, c3 are very big numbers?

I tried to search on the internet, and I found there are many codes who have much more generators than this example.

Question: In other languages, we want to avoid nested for loops, but why scala designed this mechanism, dose it have some special tricks to make a very good performance for the nested loop ?

If I misunderstand something, please tell me, I would like to know better the for-comprehension in scala. Thank you.

Answer 1

There are two reasons why one may wish to avoid nested loops. The first one, the readability and quality of the code (especially in OOP). The second, as you said, performance, but it isn't a hard rule. This is more like an indicator, that you may have in this place slower code and it's worth verifying whether it is possible to do the same thing faster. Obviously, many problems just require O(n^2) steps and it doesn't matter if you implement it using nested loops or some other way. E.g. most trivial case, if you have two collections of size n and you want to print all pairs (Cartesian product), it just requires O(n^2) steps and that's it.

And remember that for-comprehension in Scala isn't just a replacement for for instructions from other languages. It gives you a nice way for working with Monads and writing more readable code. Having multiple expressions inside the for doesn't necessarily mean that you have a performance problem here.