Random Access Lists for Emacs

Here is a quick post: I've added an implementation of random access lists to my Emacs Lisp library. These are a persistent data structure which supports fast persistent list operations (O(1)) as well as pretty fast random-access and persistent update (O(log(n))). These data structures are someplace between a list and a vector, but have the benefit of persistence - update to a random-access-list returns a new list and leaves the old one unmodified. These are similar to Clojure's vector datatype.

You can read about these structures in srfi-101. My implementation is a cargo-cult port of the reference implementation of that srfi to Emacs Lisp.

Examples:

Creation:

(setq r (ra:list 1 2 3 4 5)) ; -> [cl-struct-pl-cons 1 1 [cl-struct-pl-cons 1 2 [cl-struct-pl-cons 3 [cl-struct-pl-node 3 4 5] nil]]]

List operations are prefixed with ra::

(ra:car r) ;-> 1
(ra:cdr r) ;-> [cl-struct-pl-cons 1 2 [cl-struct-pl-cons 3
[cl-struct-pl-node 3 4 5] nil]]
(ra:map (lambda (x) (+ x 1)) r) ;-> [cl-struct-pl-cons 1 2
[cl-struct-pl-cons 1 3 [cl-struct-pl-cons 3 [cl-struct-pl-node 4 5
6] nil]]]
(ra:cons 100 r) ; ->[cl-struct-pl-cons 3 [cl-struct-pl-node 100 1 2] [cl-struct-pl-cons 3 [cl-struct-pl-node 3 4 5] nil]]

And so on.

Random access and update are accomplished with:

(ra:list-ref r 1) ;-> 2
(ra:list-set r 1 1000) [cl-struct-pl-cons 1 1 [cl-struct-pl-cons 1
1000 [cl-struct-pl-cons 3 [cl-struct-pl-node 3 4 5] nil]]]

Note that indexing is zero based.

Once can convert between ra:lists and lists via:

(ra:random-access-list->linear-access-list r) ;-> (1 2 3 4 5)
(ra:linear-access-list->random-access-list '(1 2 3)) ;->
[cl-struct-pl-cons 3 [cl-struct-pl-node 1 2 3] nil]

Conclusion:

I wrote this library by porting over the reference implementation. There are many places where very large random access lists will blow the stack. There are also probably bugs and places where efficiency can be improved. Please let me know if you find any!

They are available from my github account.

---