25 September 2009

Scala: Map of Lists

Every developer has had to deal with a Map whose key is of type X and whose value is a list. Additions to the map often happen like this in Java:


List l = map.get(key);
if ( l == null ) {
l = new ArrayList();
map.put(key, l);
}
l.add(value);


Kind of cumbersome, and kind of not thread-safe.

What is to be done?

Well, google-collections tries to take care of the cumbersome-ness with their MultiMap class. The put looks the same as in java.util.Map, but the get returns a List instead.

So, instead of the code above, you get:


map.put(key, value);


Now, if you want thread-safety as well, you call MultiMaps.synchronizedMap, passing your existing MultiMap.

So, I had a specific case that I was working on which was basically a group by function given a list of C. My decision was to create in the end a map with an A for the key and a List of B for the value where A is the type of the group by property and B a projection of C (So, the List could be of C as well).

Here is what I came up with:


def inclAsList[A,B,C](keyresolver:C=>A, valueresolver:A=>List[B], list:List[C]) = {
Map[A,List[B]](
(list map { el => keyresolver(el) } removeDuplicates)
map { key => (key, valueresolver(key)) }
: _*
)
}


So, this is thread-safe. What it does is takes the list of C and applies a function to find the group by properties. Then, iterating through those, it applies a function with each key to get a list of values that match.

"But what about 'put'?" you say. The thing is, once you have immutability built in, you will find that the need to be able to modify a map doesn't come up as often. This example is prime--because Maps and Lists are immutable in Scala, we are nearly there before we know it regarding thread safety.