Understanding Clojure’s Persistent Vectors, pt. 1 by Jean Niklas L’orange.
From the post:
You may or may not heard about Clojure’s persistent vectors. It is a data structure invented by Rich Hickey (influenced by Phil Bagwell’s paper on Ideal Hash Trees) for Clojure, which gives practically O(1) runtime for insert, update, lookups and subvec. As they are persistent, every modification creates a new vector instead of changing the old one.
So, how do they work? I’ll try to explain them through a series of blogposts, in which we look at manageable parts each time. It will be a detailed explanation, with all the different oddities around the implementation as well. Consequently, this blog series may not be the perfect fit for people who want a “summary” on how persistent vectors work.
For today, we’ll have a look at a naive first attempt, and will cover updates, insertion and popping (removal at the end).
Note that this blogpost does not represent how PersistentVector is implemented: There are some speed optimizations, solutions for transients and other details which we will cover later. However, this serves as a basis for understanding how they work, and the general idea behind the vector implementation.
….
The sort of post that makes you start wondering why we don’t have a persistent data model for XTM based topic maps?
With persistent we get to drop all the creating new identifiers on merges, creating sets of identifiers, determining if sets of identifiers intersect, to say nothing of having persistent identifiers for interchange of data with other topic maps. A topic’s identifier is its identifier today, tomorrow and at any time to which it is persisted.
To say nothing of having an audit trail for additions/deletions plus “merges.”
While you are considering those possibilities, see: Understanding Clojure’s Persistent Vectors, pt. 2