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:
data MergeableSet = ...
type Elem = Int
empty :: (Elem, Elem) -> MergeableSet
singleton :: (Elem, Elem) -> Elem -> MergeableSet
size :: MergeableSet -> Int
toList :: MergeableSet -> [Elem]
union :: MergeableSet -> MergeableSet -> MergeableSet
Seems fairly reasonable, right? I’m going to show that it is likely that no such data structure exists.