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.