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

haskell

Solution

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"])]
-}

Problem

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] ```

Original source