faster slicing for vectors? about rpds HOT 3 OPEN

Currently Vector<_> doesn't support operations that push or drop from the front. We don't need finger trees to implement that. The data structure can be modified to allow for those operations, it is just that I never got to implement those (issue #17).

Vector<_> needs some love at this point. I'll try to allocate some time to it next month (I /should/ have some free time for that).

from rpds.

+1 - would be great to have an O(1) way to do slices that takes advantage of structural sharing

from rpds.

Well...just so you know this problem is actually quite difficult because the OG Clojure that popularized this idea doesn't support prepending/drop front either: https://stackoverflow.com/questions/4095714/what-is-the-idiomatic-way-to-prepend-to-a-vector-in-clojure

If we can make it so that we can efficiently drop front, then implementing slice/ops::Range can be amortized to O(log n), by repeating drop front until range start, and repeating drop back until range end.

If we can have the other way round, I think we need to modify the data structure used for persistent vector in rpds to support efficient meld operation. That means we can quickly access the "chunks" of different shared vectors, separated like a B-Tree, and we can first persistent clone the whole tree, then find the specific leaf, and clone it to a normal vector, remove the sub-index in the cloned normal vector according to the item position in the chunk, and then meld (aka tree merge) this new vector back to the rest of the tree. This can achieve structural sharing to some sort, but it will sure be hell to implement. (I took this idea from rope data structure)

Wait hold on. No way, did I just reinvented finger tree?

from rpds.