Persistant bag/set with direct access to known elements
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.