最有效的方法来创建Set中所有元素对的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,...

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

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]