## A plausible-sounding data structure that probably doesn’t exist

Here is a description of an abstract data type: a confluently persistent set data type containing a subset of the integers in a range $$[1..n]$$ and supporting $$O(\log(n)^c)$$ time creation, $$O(\log(n)^c)$$ time size query, $$O(n \log(n)^c)$$ time conversion to a duplicate-free list, and $$O(\log(n)^c)$$ time merging, for some constant $$c$$. Here, “creation” takes as arguments the range of the element domain $$[1..n]$$ and an optional single element in this range, and “merging” takes two sets with the same domain and returns a new set representing the union of the two input sets. In Haskell, the type signatures for these operations might look like this:

Seems fairly reasonable, right? I’m going to show that it is likely that no such data structure exists.