Introducing immutable, growing vectors

Question

I am interested in implementing constant (e.g. purely functional, immutable, etc.) growing vectors in F # so that they can be used in the .NET environment. My current implementation is an option in the Hash-Mapped Trie and runs according to the Clojure implementation .

I am having problems implementing insertion and deletion of random access (insertion and deletion of elements by random indexes) using this implementation. Is there any algorithm / modification that allows me to efficiently perform these operations or some other implementation that I can look at?

Explanation: When I say “inserts” and “deletes,” I mean, for example, given the list [1; 2; 3; 4] [1; 2; 3; 4] [1; 2; 3; 4] inserting 500 at position 1 will give me [1:500:2:3:4] . I do not mean the set or associate operation.

Answer 1

The fingers of the trees may be what you are looking for. There is a Clojure implementation .

Answer 2

Immutable vectors / lists usually provide quick updates, allowing only inserts from one end and then sharing immutable data at the other end. If you want to do non-main / tail inserts, what you really want to do is change the immutable end of your collection. You will need to divide the vector around the element that you want to insert, and then combine it again to create a new vector, and best of all you can do it - this is O (n) time.

Immutable sorted trees work a little differently, but they won't let you re-specify characters (keys) in less than O (n) time.

In principle, if someone has discovered an effective way to support random access inserts in an immutable vector, then it will be supported in one of the main functional languages ​​- but there is no such known data structure or algorithm, so there are no such implementations.

Answer 3

The only thing that can be done is split and unification. This is very inefficient with clojure vectors. This is why Phill Bagwell has listed a stable vector that you can split and join log (n).

You might want to watch this video: http://blip.tv/clojure/phill-bagwell-striving-to-make-things-simple-and-fast-5936145

or directly on his paper here: infoscience.epfl.ch/record/169879/files/RMTrees.pdf

Answer 4

Put the Haskell Hamt library ? Insert operation - O (log n)