3
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.