複雑なマージ

Question

のは、私はこのようになります関係の集合を持っているとしましょう：

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

私はA Sの関係とB Sの新しいセットに関係のこのセットを変換したいです。そのBのmappend編を持っている必要があり等しい

1. A S：

   は今、ここにトリッキーなものをしています。

2. Bは、A s mappend edである必要があります。
3. AとBが別々のものになるまで繰り返す（そうでない場合は、何らかの理由でこれをやり直すことができるかどうかによって異なります）。

EDIT：注文の制約により問題は些細なものになっていたので、削除しました。

Ord,Hashableなど、必要なものはすべて利用可能です。すべての意図や目的のために、一つはAがを振る舞う正確HashSetとB等が正確Vector（または合理的なサイズのチェックといくつかの他のタイプ）などが動作することを言うことができます。

これは、など

この変換が起こる方法の例

[(<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. 

これを行うことができますどのように（<a, b>がSet.fromList [a, b]であることをふり）1は、その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を、想定することができることを意味しできるだけ効率的な方法で（時間、空間）？

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