数据关系的复杂合并

Question

假设我有一组如下所示的关系：

relations :: [(A, B)]
instance Monoid A
instance Monoid B

我想将这组关系转换为一组新的 A 和 B 关系。

现在，棘手的事情来了：

1. 相等的 A 应该对其 B 进行 mappend 编辑。
2. 相等的 B 应该对其 A 进行 mappend 编辑。
3. 重复直到所有 A 和 B 都不同（或者不不同，取决于是否可以以非迭代方式完成）。

编辑：排序约束使问题变得微不足道，因此我将其删除。

人们可以假设 Ord、Hashable 或您需要的任何其他内容是可用的。出于所有意图和目的，我们可以说 A 的行为完全类似于 HashSet，而 B 的行为完全 就像 Vector （或具有合理大小检查的其他类型）。

这意味着可以假设 let s = size (mappend ab); s>=尺寸a； s >= size b，并且 a, b :: B; mappend ab /= mappend ba <=>; a、b不为空； a＞ b => (映射ac)> b 等。

如何发生的示例（假设 是 Set.fromList [a, b]）

[(<1>, [a]), (<4>, [d]), (<2>, [b]), (<5>, [e]), (<1>, [b]), (<2>, [a]), (<3>, [c])]
-- Merge `A`s for equal `B`s
[(<1,2>, [a]), (<4>, [d]), (<1,2> [b]), (<5>, [e]), (<3>, [c])]
-- Merge `B`s for equal `A`s
[(<1,2>, [a, b]), (<4>, [d]), (<5>, [e]), (<3>, [c])]
-- All values are distinct, so we're done.

此转换 这可以以尽可能有效的方式（时间、空间）完成吗？

Answer 1

我认为一般情况不能比 O(n^2) 合并的直接方法更好，因此总算法可能是 O(n^3)。在不限制列表中元素的顺序和mappend结果的情况下，您必须匹配每对元素以查看它们是否应该合并，然后重复直到完成。

merge :: Eq e => (a -> a -> a) -> (a -> e) -> [a] -> (Bool,[a])
merge combine eqval [] = (False, [])
merge combine eqval (x:xs) = (not (null a) || t, y : zs)
  where
    e = eqval x
    (a,b) = partition ((e ==) . eqval) xs
    y = mconcat (x:a)
    (t,zs) = merge combine eqval b

mergeRelations :: [(A,B)] -> [(A,B)]
mergeRelations = go False
  where
    mergeFsts = merge (\(a1,b1) (a2,b2) -> (a1, b1 `mappend` b2)) fst
    mergeSnds = merge (\(a1,b1) (a2,b2) -> (a1 `mappend` a2, b1)) snd
    go started xs
      | started && not f = xs
      | s = go True n
      | otherwise = m
        where
          (f,m) = mergeFsts xs
          (s,n) = mergeSnds m