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: clojure, F#, FSharpx, persistent data structures