Komplexe Verschmelzung der Datenbeziehungen

Question

Nehmen wir an, ich habe eine Reihe von Beziehungen, die so aussehen:

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

Ich möchte diese Beziehungen in einen neuen Satz von Beziehungen von verwandeln As und Bs.

Nun, hier kommt das knifflige Zeug:

1. AS, die gleich sind, sollten ihre haben Bs mappended.
2. BS, die gleich sind, sollten ihre haben As mappended.
3. Wiederholen bis alles As und BS sind unterschiedlich (oder nicht, je nachdem, ob dies nicht mehr immer irgendwie erfolgen kann).

Bearbeiten: Die Bestellbeschränkung machte das Problem trivial, also habe ich es entfernt.

Man kann das annehmen Ord, Hashable, oder was auch immer Sie brauchen, was Sie brauchen. In jeder Hinsicht könnte man das sagen A verhält exakt wie HashSet und B verhält exakt wie Vector (oder ein anderer Typ mit angemessener Größenüberprüfung).

Dies bedeutet, dass man das annehmen kann let s = size (mappend a b); s >= size a; s >= size b, und das a, b :: B; mappend a b /= mappend b a <=> a, b not mempty; a > b => (mappend a c) > b, etc.

Ein Beispiel dafür, wie diese Transformation passieren würde (so tun <a, b> ist 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.

Wie kann dies so effizient wie möglich (Zeit, Raum) erfolgen?

Answer 1

Ich denke, der allgemeine Fall kann mit einem O (n^2) -GeuNge nicht besser als der unkomplizierte Weg durchgeführt werden, sodass der Gesamtalgorithmus o (n^3) sein könnte. Ohne Einschränkungen in der Reihenfolge der Elemente in der Liste und den Ergebnissen von mappend, Sie müssen jedes Elementpaar übereinstimmen, um festzustellen, ob sie zusammengeführt werden sollten, und wiederholen, bis sie fertig sind.

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