Most efficient way to create the Data.Set of all pairs of elements in a Set?

Question

Given an arbitrary set holding an arbitrary number of elements of arbitrary type, e.g.

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

or

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

or

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

for some data constructors A, B, C, D, ...

What is the computationally most efficient way to generate the set of all unordered pairs of elements is the given set? I.e.

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

or

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

or

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

---

My initial naive guess would be:

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

but surely that cannot be the best solution?

Answer 1

Benchmarking might prove me wrong, but my suspicion is that there's no win in staying in the set representation. You're going to need O(n^2) regardless, because that's the size of the output. The key advantage would be producing your list such that you could use a call to S.fromDistinctAscList such that it only costs O(n) to build the set itself.

The following is pretty clean, preserves a fair amount of sharing, and is generally the simplest, most straightforward and intuitive solution I can imagine.

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

---

Edit

Shorter/clearer (not sure performancewise, but probably as good/better):

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