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:

1 2 3 4 5 6 7 8 |
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**.

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