optimization - 复杂的数据关系合并

假设我有一组看起来像这样的关系：

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

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

现在，这是棘手的事情：


相等的A应具有B的mappend。
相等的B应具有A的mappend。
重复直到所有A和B都不同（或不同，取决于是否可以以某种方式非迭代地完成）。


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

可以假定Ord，Hashable或您需要的其他任何内容都可用。出于所有意图和目的，可以说A的行为与HashSet完全相同，而B的行为与Vector完全相同（或其他具有合理大小检查的类型）。

这意味着可以假定let s = size (mappend a b); s >= size a; s >= size b以及a, b :: B; mappend a b /= mappend b a <=> a, b not mempty; a > b => (mappend a c) > b等。

此转换如何发生的示例（假设<a, 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.

如何以尽可能有效的方式（时间，空间）完成此操作？

最佳答案

我认为一般情况不能比使用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