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 ...
Get Learning F# Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
