How can I elegantly invert a Map's keys and values?

Question

I have a Map (or associative list) that looks like this:

[("A", ["KB", "KC"]), ("B", ["KD", "KE"])]

How can I concisely transform the above Map so that the keys are the values and the values are the keys, so that the result should look like this?

[("KB", "A"), ("KC", "A"), ("KD", "B"), ("KE", "B")]

EDIT

Here is my solution

invertAList xs = [(val,key) |  (key, vals) <- xs, val <- vals]

Answer 1

One of the key problems here is how to handle the case where a value appears more than once in the "right hand side" assignments:

import Data.Map (Map)
import qualified Data.Map as Map

-- "KB" occurs twice.
example = Map.fromList [("A", ["KB", "KC"]), ("B", ["KD", "KB"])]

The solution is to use Map.fromListWith:

invert :: Ord v => Map k [v] -> Map v [k]
invert m = Map.fromListWith (++) pairs
    where pairs = [(v, [k]) | (k, vs) <- Map.toList m, v <- vs]

{-
>>> invert (Map.fromList [("A", ["KB", "KC"]), ("B", ["KD", "KE"])])
fromList [("KB",["A"]),("KC",["A"]),("KD",["B"]),("KE",["B"])]

>>> invert (Map.fromList [("A", ["KB", "KC"]), ("B", ["KD", "KB"])])
fromList [("KB",["B","A"]),("KC",["A"]),("KD",["B"])]
-}