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.
Vectors (IPersistentVector)
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.
From http://clojure.org/data_structures
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.
Additional resources:
- Original implementation
- Data structures in Clojure
- Rich Hickey on "Persistent Data Structures and Managed References"
- Understanding Clojure’s PersistentVector implementation
- Hash array mapped trie
[…] the last post I wrote about the PersistentVector which I ported from Clojure to .NET. It’s implemented as an […]
Pingback by Porting Clojure’s persistent data structures to .NET part 2 of n – TransientVector » Rash thoughts about .NET, C#, F# and Dynamics NAV. — Tuesday, 29. May 2012 um 18:15 Uhr
You know this has already been done in the Clojure/CLR project?
https://github.com/clojure/clojure-clr/tree/master/Clojure/Clojure/Lib
Would perhaps be interesting to benchmark for implementation against the C# ones.
Comment by Martin Trojer — Tuesday, 29. May 2012 um 20:50 Uhr
How do we use it in F#? Can’t seem to get the syntax right.
Comment by Chris — Wednesday, 31. July 2013 um 7:15 Uhr