Update Immutable Map How's the following function to update an immutable Map's values? 

scala&gt; def updateMap[A](map: Map[A, Set[A]], item: A, toAdd: A) = { 
    map.map(x =&gt; if(x._1 == item) (x._1, (x._2 + toAdd)) else (x._1, x._2)) 
}

scala&gt; val map = Map(1 -&gt; Set(2), 3 -&gt; Set(4))

scala&gt; updateMap(map, 1, 5)
res1 ...= Map(1 -&gt; Set(2, 5), 3 -&gt; Set(4))
You iterate through the whole Map, which is O(n) and therefore slow as hell. Worse, you even recreate every element and put it into another element, which is even slower.

Why not just do:

scala&gt; val map = Map(1 -&gt; Set(5,3), 2 -&gt; Set(7,3))
map: scala.collection.immutable.Map[Int,scala.collection.immutable.Set[Int]] = Map(1 -&gt; Set(5, 3), 2 -&gt; Set(7, 3))

scala&gt; def updateMap[A, B](map: Map[A, Set[B]], key: A, value: B) =
         map + ((key, map.getOrElse(key, Set()) + value))
updateMap: [A, B](map: Map[A,Set[B]], key: A, value: B)scala.collection.immutable.Map[A,Set[B]]

scala&gt; updateMap(map, 1, 9)
res0: scala.collection.immutable.Map[Int,Set[Int]] = Map(1 -&gt; Set(5, 3, 9), 2 -&gt; Set(7, 3))


And you probably want to introduce another type parameter B to the signature of updateMap to allow values of a different type than the one of the key.