performance - 创建集合中所有元素对的 Data.Set 的最有效方法是什么？

Question

给定一个任意集合，其中包含任意数量的任意类型的元素，例如

mySet1 = Set.fromList [1,2,3,4]

或者

mySet2 = Set.fromList ["a","b","c","d"]

或者

mySet3 = Set.fromList [A, B, C, D]

对于某些数据构造函数 A、B、C、D、...

生成所有无序元素对的集合的计算上最有效的方法是给定集合？ IE。

setPairs mySet1 == Set.fromList [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

或者

setPairs mySet2 == fromList [ ("a","b")
                            , ("a","c")
                            , ("a","d")
                            , ("b","c")
                            , ("b","d")
                            , ("c","d") ]

或者

setPairs mySet2 == fromList [ (A,B)
                            , (A,C)
                            , (A,D)
                            , (B,C)
                            , (B,D)
                            , (C,D) ]

我最初的天真猜测是:

setPairs s = fst $ Set.fold
    (\e (pairAcc, elementsLeft) ->
        ( Set.fold
              (\e2 pairAcc2 ->
                  Set.insert (e2, e) pairAcc2
              ) pairAcc $ Set.delete e elementsLeft
        , Set.delete e elementsLeft )
    ) (Set.empty, s) s

但这肯定不是最好的解决方案吗？

Answer 1

基准测试可能证明我错了，但我怀疑留在设定的表示中没有胜利。无论如何，您都将需要 O(n^2) ，因为这是输出的大小。主要优势是生成您的列表，以便您可以调用 S.fromDistinctAscList这样它只花费 O(n) 来构建集合本身。

以下内容非常简洁，保留了相当多的共享，并且通常是我能想象到的最简单、最直接和直观的解决方案。

pairs s = S.fromDistinctAscList . concat $ zipWith zip (map (cycle . take 1) ts) (drop 1 ts)
   where ts = tails $ S.toList s

编辑

更短/更清晰(不确定性能，但可能一样好/更好):

pairs s = S.fromDistinctAscList [(x,y) | (x:xt) <- tails (S.toList s), y <- xt]