Scala Immutable MultiMap

Question

In Scala I would like to be able to write

val petMap = ImmutableMultiMap(Alice->Cat, Bob->Dog, Alice->Hamster)

The underlying Map[Owner,Set[Pet]] should have both Map and Set immutable. Here's a first draft for ImmutibleMultiMap with companion object:

import collection.{mutable,immutable}

class ImmutableMultiMap[K,V] extends immutable.HashMap[K,immutable.Set[V]]

object ImmutableMultiMap {
  def apply[K,V](pairs: Tuple2[K,V]*): ImmutableMultiMap[K,V] = {
    var m = new mutable.HashMap[K,mutable.Set[V]] with mutable.MultiMap[K,V]
    for ((k,v) <- pairs) m.addBinding(k,v)
    // How do I return the ImmutableMultiMap[K,V] corresponding to m here?
  }
}

Can you resolve the comment line elegantly? Both the map and the sets should become immutable.

Thanks!

This may be useful as an example of how to convert a mutable to an immutable map: http://stackoverflow.com/questions/2817055/converting-mutable-to-immutable-map — Arjan Blokzijl, Aug 08 '10 at 07:48

score 5 · Answer 1 · answered Dec 16 '10 at 00:04

I've rewritten this same method twice now, at successive jobs. :) Somebody Really Oughta make it more general. It's handy to have a total version around too.

  /**
   * Like {@link scala.collection.Traversable#groupBy} but lets you return both the key and the value for the resulting
   * Map-of-Lists, rather than just the key.
   *
   * @param in the input list
   * @param f the function that maps elements in the input list to a tuple for the output map.
   * @tparam A the type of elements in the source list
   * @tparam B the type of the first element of the tuple returned by the function; will be used as keys for the result
   * @tparam C the type of the second element of the tuple returned by the function; will be used as values for the result
   * @return a Map-of-Lists
   */
  def groupBy2[A,B,C](in: List[A])(f: PartialFunction[A,(B,C)]): Map[B,List[C]] = {

    def _groupBy2[A, B, C](in: List[A],
                           got: Map[B, List[C]],
                           f: PartialFunction[A, (B, C)]): Map[B, List[C]] =
    in match {
      case Nil =>
        got.map {case (k, vs) => (k, vs.reverse)}

      case x :: xs if f.isDefinedAt(x) =>
        val (b, c) = f(x)
        val appendTo = got.getOrElse(b, Nil)
        _groupBy2(xs, got.updated(b, c :: appendTo), f)

      case x :: xs =>
        _groupBy2(xs, got, f)
    }

    _groupBy2(in, Map.empty, f)
  }

And you use it like this:

val xs = (1 to 10).toList
groupBy2(xs) {
  case i => (i%2 == 0, i.toDouble)
}   

res3: Map[Boolean,List[Double]] = Map(false -> List(1.0, 3.0, 5.0, 7.0, 9.0),       
                                      true -> List(2.0, 4.0, 6.0, 8.0, 10.0))

Used this answer many times. Note that `Seq` is more general than list and just requires changing the signatures and converting `c :: appendTo` to be `c +: seq`. I think that the answer would be improved by upgrading to `Seq`? — simbo1905, Dec 12 '15 at 20:39

score 3 · Answer 2 · answered Aug 07 '10 at 19:28

3

You have a bigger problem than that, because there's no method in ImmutableMultiMap that will return an ImmutableMultiMap -- therefore it is impossible to add elements to it, and the constructor does not provide support for creating it with elements. Please see existing implementations and pay attention to the companion object's builder and related methods.

answered Aug 07 '10 at 19:28

Daniel C. Sobral

295,120
86
501
681

Thanks Daniel. I did try and decipher the builder stuff, by walking through the source code for the companion object to immutable.HashSet. However, I cannot make sense of it. Would you mind showing me how you would solve the problem of constructing the desired ImmutableMultiMap? – PerfectTiling Aug 08 '10 at 00:35

Scala Immutable MultiMap

2 Answers2