I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations.
Clojure provides persistent Vector, but it's only for fast append. Scala's Vector has effectively constant-time append and prepend, but I can't get how it's implemented, since it's based on same data structure (bit-mapped vector trie) as Clojure vector, and, as I understand, bit-mapped vector trie can't have fast prepend without some tricks.
I'm interested not in ready to use implementation but in a description of how to implement such a data structure myself.