性能 – 创建Set中所有元素对的Data.Set的最有效方法？

给定任意数组,保持任意数量的任意类型的元素,例如

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

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

基准测试可能证明我错了,但我的怀疑是,在设定的代表性中没有胜利.无论如何你都需要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]