如何优雅地反转Map的键和值？

Question

我有一个如下所示的Map(或关联列表):

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

如何简洁地转换上面的Map,以便键是值,值是键,所以结果应该是这样的？

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

编辑

这是我的解决方案

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

Answer 1

这里的一个关键问题是如何处理"右侧"赋值中出现多次值的情况:

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

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

解决方案是使用Map.fromListWith:

invert :: (Ord k, 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"])]
-}

Answer 2

怎么样

Prelude> let xs = [("A", ["KB", "KC"]), ("B", ["KD", "KE"])]
Prelude> concatMap (\(k, vs) -> [(v, k) | v <- vs]) xs
[("KB","A"),("KC","A"),("KD","B"),("KE","B")]