Sek: a new sequence data structure

Show & Tell
1

I'm excited to announce Sek: Catenable, Splittable, Transient Sequences

It's an implementation of a new ICFP paper by Arthur Charguéraud and François Pottier.

You can install it with raco pkg install sek and then use (require sek) to get the whole thing. The implementation is at https://github.com/samth/racket-sek.

Like Racket's treelist and mutable-treelist, it's implemented as a wide tree, but it has a few interesting properties, such as being faster on the front and back, because the tree is deeper in the middle. But the most interesting feature is that it supports "transient" operation, as seen previously in Clojure. This allows the data structure to switch back and forth between mutable and immutable versions efficiently, so that you can make a sequence of updates much more efficiently than with traditional immutable data structures.

Using transience works like this:

(require sek)

(define N 10000000)
(define s1 (build-psek N values))

(define increment1
  (for/fold ([s s1]) ([i (in-range N)])
    (psek-set s i (add1 (psek-ref s i)))))

(define increment2
  (let ([e (psek-edit s1)])
    (for ([i (in-range N)])
      (esek-set! e i (add1 (esek-ref e i))))
    (esek-snapshot e)))

The advantage is that on my machine, increment1 takes about 1.2 seconds and increment2 takes about .4 seconds.

There are lots of other optimizations inside, most of which are due to the paper, but some of which are Racket-specific. As a result, sek is competitive with, and often faster than, other simpler data structures like treelists. Additionally, even though the underlying persistent data structure uses mutation internally, the library is comparably thread-safe to other sequences -- persistent psek use should not notice mutation even in the presence of threads, and esek will remain memory safe even when used without locking.

A note on development: while I was watching François' talk at ICFP, I was immediately jealous that OCaml had this cool library and we didn't. I then asked Claude Code to implement it, using the paper as a reference. The result mostly worked, but was not nearly up to the standards of Racket. Subsequently, I've substantially improved it in conjunction with Claude Code, producing the results now shown.

5 Likes