Right, except for the fact that they always are made to behave that way, and if I were using a language with a "vector" type which performed like a linked list i would probably stop using that language altogether.
It has nothing to do with pointers, but memory access patterns can have a huge performance impact. Iterate over a large array, and do the same over a large linked list. The latter cannot make use of the CPU cache in any meaningful way, for example.
I agree, memory access patterns can have a huge performacne impact. The cache is importent but its not as simple as you think.
Im not gone explain to you why it work, but see paper [1].
Its not about the clojure vector, but basiclly the same and he explains performance and he it is quite fast for lookup. Adding is also quite fast, both for immutable and the mutable case.
And the linked list can share storage between different lists which the straight array cannot. There are always benefits and drawbacks with different structures. "list" doesn't say what data structure is used, it only describes the semantics (an ordered collection of items). It's the same with a vector.
much of the point of immutable data structures is to re-use the storage of items. A mutable vector is usually just a continuous array for that reason (can't re-use so just as well to optimize for compactness and access). But an immutable vector isn't as natural to store in an array.
The opinion that vector must equal array is presumably because people have used mutable vectors in e.g Java or C++ and assumed the underlying data structure is the same in other contexts.
A mutable List is very natural to implement array based, but an immutable List is usually not. It's the same thing.
