Racket

Sek: Catenable, Splittable, Transient Sequences🔗ℹ

Sam Tobin-Hochstadt <samth@racket-lang.org>

package: sek-lib

An implementation of the sequence data structure of Charguéraud and Pottier [Chargueraud26].

This library provides efficient persistent sequences and ephemeral sequences, together with cheap conversions between the two. Both support random access, pushing and popping at either end, concatenation and splitting.

The conversions are what make the pair worth having together. Holding a persistent sequence, a program can pseq-edit it to obtain an ephemeral one, update that in place as often as it likes, and eseq-snapshot it to get a persistent sequence back. It pays neither for copying the sequence nor for persistent update while the sequence is being edited. That round trip is what the paper calls transience: the two are one representation, and a conversion changes which of them owns it rather than copying it.

1 Overview🔗ℹ

Examples:

> (define p (list->pseq '(1 2 3 4 5)))
> (pseq->list (pseq-push-front p 0))
'(0 1 2 3 4 5)
; p itself is unchanged
> (pseq->list p)
'(1 2 3 4 5)
; switch to in-place updates in O(1) ...
> (define e (pseq-edit p))
> (eseq-push-back! e 6)
> (eseq-set! e 0 'a)
; ... and back again, also in O(1)
> (define q (eseq-snapshot e))
> (pseq->list q)
'(a 2 3 4 5 6)
> (pseq->list p)
'(1 2 3 4 5)

2 Sequences🔗ℹ

A sequence is stored as a tree whose nodes hold arrays of up to K items, called chunks. Each level of the tree consists of a front chunk, a back chunk, and a middle sequence, which is itself a tree of the same shape one level down, holding chunks of the current level’s items. Because the two ends of the sequence live at the root, pushing and popping there is cheap; because the tree is balanced by a density invariant on the middle sequences, indexing, splitting and concatenation are logarithmic.

Throughout, N is the length of the sequence, K the chunk capacity, and T the threshold below which a persistent sequence is held in a plain vector. Unless otherwise specified, operations on a sequence of length N take O(logK N) time. As for treelists, the base of the log is large enough that it is effectively constant-time for many purposes: with the default K of 128 at the leaves, a sequence of a million elements is three levels deep.

3 Comparison with treelists🔗ℹ

Racket’s treelists solve a similar problem, and for most programs they are the better choice: they are in the core and they are simpler. Both structures support random access, concatenation and splitting in O(log N) time, with a base large enough that the logarithm is effectively a constant.

The two differ at the ends and in the conversions. Pushing or popping at either end of an ephemeral sequence is O(1) amortized, where the corresponding treelist operation takes O(log N) time.

Conversion is the larger difference. treelist-copy and mutable-treelist-snapshot each take O(N) time, so a program that moves between the immutable and mutable forms pays for the whole sequence at every switch. Here pseq-edit takes O(1) time and eseq-snapshot takes O(K logK N) time, so a loop can move back and forth. Likewise mutable-treelist-append! takes O(N) time in the length of its second argument, where eseq-append! does not.

Traversal is O(N) for both. This library also hands out segments, a run of the sequence’s own storage that a caller can process with a vector loop instead of one cursor step per element.

Treelists are RRB trees [Stucki15], which store one element per leaf slot. The sequences here store chunks of up to K elements and keep track of who owns each chunk. That is what makes the ends and the conversions cheap, and it is also where the K in the bounds above comes from.

3.1 Persistent sequences🔗ℹ

A persistent sequence is immutable: an operation on one produces a new sequence and leaves the original intact.

A persistent sequence can be used as a single-valued sequence, whose elements are the elements of the sequence; see also in-pseq. It can also be used as a stream, and it is serializable?. Two persistent sequences are equal? when their elements are.

procedure
(pseq? v) → boolean?
v : any/c

Returns #t if v is a persistent sequence, #f otherwise.

procedure
(pseq v ...) → pseq?
v : any/c

Returns a persistent sequence with vs as its elements in order.

Example:

> (pseq 1 "a" 'apple)
(pseq 1 "a" 'apple)

procedure
(pseq-empty? s) → boolean?
s : pseq?
value
empty-pseq : (and/c pseq? pseq-empty?)

A predicate and constant for a persistent sequence of length 0.

procedure
(pseq-length s) → exact-nonnegative-integer?
s : pseq?

Returns the number of elements in s. This operation takes O(1) time.

Example:

> (pseq-length (pseq 1 "a" 'apple))
3

procedure
(pseq-add s v) → pseq?
  s : pseq?
  v : any/c
procedure
(pseq-cons s v) → pseq?
  s : pseq?
  v : any/c
procedure
(pseq-push-back s v) → pseq?
  s : pseq?
  v : any/c
procedure
(pseq-push-front s v) → pseq?
  s : pseq?
  v : any/c

Return a persistent sequence with v added at the end, in the case of pseq-add, or at the front, in the case of pseq-cons – the same division of labor as treelist-add and treelist-cons. pseq-push-back and pseq-push-front are aliases for them, under the names the paper and the authors’ OCaml library use.

These take O(K logK N) time in the worst case, and O(1) time when the affected chunk admits a monotonic in-place update.

Examples:

> (define s (pseq 1 2 3))
> (pseq-cons s 0)
(pseq 0 1 2 3)
> (pseq-add s 4)
(pseq 1 2 3 4)
> s
(pseq 1 2 3)

procedure
(pseq-pop-front s) →
any/c pseq?
s : pseq?
procedure
(pseq-pop-back s) →
any/c pseq?
s : pseq?

Return the element at the given end and the rest of the sequence. These operations take O(logK N) time, or O(T) time when the result becomes short enough to switch to the compact representation. Raises exn:fail:contract if s is empty.

procedure
(pseq-first s) → any/c
s : pseq?
procedure
(pseq-last s) → any/c
s : pseq?

Shorthands for using pseq-ref to access the first or last element of a persistent sequence.

procedure
(pseq-ref s i) → any/c
  s : pseq?
  i : exact-nonnegative-integer?
procedure
(pseq-set s i v) → pseq?
  s : pseq?
  i : exact-nonnegative-integer?
  v : any/c

Returns the ith element of s, or a sequence with that element replaced by v. The first element is position 0, and the last position is one less than (pseq-length s).

These operations take O(K logK N) time in general, and O(logK N) time when every chunk on the path is packed, which is the case for any sequence built without concatenation.

Examples:

> (define s (list->pseq '(a b c d)))
> (pseq-ref s 2)
'c
> (pseq->list (pseq-set s 2 'C))
'(a b C d)
> (pseq->list s)
'(a b c d)

procedure
(pseq-append s1 s2) → pseq?
s1 : pseq?
s2 : pseq?

Returns a persistent sequence with the elements of s1 followed by those of s2, in O(K logK N + logK2 N).

Example:

> (pseq->list (pseq-append (pseq 1 2) (pseq 3 4)))
'(1 2 3 4)

procedure
(pseq-split s i) →
pseq? pseq?
s : pseq?
i : exact-nonnegative-integer?

Returns the first i elements and the rest, in O(K logK N + logK2 N).

Examples:

> (define-values (before after) (pseq-split (list->pseq '(a b c d e)) 2))
> (pseq->list before)
'(a b)
> (pseq->list after)
'(c d e)

procedure
(pseq-take s i) → pseq?
  s : pseq?
  i : exact-nonnegative-integer?
procedure
(pseq-drop s i) → pseq?
  s : pseq?
  i : exact-nonnegative-integer?

The two halves of pseq-split separately: the first i elements, or all but the first i. Same cost as pseq-split, and s is unchanged.

Examples:

> (define s (list->pseq '(a b c d e)))
> (pseq->list (pseq-take s 2))
'(a b)
> (pseq->list (pseq-drop s 2))
'(c d e)

procedure
(pseq->list s) → list?
  s : pseq?
procedure
(list->pseq xs) → pseq?
  xs : list?
procedure
(pseq->vector s) → vector?
  s : pseq?
procedure
(vector->pseq v) → pseq?
  v : vector?
procedure
(pseq-for-each s proc) → void?
  s : pseq?
  proc : (-> any/c any)
procedure
(pseq-map s proc) → pseq?
  s : pseq?
  proc : (-> any/c any/c)

Conversion and iteration. Each of these takes O(N) time. See in-pseq below for iterating in a for clause.

3.2 Ephemeral sequences🔗ℹ

An ephemeral sequence is updated in place. Where an operation on a persistent sequence returns a new sequence, the corresponding operation here modifies the sequence it is given and returns void.

An ephemeral sequence can be used as a single-valued sequence; see also in-eseq. It is serializable?, and two ephemeral sequences are equal? when their elements are. It is not a stream, for the same reason a mutable-treelist is not: a stream’s rest is a value, and this one is modified in place.

procedure
(eseq? v) → boolean?
v : any/c

Returns #t if v is an ephemeral sequence, #f otherwise.

procedure
(eseq v ...) → eseq?
v : any/c

Returns an ephemeral sequence with vs as its elements in order.

Example:

> (eseq 1 "a" 'apple)
(eseq 1 "a" 'apple)

procedure
(make-eseq [n v]) → eseq?
n : exact-nonnegative-integer? = 0
v : any/c = #f

Returns an ephemeral sequence of length n, where every element is v.

Examples:

> (make-eseq 0)
(eseq)
> (make-eseq 3 'pear)
(eseq 'pear 'pear 'pear)

procedure
(eseq-empty? e) → boolean?
e : eseq?

Returns #t if e has no elements, #f otherwise. This operation takes O(1) time.

procedure
(eseq-length e) → exact-nonnegative-integer?
e : eseq?

Returns the number of elements in e. This operation takes O(1) time.

Example:

> (eseq-length (eseq 1 "a" 'apple))
3

procedure
(eseq-add! e v) → void?
  e : eseq?
  v : any/c
procedure
(eseq-cons! e v) → void?
  e : eseq?
  v : any/c
procedure
(eseq-push-back! e v) → void?
  e : eseq?
  v : any/c
procedure
(eseq-push-front! e v) → void?
  e : eseq?
  v : any/c
procedure
(eseq-pop-back! e) → any/c
  e : eseq?
procedure
(eseq-pop-front! e) → any/c
  e : eseq?

Adds v at the end (eseq-add!) or the front (eseq-cons!) of e, or removes and returns the element at one of its ends, modifying e in place. eseq-push-back! and eseq-push-front! are aliases, under the names the paper uses.

These take amortized O(logK N) time even though the middle of the structure may contain chunks shared with snapshots, which is the paper’s main result. The bound rests on the two inner chunks held at the root, which stop an alternating series of pushes and pops from cascading down the tree on every operation.

Examples:

> (define items (eseq 1 2 3))
> (eseq-cons! items 0)
> (eseq-add! items 4)
> items
(eseq 0 1 2 3 4)
> (eseq-pop-front! items)
0
> (eseq-pop-back! items)
4
> items
(eseq 1 2 3)

procedure
(eseq-ref e i) → any/c
  e : eseq?
  i : exact-nonnegative-integer?
procedure
(eseq-set! e i v) → void?
  e : eseq?
  i : exact-nonnegative-integer?
  v : any/c

Returns the ith element of e, or replaces it with v. The first element is position 0, and the last position is one less than (eseq-length e).

eseq-set! takes O(K logK N) time, dropping to O(logK N) once the chunks along the path are uniquely owned, which is what makes a run of updates at nearby indices cheap.

Examples:

> (define items (eseq 1 "a" 'apple))
> (eseq-ref items 2)
'apple
> (eseq-set! items 2 'pear)
> items
(eseq 1 "a" 'pear)

procedure
(eseq-first e) → any/c
e : eseq?
procedure
(eseq-last e) → any/c
e : eseq?

Shorthands for using eseq-ref to access the first or last element of an ephemeral sequence.

The five operations that follow rearrange ephemeral sequences in place, and they consume the sequences they are given: each one is emptied. That is what the reference library does, and for a good reason – handing over a sequence’s representation instead of sharing it keeps later updates out of the copy-on-write path. Use sek-take, sek-drop and sek-sub when the input must survive.

procedure
(eseq-append! e other [side]) → void?
  e : eseq?
  other : (or/c eseq? pseq?)
  side : (or/c 'front 'back) = 'back

Appends the contents of other to e, in place, at the given end. An ephemeral other is emptied; a persistent one is of course untouched. The two sequences must be distinct.

procedure
(eseq-concat! e1 e2) → eseq?
e1 : eseq?
e2 : eseq?

Returns a new sequence holding the concatenation, and empties both arguments, which must be distinct.

procedure
(eseq-split! e i) →
eseq? eseq?
e : eseq?
i : exact-nonnegative-integer?

Returns two new sequences holding the first i elements and the rest, and empties e.

procedure
(eseq-carve! e i [side]) → eseq?
  e : eseq?
  i : exact-nonnegative-integer?
  side : (or/c 'front 'back) = 'back

Splits e at i, keeping one part in e and returning the other: 'back keeps the front part, 'front keeps the back part. Cheaper than eseq-split! when one part is going back into the same variable.

procedure
(eseq-take! e i [side]) → void?
  e : eseq?
  i : exact-nonnegative-integer?
  side : (or/c 'front 'back) = 'front
procedure
(eseq-drop! e i [side]) → void?
  e : eseq?
  i : exact-nonnegative-integer?
  side : (or/c 'front 'back) = 'front

Truncate e at index i. eseq-take! keeps the front part when side is 'front and the back part otherwise; eseq-drop! keeps the other one.

procedure
(eseq-clear! e) → void?
e : eseq?

Empties e.

procedure
(eseq-assign! e1 e2) → void?
e1 : eseq?
e2 : eseq?

Moves the contents of e2 into e1 and empties e2. Does nothing if the two are the same sequence.

procedure
(eseq->list e) → list?
  e : eseq?
procedure
(list->eseq xs) → eseq?
  xs : list?
procedure
(eseq->vector e) → vector?
  e : eseq?
procedure
(eseq-for-each e proc) → void?
  e : eseq?
  proc : (-> any/c any)

Conversion and iteration. Each of these takes O(N) time. See in-eseq below for iterating in a for clause.

3.3 Converting between the two flavors🔗ℹ

procedure
(eseq-snapshot e) → pseq?
e : eseq?

Returns a persistent sequence with the current contents of e. e remains usable and keeps its contents; later updates to it do not affect the snapshot.

This operation takes O(K logK N) time in the worst case: the two inner chunks are folded into the middle sequence first, and only then does the conversion install a fresh ownership identifier on e, which makes every chunk in the structure stop being recognizable as uniquely owned and so silently immutable. The cost of re-acquiring ownership is paid later, and only for the chunks that are actually written. Compare mutable-treelist-snapshot, which takes O(N) time.

Examples:

> (define e (list->eseq '(1 2 3)))
> (define snap (eseq-snapshot e))
> (eseq-push-back! e 4)
> (eseq->list e)
'(1 2 3 4)
; the snapshot does not see the push
> (pseq->list snap)
'(1 2 3)

procedure
(pseq-edit s) → eseq?
s : pseq?

Returns an ephemeral sequence with the contents of s, sharing its representation. s is unaffected by later updates to the result.

This operation takes O(1) time: the front and back chunks are shared rather than copied, and a chunk is copied only on the first write to it. Compare treelist-copy, which takes O(N) time.

Examples:

> (define s (pseq 1 2 3))
> (define e (pseq-edit s))
> (eseq-set! e 0 'changed)
> (eseq->list e)
'(changed 2 3)
> (pseq->list s)
'(1 2 3)

procedure
(eseq-snapshot-and-clear! e) → pseq?
e : eseq?

Takes the snapshot and empties e. Because nothing is left sharing chunks with the result, later updates to e never pay for copy-on-write; this is the cheaper operation when the old contents are not needed.

procedure
(eseq-copy e [#:mode mode]) → eseq?
e : eseq?
mode : (or/c 'share 'copy) = 'share

An independent ephemeral copy of e. In 'share mode the two sequences start out sharing everything and are separated lazily by whichever one writes first, which is O(1) now and makes the next update to either sequence more expensive; in 'copy mode the elements are copied up front, which costs O(N) and leaves no latent cost.

4 Iterators🔗ℹ

An iterator is a cursor into a sequence. Its position is an integer in [-1, N]: the indices in [0, N) designate elements, and the two extremes are sentinels, one just before the sequence and one just after. An iterator that sits on a sentinel is sek-iter-finished?.

Moving one step costs O(1) as long as the iterator stays inside one run of contiguous storage, which is the common case; crossing a chunk or a level of the tree costs more, but happens only once every K elements. This is what makes a full traversal O(N) where repeated pseq-ref would be O(N logK N).

Iterating an ephemeral sequence is guarded: any update to the sequence invalidates every iterator on it, and using an invalidated iterator raises an exception instead of quietly reading stale storage. The check can be turned off with sek-configure!, at which point using an invalidated iterator is undefined. Iterators on persistent sequences are never invalidated.

procedure
(sek-iterator s [dir]) → sek-iter?
s : (or/c pseq? eseq?)
dir : (or/c 'forward 'backward) = 'forward

An iterator on the first element of s, or on the last one if dir is 'backward. On an empty sequence the result is already finished.

procedure
(sek-iterator-at-sentinel s [side]) → sek-iter?
s : (or/c pseq? eseq?)
side : (or/c 'front 'back) = 'front

An iterator on the sentinel just before (or just after) the sequence.

procedure
(sek-iter? v) → boolean?
v : any/c

Returns #t if v is an iterator, #f otherwise.

procedure
(sek-iter-sequence it) → (or/c pseq? eseq?)
  it : sek-iter?
procedure
(sek-iter-length it) → exact-nonnegative-integer?
  it : sek-iter?
procedure
(sek-iter-index it) → exact-integer?
  it : sek-iter?
procedure
(sek-iter-finished? it) → boolean?
  it : sek-iter?
procedure
(sek-iter-valid? it) → boolean?
  it : sek-iter?

The sequence an iterator was made from, its length, the iterator’s current position, whether that position is a sentinel, and whether the iterator is still usable. All O(1).

procedure
(sek-iter-get it) → any/c
it : sek-iter?
procedure
(sek-iter-get* it) → any/c
it : sek-iter?

The element under the iterator. sek-iter-get raises an exception at a sentinel; sek-iter-get* returns #f there. O(1).

Throughout this section, a name ending in * is the variant that returns #f at a sentinel instead of raising – which is usually what a traversal loop wants, since reaching a sentinel is how it ends.

procedure
(sek-iter-move! it [dir]) → void?
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-get-and-move! it [dir]) → any/c
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-get-and-move*! it [dir]) → any/c
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward

Step one element. Moving off the far sentinel raises an exception. O(1) amortized.

procedure
(sek-iter-jump! it dir n) → void?
  it : sek-iter?
  dir : (or/c 'forward 'backward)
  n : exact-nonnegative-integer?
procedure
(sek-iter-reach! it i) → void?
  it : sek-iter?
  i : exact-integer?

Move by n elements, or to index i, which may be -1 or the length of the sequence. A jump that stays inside the current run is O(1); otherwise the cost is that of an index lookup.

procedure
(sek-iter-copy it) → sek-iter?
  it : sek-iter?
procedure
(sek-iter-reset! it [dir]) → void?
  it : sek-iter?
  dir : (or/c 'forward 'backward 'sentinel) = 'forward

sek-iter-copy duplicates an iterator, so that the two move independently. sek-iter-reset! puts an iterator back where a freshly created one would be, which is also how an iterator that was invalidated by an update is made usable again.

procedure
(sek-iter-check it) → sek-iter?
it : sek-iter?

Check the iterator’s internal invariants and return it. For testing.

4.1 Segments🔗ℹ

A segment is a run of contiguous storage inside the sequence: a vector, a start index and a length. An iterator can hand out the whole run it is sitting on, which lets a caller process K elements with a tight vector loop instead of K iterator steps. This is how sek-fold-left and the rest of the derived operations are implemented.

A segment is a view into the sequence, not a copy. It is valid only as long as the iterator that produced it is, and writing through one writes into the sequence.

procedure
(sek-iter-segment it [dir]) → segment?
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-segment* it [dir]) → (or/c segment? #f)
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-segment-and-jump! it [dir]) → segment?
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-segment-and-jump*! it [dir]) → (or/c segment? #f)
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward

The elements from the current position to the end of the run, in the given direction. Note that a backward segment still lists its elements in sequence order; it is the elements at and before the cursor. sek-iter-segment-and-jump! additionally moves the iterator past the segment, which is how a traversal advances run by run.

procedure
(segment v start len) → segment?
  v : vector?
  start : exact-nonnegative-integer?
  len : exact-nonnegative-integer?
procedure
(segment? v) → boolean?
  v : any/c
procedure
(segment-valid? s) → boolean?
  s : any/c
procedure
(segment-vector s) → vector?
  s : segment?
procedure
(segment-start s) → exact-nonnegative-integer?
  s : segment?
procedure
(segment-length s) → exact-nonnegative-integer?
  s : segment?
procedure
(segment-empty? s) → boolean?
  s : segment?
procedure
(segment-ref s i) → any/c
  s : segment?
  i : exact-nonnegative-integer?
procedure
(segment-set! s i v) → void?
  s : segment?
  i : exact-nonnegative-integer?
  v : any/c
procedure
(segment-for-each s proc [dir]) → void?
  s : segment?
  proc : (-> any/c any)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(segment-for-each2 s1 s2 proc [dir]) → void?
  s1 : segment?
  s2 : segment?
  proc : (-> any/c any/c any)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(in-segment s) → sequence?
  s : segment?
procedure
(segment->list s) → list?
  s : segment?
procedure
(segment->vector s) → vector?
  s : segment?

Segments and their accessors.

4.2 Writing through an iterator🔗ℹ

procedure
(sek-iter-set! it v) → void?
  it : sek-iter?
  v : any/c
procedure
(sek-iter-set-and-move! it v [dir]) → void?
  it : sek-iter?
  v : any/c
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-writable-segment it [dir]) → segment?
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-writable-segment* it [dir]) → (or/c segment? #f)
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-writable-segment-and-jump! it
[ dir]) → segment?
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-iter-writable-segment-and-jump*! it
[ dir]) → (or/c segment? #f)
  it : sek-iter?
  dir : (or/c 'forward 'backward) = 'forward

Write at the iterator’s position, or obtain a segment that may be written through. Both require an iterator on an ephemeral sequence, and both invalidate every other iterator on that sequence.

The first write into a chunk that is shared with some snapshot costs O(K logK N), because the chunk has to be copied and the iterator rebuilt; after that, writes into the same chunk are O(1). A sweep that writes every element therefore costs O(N + K logK N) rather than one tree descent per element.

5 Operations on either flavor🔗ℹ

The operations in this section accept a persistent or an ephemeral sequence. Those that build a new sequence return the same flavor they were given, which is how the OCaml library’s two parallel modules are collapsed into one set of names here.

procedure
(sek? v) → boolean?
  v : any/c
procedure
(sek-length s) → exact-nonnegative-integer?
  s : sek?
procedure
(sek-empty? s) → boolean?
  s : sek?
procedure
(sek-ref s i) → any/c
  s : sek?
  i : exact-nonnegative-integer?
procedure
(sek-first s) → any/c
  s : sek?
procedure
(sek-last s) → any/c
  s : sek?

Basic accessors, dispatching on the flavor.

5.1 Traversal🔗ℹ

syntax
(in-sek s)
(in-sek s dir)
syntax
(in-pseq s)
(in-pseq s dir)
syntax
(in-eseq e)
(in-eseq e dir)

Sequences over the elements, in 'forward order by default. Written directly in a for clause these expand to a loop over the sequence’s own storage, so a step is a vector reference and an increment; used as ordinary values they fall back to a checked iterator. Either way, modifying an ephemeral sequence during the loop is detected rather than silently producing nonsense.

procedure
(sek-for-each s proc [dir]) → void?
  s : sek?
  proc : (-> any/c any)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-for-each/index s proc [dir]) → void?
  s : sek?
  proc : (-> exact-nonnegative-integer? any/c any)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-segments-for-each s proc [dir]) → void?
  s : sek?
  proc : (-> segment? any)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-segments-for-each2 s1 s2 proc [dir]) → void?
  s1 : sek?
  s2 : sek?
  proc : (-> segment? segment? any)
  dir : (or/c 'forward 'backward) = 'forward

Apply proc to each element, to each index and element, or to each run of contiguous storage. The last is the fastest way to sweep a sequence and is what the others are built on.

procedure
(sek-fold-left s proc init) → any/c
  s : sek?
  proc : (-> any/c any/c any/c)
  init : any/c
procedure
(sek-fold-right s proc init) → any/c
  s : sek?
  proc : (-> any/c any/c any/c)
  init : any/c

Fold from the left or from the right. These operations take O(N) time.

procedure
(sek->list s [dir]) → list?
  s : sek?
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek->vector s) → vector?
  s : sek?

Conversions.

5.2 Searching🔗ℹ

procedure
(sek-find s pred [dir]) → any/c
  s : sek?
  pred : (-> any/c any/c)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-find-index s pred [dir])
→ (or/c exact-nonnegative-integer? #f)
  s : sek?
  pred : (-> any/c any/c)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-find-map s proc [dir]) → any/c
  s : sek?
  proc : (-> any/c any/c)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-for-all? s pred) → boolean?
  s : sek?
  pred : (-> any/c any/c)
procedure
(sek-exists? s pred) → boolean?
  s : sek?
  pred : (-> any/c any/c)
procedure
(sek-member? s v [same?]) → boolean?
  s : sek?
  v : any/c
  same? : (-> any/c any/c any/c) = equal?
procedure
(sek-memq? s v) → boolean?
  s : sek?
  v : any/c

Search operations, all of which stop as soon as they can. sek-find returns #f when nothing matches, so use sek-find-index when an element could itself be #f.

5.3 Building new sequences🔗ℹ

procedure
(sek-map s proc) → sek?
  s : sek?
  proc : (-> any/c any/c)
procedure
(sek-map/index s proc) → sek?
  s : sek?
  proc : (-> exact-nonnegative-integer? any/c any/c)
procedure
(sek-filter s pred) → sek?
  s : sek?
  pred : (-> any/c any/c)
procedure
(sek-filter-map s proc) → sek?
  s : sek?
  proc : (-> any/c any/c)
procedure
(sek-partition s pred) →
sek? sek?
  s : sek?
  pred : (-> any/c any/c)
procedure
(sek-reverse s) → sek?
  s : sek?
procedure
(sek-append* s) → sek?
  s : sek?
procedure
(sek-append-map s proc) → sek?
  s : sek?
  proc : (-> any/c sek?)

The usual list-shaped operations, each O(N) plus the cost of proc. sek-append* concatenates a sequence of sequences; given an ephemeral one it empties both it and its elements, as the reference library’s flatten does, because it hands over each sequence’s representation rather than copying its elements.

procedure
(sek-sub s start size) → sek?
  s : sek?
  start : exact-nonnegative-integer?
  size : exact-nonnegative-integer?
procedure
(sek-take s n) → sek?
  s : sek?
  n : exact-nonnegative-integer?
procedure
(sek-drop s n) → sek?
  s : sek?
  n : exact-nonnegative-integer?
procedure
(sek-copy s [#:mode mode]) → sek?
  s : sek?
  mode : (or/c 'share 'copy) = 'share

sek-sub extracts a slice in O(size + K), which beats splitting when the slice is short; sek-take and sek-drop split instead, in O(K logK N + logK2 N). None of them modifies s. sek-copy is the identity on a persistent sequence.

procedure
(sek-take-right s n) → sek?
  s : sek?
  n : exact-nonnegative-integer?
procedure
(sek-drop-right s n) → sek?
  s : sek?
  n : exact-nonnegative-integer?

Produce a sequence like s but with only the last n elements, or without the last n elements, respectively. They cost what sek-take and sek-drop cost, and neither modifies s.

Examples:

> (sek-take-right (pseq 1 2 3 4 5) 2)
(pseq 4 5)
> (sek-drop-right (pseq 1 2 3 4 5) 2)
(pseq 1 2 3)

procedure
(sek-insert s i v) → sek?
  s : sek?
  i : exact-nonnegative-integer?
  v : any/c
procedure
(sek-delete s i) → sek?
  s : sek?
  i : exact-nonnegative-integer?

Produce a sequence like s, except that v is inserted before the element at i, or that the element at i is removed. If i is (sek-length s) then sek-insert adds v at the end.

Each goes through a split and a concatenation rather than rebuilding the sequence, so each takes O(K logK N + logK2 N) time. Neither modifies s.

Examples:

> (sek-insert (pseq 1 2 3) 1 'x)
(pseq 1 'x 2 3)
> (sek-insert (pseq 1 2 3) 3 'x)
(pseq 1 2 3 'x)
> (sek-delete (pseq 1 2 3) 1)
(pseq 1 3)

procedure
(sek-index-of s v [same?]) → (or/c exact-nonnegative-integer? #f)
  s : sek?
  v : any/c
  same? : (-> any/c any/c any/c) = equal?

Returns the index of the first element of s that is same? to v, or #f if there is none. same? receives v first and the element second.

Examples:

> (sek-index-of (pseq 'a 'b 'c) 'b)
1
> (sek-index-of (pseq 'a 'b 'c) 'z)
#f

5.4 Ordering🔗ℹ

procedure
(sek-sort s less?) → sek?
  s : sek?
  less? : (-> any/c any/c any/c)
procedure
(sek-uniq s [same?]) → sek?
  s : sek?
  same? : (-> any/c any/c any/c) = equal?
procedure
(sek-merge s1 s2 less?) → sek?
  s1 : sek?
  s2 : sek?
  less? : (-> any/c any/c any/c)

A stable sort, which takes O(N log N) time; removal of adjacent duplicates, which removes all duplicates from a sorted sequence; and a stable merge of two sorted sequences.

5.5 Two sequences at once🔗ℹ

procedure
(sek-for-each2 s1 s2 proc [dir]) → void?
  s1 : sek?
  s2 : sek?
  proc : (-> any/c any/c any)
  dir : (or/c 'forward 'backward) = 'forward
procedure
(sek-fold-left2 s1 s2 proc init) → any/c
  s1 : sek?
  s2 : sek?
  proc : (-> any/c any/c any/c any/c)
  init : any/c
procedure
(sek-fold-right2 s1 s2 proc init) → any/c
  s1 : sek?
  s2 : sek?
  proc : (-> any/c any/c any/c any/c)
  init : any/c
procedure
(sek-map2 s1 s2 proc) → sek?
  s1 : sek?
  s2 : sek?
  proc : (-> any/c any/c any/c)
procedure
(sek-zip s1 s2) → sek?
  s1 : sek?
  s2 : sek?
procedure
(sek-unzip s) →
sek? sek?
  s : sek?
procedure
(sek-for-all2? s1 s2 pred) → boolean?
  s1 : sek?
  s2 : sek?
  pred : (-> any/c any/c any/c)
procedure
(sek-exists2? s1 s2 pred) → boolean?
  s1 : sek?
  s2 : sek?
  pred : (-> any/c any/c any/c)
procedure
(sek-equal? s1 s2 [same?]) → boolean?
  s1 : sek?
  s2 : sek?
  same? : (-> any/c any/c any/c) = equal?
procedure
(sek-compare s1 s2 cmp) → (or/c -1 0 1)
  s1 : sek?
  s2 : sek?
  cmp : (-> any/c any/c real?)

Binary operations. They stop at the end of the shorter sequence, except sek-equal?, which first compares lengths, and sek-compare, which orders a proper prefix before the sequence that extends it. sek-zip pairs elements with cons; sek-unzip undoes it.

5.6 Bulk writes🔗ℹ

procedure
(sek-fill! e start size v) → void?
  e : eseq?
  start : exact-nonnegative-integer?
  size : exact-nonnegative-integer?
  v : any/c
procedure
(sek-blit! src src-start dst dst-start size) → void?
  src : sek?
  src-start : exact-nonnegative-integer?
  dst : eseq?
  dst-start : exact-nonnegative-integer?
  size : exact-nonnegative-integer?

Overwrite a range with one value, or copy a range from one sequence into another. Both go through writable segments, so they cost O(size + K logK N) rather than one tree descent per element. sek-blit! handles the case where src and dst are the same sequence and the ranges overlap.

5.7 Construction🔗ℹ

procedure
(build-pseq n proc) → pseq?
  n : exact-nonnegative-integer?
  proc : (-> exact-nonnegative-integer? any/c)
procedure
(build-eseq n proc) → eseq?
  n : exact-nonnegative-integer?
  proc : (-> exact-nonnegative-integer? any/c)
procedure
(make-pseq n [v]) → pseq?
  n : exact-nonnegative-integer?
  v : any/c = #f
procedure
(sequence->pseq s [n]) → pseq?
  s : sequence?
  n : (or/c exact-nonnegative-integer? #f) = #f
procedure
(sequence->eseq s [n]) → eseq?
  s : sequence?
  n : (or/c exact-nonnegative-integer? #f) = #f
syntax
(for/eseq (for-clause ...) body ...+)
syntax
(for*/eseq (for-clause ...) body ...+)
syntax
(for/pseq (for-clause ...) body ...+)
syntax
(for*/pseq (for-clause ...) body ...+)

Build a sequence of n elements, or from the elements of any Racket sequence, or from the results of a comprehension, in O(N + K). See also make-eseq, which takes the same arguments as make-vector.

6 Configuration🔗ℹ

procedure
(sek-configure! #:leaf-capacity k0
#:node-capacity k1
#:short-threshold t
#:overwrite-empty-slots? overwrite?
#:check-iterator-validity? check?) → void?
  k0 : (and/c exact-integer? (>=/c 2))
  k1 : (and/c exact-integer? (>=/c 2))
  t : exact-nonnegative-integer?
  overwrite? : any/c
  check? : any/c

Set the tunable parameters of the implementation. Any argument that is not supplied is left as it is.

k0 and k1 are the chunk capacities used at the leaves and at internal nodes, and t is the length below which a persistent sequence is represented by a plain vector. The defaults are 128, 16 and 32.

overwrite? controls whether a slot that becomes logically empty is overwritten. Leaving it alone saves one write per pop but lets the garbage collector retain a value that the sequence no longer holds; overwriting is the default.

check? controls whether the use of an invalidated iterator is detected at runtime. Detection costs a comparison per iterator operation and a sign test per update, and is on by default; with it off, using an invalidated iterator is undefined rather than an error.

Call the capacity and threshold settings before building any sequences: a structure whose chunks were allocated under different settings will not satisfy the invariants that sek-validate-pseq checks, and its density bounds no longer hold. Small capacities are chiefly useful for testing, where they force deep trees.

7 Validation🔗ℹ

procedure
(sek-validate-pseq s) → pseq?
s : pseq?
procedure
(sek-validate-eseq e) → eseq?
e : eseq?

Check the structural invariants of a sequence and return it, raising an exception describing the first violation found. This is the runtime validation function of Appendix A; the test suite calls it after every operation. It costs O(N) and is meant for testing, not production use.

8 Implementation notes🔗ℹ

The paths that every push, pop and indexed access goes through use racket/unsafe/ops. Each use rests on an invariant the library maintains: a chunk’s backing vector is allocated here and never impersonated; an index into it is always reduced modulo the capacity, so it is in range; and heads, sizes and weights are bounded by a vector length or a sequence length, so they are fixnums. The runtime validator checks the first two after every operation in the test suite, and the conformance harness runs the same operations against the reference implementation.

An ephemeral sequence does not allocate its front and back chunks until the first push to that side. Figure 16 gives the cost of creating one as O(N + K), the K being those two arrays; deferring them makes creation O(1) without making anything else slower, since the first push allocates exactly the chunk it needs. It is worth having when a program makes many short-lived sequences – though for that use a growable vector is still the better tool, because a chunk of capacity K is a lot of storage for a ten-element sequence.

9 Differences from the paper🔗ℹ

This library follows the paper, and where the paper is silent, the authors’ OCaml library Sek.

Agreement with the reference is checked by running both implementations on the same generated script and comparing the traces: the result of every operation and the full contents of a dozen sequences after each one. The harness, the operation-by-operation mapping between the two APIs, and what has been checked are all in the conformance directory. The remaining differences are these.

Sequences are parameterized by neither an element type nor a default value. Logically empty slots are filled with a private sentinel instead, which removes the default argument that the OCaml library has to thread through every constructor.
The two flavors are one set of names rather than two parallel modules: an operation that builds a sequence returns the same flavor it was given.
sek-sort is stable, so it covers stable_sort too; sort makes no such promise.
The iterator supports the operations of the OCaml library’s ITER and ITER_EPHEMERAL signatures. sek-iter-reach! reuses the cursor’s position when the target lies in the run or the chunk it is already on, which is what makes a scan with short hops cheap, but descends from the root when the target is in a different chunk, where the reference can sometimes continue from the middle-sequence cursor.
pseq-edit and eseq-snapshot share the front and back chunks instead of copying them, where the OCaml library’s copy. A chunk is copied on the first write to it, if there is one, which makes pseq-edit take O(1) time rather than O(K). This is observationally identical and measurably better: a loop that snapshots after every push runs ten times faster, because the next push usually extends a chunk monotonically and copies nothing.
A #:short-threshold of 0 is supported here; the reference rejects it, because it still builds a compact node for a two-element sequence and its own validator then refuses that node.
The paper’s One and Short constructors for short persistent sequences are unified into a single vector representation, and appear only at the top of the structure, as in the authors’ implementation.
eseq-snapshot folds the two inner chunks into the middle sequence, as the OCaml library does, so it costs O(K logK N) in the worst case rather than the O(1) of Figure 16.
Like the paper’s implementation, monotonic in-place updates make the persistent flavor unsafe to share across threads without synchronization.

Bibliography🔗ℹ

[Chargueraud26]		Arthur Charguéraud and François Pottier, “A Catenable, Splittable, Transient Sequence Data Structure,” International Conference on Functional Programming, 2026. https://doi.org/10.1145/3828706
[Stucki15]		Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell, “RRB Vector: A Practical General Purpose Immutable Sequence,” International Conference on Functional Programming, 2015. https://dl.acm.org/doi/abs/10.1145/2784731.2784739

1	Overview
2	Sequences
3	Comparison with treelists
4	Iterators
5	Operations on either flavor
6	Configuration
7	Validation
8	Implementation notes
9	Differences from the paper
	Bibliography