Комплексное слияние данных отношений - PullRequest
Новая
       29

Комплексное слияние данных отношений

3 голосов
/ 11 января 2012

Допустим, у меня есть набор отношений, который выглядит следующим образом: 

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

Я хочу преобразовать этот набор отношений в новый набор отношений A с и B с..

Теперь, вот такие хитрые вещи:

  1. A s, которые равны, должны иметь свои B s mappend ed.
  2. B равных должны иметь свои A s mappend ed.
  3. Повторять до тех пор, пока все A s и B s не будут различны (или нет, в зависимости от того, может ли это бытькак-то не итеративно).

РЕДАКТИРОВАТЬ: ограничение порядка упорядочило проблему, поэтому я ее убрал.

Можно предположить, что 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.

Как это можно сделать максимально эффективным образом (время, пространство)?

1 Ответ

2 голосов
/ 11 января 2012

Я думаю, что общий случай не может быть лучше, чем простой способ слияния 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
...