Functional equivalent to the concurrent multimap

Question

In another question, I asked about concurrent multimaps for Java.

Is there some functional programming (immutable) pattern that can be used instead in a Scala or Clojure program? I image that the Scala solution will probably involve actors and the clojure one an atom, ref or agent, but there may be a better way. Since both languages allow "falling back" to Java interop and just using a Java solution, I can use whatever answer I get to my first question, but that will not adhere to the functional programming paradigm. How do Haskell programmers solve this?

Answer 1

Standard Clojure maps and sets are immutable (and persistent)[1], so they work just as well in concurrent programs. You may want to store them in a ref/agent/var/atom depending on your requirements, and you can just update the ref/agent/var/atom as ever.

You can have a more mutable map, if the values are actually refs, like this:

{:a (ref #{1 2 3})
 :b (ref #{4 5 6})}

In this case, you'll be able to actually add values to already existing key (in transaction of course). Addition and removal of keys will still return new maps, which would share the same refs as the original maps, and so changes to one of them will be visible to the others:

user=> (def mmap {:a (ref #{1 2 3}) :b (ref #{4 5 6})})
#'user/mmap
user=> mmap
{:a #<Ref@be0446: #{1 2 3}>, :b #<Ref@10aa282: #{4 5 6}>}
user=> (def mmap2 (assoc mmap :c (ref #{7 8 9})))
#'user/mmap2
user=> mmap2
{:c #<Ref@405f6: #{7 8 9}>, :a #<Ref@be0446: #{1 2 3}>, :b #<Ref@10aa282: #{4 5 6}>}
user=> mmap
{:a #<Ref@be0446: #{1 2 3}>, :b #<Ref@10aa282: #{4 5 6}>}
user=> (dosync (alter (:a mmap2) conj 0))
#{0 1 2 3}
user=> mmap
{:a #<Ref@be0446: #{0 1 2 3}>, :b #<Ref@10aa282: #{4 5 6}>}
user=> mmap2
{:c #<Ref@405f6: #{7 8 9}>, :a #<Ref@be0446: #{0 1 2 3}>, :b #<Ref@10aa282: #{4 5 6}>}

[1] That is, adding/removing/modifying keys, and values actually return a new map, without changing the original.

Answer 2

A functional data structure is an immutable data structure. Immutable data structures do not have problems with concurrency because they cannot be modified.