Converting a Scala Map to a List

Question

I have a map that I need to map to a different type, and the result needs to be a List. I have two ways (seemingly) to accomplish what I want, since calling map on a map seems to always result in a map. Assuming I have some map that looks like:

val input = Map[String, List[Int]]("rk1" -> List(1,2,3), "rk2" -> List(4,5,6)) 

I can either do:

val output = input.map{ case(k,v) => (k.getBytes, v) } toList 

Or:

val output = input.foldRight(List[Pair[Array[Byte], List[Int]]]()){ (el, res) =>   (el._1.getBytes, el._2) :: res } 

In the first example I convert the type, and then call toList. I assume the runtime is something like O(n*2) and the space required is n*2. In the second example, I convert the type and generate the list in one go. I assume the runtime is O(n) and the space required is n.

My question is, are these essentially identical or does the second conversion cut down on memory/time/etc? Additionally, where can I find information on storage and runtime costs of various scala conversions?

Thanks in advance.

Answer 1

My favorite way to do this kind of things is like this:

input.map { case (k,v) => (k.getBytes, v) }(collection.breakOut): List[(Array[Byte], List[Int])] 

With this syntax, you are passing to map the builder it needs to reconstruct the resulting collection. (Actually, not a builder, but a builder factory. Read more about Scala's CanBuildFroms if you are interested.) collection.breakOut can exactly be used when you want to change from one collection type to another while doing a map, flatMap, etc. — the only bad part is that you have to use the full type annotation for it to be effective (here, I used a type ascription after the expression). Then, there's no intermediary collection being built, and the list is constructed while mapping.

Answer 2

Mapping over a view in the first example could cut down on the space requirement for a large map:

val output = input.view.map{ case(k,v) => (k.getBytes, v) } toList