Persistant bag/set with direct access to known elements

Question

I'm looking for a bag or set data structure that will allow for the following operations:

• Add an element to the set, and get a "pointer" to that element.

  Add :: mystructure a -> a -> (mystructure a, myptr a)

• Remove an element for which I have a "pointer".

  Remove :: mystructure a -> myptr a -> mystructure a

• Enumerate all the elements in the set. Enumerate :: mystructure a -> [a]

Note that I don't really care about duplicate values (the values I enter are already unique), nor the order of elements.

A very simple implementation for this structure would be to use a doubly-linked list, with the standard Add returning a pointer to the newly created list node, the standard Remove removing such a node from the list, and Enumerate simply traversing the list.

However, I need the structure to be immutable/persistant (i.e. the Add and Remove operations don't modify the original data structure). Ideally, the operations would still be O(1), like with a doubly-linked list. I think finger trees could be used for this, but I don't know them well.

Answer 1

You can solve this with a dictionary, using myptr a = a.

You can get $O(\lg n)$ add and remove in an immutable data structure by using a balanced binary search tree. Enumerate will take $O(n)$ time, but the $i$th element can be made available in $O(i)$ time, so your enumerate result can keep up with any consumption of it.

"Confluently Persistent Tries for Efficient Version Control", by Erik D. Demaine, Stefan Langerman, and Eric Price provides a dictionary that is fully persistent, but not immutable. With it, you can get the same bound on enumerate, and a $O(\lg \lg n)$ bound on add and remove.