Rash thoughts about .NET, C#, F# and Dynamics NAV.

"Every solution will only lead to new problems."

Tuesday, 29. May 2012

Porting Clojure’s persistent data structures to .NET part 1 of n – PersistentVector

Filed under: C#,F# — Steffen Forkmann at 14:41 Uhr

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:

Tags: , , , , ,


  1. […] 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

  2. You know this has already been done in the Clojure/CLR project?


    Would perhaps be interesting to benchmark for implementation against the C# ones.

    Comment by Martin Trojer — Tuesday, 29. May 2012 um 20:50 Uhr

  3. 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

RSS feed for comments on this post. | TrackBack URI

Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> .