Vectors

Lists are an effective data structure when the processing is focused mainly on the head element, which takes a constant time to access. For the elements further within the list, the access time is linearly proportional to the depth of the list, that is, their position within the list. This random access issue on the list is addressed by vectors in various functional (or multi-paradigm) programming languages such as Scala. Scala is to JVM what F# is to .NET. A vector is built as a collection type based on bit-mapped vector tries, providing a solution to the inadequacy of random access on lists.

Note

A discussion on bit vector optimization and tries are beyond the scope of this book. However, you can find an excellent talk on Persistent Data Structures and Managed References by Rich Hickey, the author of Clojure at www.infoq.com/presentations/Value-Identity-State-Rich-Hickey.

The conventional implementation of vectors can rapidly access an indexed array element. However, a bitmapped vector...