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 2 of n – TransientVector

Filed under: C#,F# — Steffen Forkmann at 18:15 Uhr

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.

Tags: , , ,

4 Comments »

  1. Thanks for this worthy addition to data structures. I have one objection, however. You added the static method “cons” to IVector which performs vector.Conj (adding the new element to the end). I think this is confusing, since every language I have seen “cons” used (admittedly not very many), including in F# Lists, “cons” adds the new element at the head of the collection, it does not append it at the end.

    Comment by Jack Fox — Thursday, 7. June 2012 um 18:01 Uhr

  2. […] Porting Clojure’s Persistent Data Structures to .NET, part 2 […]

    Pingback by Lambda_Jam_fsharp_bibliography | craftyThoughts — Tuesday, 2. July 2013 um 3:53 Uhr

  3. FWIW, the conventional name for append in functional programming is snoc because that is cons spelled backwards. Personally, it is a convention I find hideous in the extreme. I would much prefer “append” and “prepend”!!!

    Comment by Jon Harrop — Thursday, 28. November 2013 um 12:33 Uhr

  4. I think conj is the name used in Clojure so we copied this.

    IIRC Jack Fox added added snoc as an alias, but not sure.

    Comment by Steffen Forkmann — Thursday, 28. November 2013 um 12:49 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> .