Persistant bag/set with direct access to known elements 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 &quot;pointer&quot; to that element.
Add :: mystructure a -&gt; a -&gt; (mystructure a, myptr a)

Remove an element for which I have a &quot;pointer&quot;.
Remove :: mystructure a -&gt; myptr a -&gt; mystructure a

Enumerate all the elements in the set.
Enumerate :: mystructure a -&gt; [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.
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.