Rich Hickey created a very nice set of persistent collections for Clojure. I started to port them to FSharpx and today I want to present the PersistentVector. The basic idea is that we want to have something like an array but immutable.
A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. count is O(1). conj puts the item at the end of the vector.
These vectors are very fast in practical applications since the depth of the underlying tree is not greater than 7. First performance tests show the following on my machine:
These results are not that far away from the Clojure/Java implementation (see below). The lookup seems to be a bit faster but assoc is slower. Maybe that has something to do with the internal array copy function of .NET:
After installing the FSharpx nuget package can use this Vector<T> from C# like this:
More samples can be found in the PersistentVectorTest.fs file.
- Original implementation
- Data structures in Clojure
- Rich Hickey on "Persistent Data Structures and Managed References"
- Understanding Clojureâ€™s PersistentVector implementation
- Hash array mapped trie