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

In the last post I wrote about the PersistentVector which I ported from Clojure to .NET. It’s implemented as an immutable hash array mapped trie which optimizes the constant factors so that we can assume O(1) for count, nth, conj, assocN, peek and pop.

But for some applications Rich Hickey shows us that we can optimize the constant factors even further. If we are sure that we are only holding exactly one reference to the vector than we can mutate the underlying representation instead of copying the arrays on every change. This idea is implemented in the TransientVector which I also ported from Clojure.Core to FSharpx.

Let’s look at a small example. Here we want to convert a collection to a PersistentVector:

As you can see we iterate over the collection and conj the items to the current PersistentVector. But in every step we forget the reference to the last version. This is exactly the point where can use TransientVector:

Here are the results:

Most higher-order functions on vectors like map are also implemented with this trick.

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