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].

The Sek 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.

Conversions between these two flavors are cheap: pseq-edit produces an ephemeral sequence in constant time, and eseq-snapshot produces a persistent sequence in logarithmic time. In contrast, snapshotting and editing other data structures typically takes linear time relative to the size of the data.

This approach is called transience, following terminology originally developed in Clojure.

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) time
> (define e (pseq-edit p))
> (eseq-push-back! e 6)
> (eseq-set! e 0 'a)
; and back again
> (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 a finite ordered collection of elements, in either of two flavors: a persistent sequence is immutable, and an ephemeral sequence is updated in place. A sequence stores its elements in chunks of up to K elements.

Throughout this manual, N is the length of the sequence, K the chunk capacity (by default 128 at the leaves and 16 at internal nodes), and T the length up to which a persistent sequence is held in a plain vector. Unless otherwise specified, operations on a sequence of length N take O(log_K N) time. As with treelists, the base of the log is large enough that it is effectively constant-time for many purposes: with the default settings, a sequence of up to a hundred million elements is at most six levels deep.

2.1 Comparison with treelists🔗ℹ

Racket’s treelists solve a similar problem—efficient, persistent data structures with fast indexing, implemented using wide trees. 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.

Sequences from this library are more efficient at the beginning and the end. Most pushes and pops at either end take O(1) time, for either flavor (see pseq-add for when a persistent push costs O(K)). In the worst case a push takes O(K log_K N) time and a pop O(log_K N), and a series of pushes and pops on an ephemeral sequence takes amortized O(log_K N) time per operation. The corresponding treelist operations take O(log N) time.

Conversions are cheaper too. treelist-copy and mutable-treelist-snapshot each take O(N) time, where pseq-edit takes O(1) and eseq-snapshot O(K log_K N). Likewise mutable-treelist-append! takes O(N) time in the length of its second argument, where eseq-append! takes O(K log_K N + log_K² N).

Traversal is O(N) for both. This library also provides segments, which give a caller the elements a run at a time.

2.2 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.

Adding elements to the same persistent sequence from several threads at once requires synchronization.

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 (pseq-add) or at the front (pseq-cons). pseq-push-back and pseq-push-front are aliases for these operations, following the names in the paper.

These take O(K log_K N) time in the worst case. Most take O(1) time, or O(K) time if s has already had an element added at that end or is the result of removing one from it.

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(log_K N) time in the worst case, and most take O(1); they take O(T) time when the result has at most T elements. 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).

pseq-ref takes O(K log_K N) time in general, and O(log_K N) time for a sequence built without concatenation. pseq-set takes O(K log_K N) time.

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 log_K N + log_K² 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 log_K N + log_K² 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.

2.3 Ephemeral sequences🔗ℹ

An ephemeral sequence changes 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.

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 for these operations, following the names in the paper.

In the worst case a push takes O(K log_K N) time and a pop O(log_K N). A series of pushes and pops takes amortized O(log_K N) time per operation, and most take O(1).

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-ref takes O(K log_K N) time in general, and O(log_K N) time for a sequence built without concatenation. eseq-set! takes O(K log_K N) time. For a sequence built without concatenation it takes O(log_K N), except that after a snapshot or an edit the first update near each index costs the full O(K log_K N).

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, leaving each empty. 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. This empties an ephemeral other and leaves a persistent one 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.

procedure
(eseq-fill! e v [start end]) → void?
  e : eseq?
  v : any/c
  start : exact-nonnegative-integer? = 0
  end : exact-nonnegative-integer? = (eseq-length e)
procedure
(eseq-copy! dst
dst-start
src
[ src-start
src-end]) → void?
  dst : eseq?
  dst-start : exact-nonnegative-integer?
  src : sek?
  src-start : exact-nonnegative-integer? = 0
  src-end : exact-nonnegative-integer? = (sek-length src)

Change the elements of an ephemeral sequence in place: eseq-fill! sets those from start to end to v, and eseq-copy! sets those starting at dst-start to match the elements of src from src-start to src-end. They take the same arguments in the same order as vector-fill! and vector-copy!.

src may be of either flavor; only the destination is modified. eseq-copy! handles the case where src and dst are the same sequence and the ranges overlap.

For a sequence built without concatenation, both cost O(size + K log_K N) time, even after a snapshot, and O((size + K) log_K N) in general.

Examples:

> (define items (eseq 1 2 3 4 5))
> (eseq-fill! items 'x 1 3)
> items
(eseq 1 'x 'x 4 5)
> (eseq-copy! items 0 (pseq 'a 'b))
> items
(eseq 'a 'b 'x 4 5)

2.4 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 log_K N) time in the worst case. Later updates to e may cost more than they otherwise would.

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. s is unaffected by later updates to the result.

This operation takes O(1) 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?

Returns a snapshot of e and empties e. Unlike eseq-snapshot, it does not make later updates to e more expensive.

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

An independent ephemeral copy of e. 'copy mode, the default, costs O(N) and leaves no later cost. 'share mode costs O(1) but makes later updates to either sequence more expensive, e included.

3 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) amortized and O(log_K N) in the worst case, so a full traversal costs O(N), where repeated pseq-ref pays for a lookup at every element.

Iterating an ephemeral sequence is checked: any update to the sequence invalidates every iterator on it, and using an invalidated iterator raises an exception. sek-configure! turns the check off, after which 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.

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. Reaching -1 or the length, or a position inside the current run, is O(1); any other move costs at most as much as sek-ref.

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.

3.1 Segments🔗ℹ

A segment is a run of up to K consecutive elements of a sequence, given as a vector, a start index and a length. An iterator can return the run it is on as a segment.

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.

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.

3.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 writable segment. 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 a snapshot costs O(K log_K N) in the worst case, and later writes into the same chunk cost O(1). For a sequence built without concatenation, a sweep that writes every element costs O(N + K log_K N), even after a snapshot.

4 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.

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.

4.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. They are fastest written directly in a for clause. Updating an ephemeral sequence during the loop is detected, as for an iterator.

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 first two call proc N times; the last two call it O(N/K) times, once per run.

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.

4.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.

4.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.

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) = 'copy

sek-take and sek-drop take O(K log_K N + log_K² N) time. So does sek-sub on a persistent sequence; on an ephemeral sequence it copies the slice instead, in O(size + K log_K N) time, which does not make later updates to s more expensive. None of them modifies s. sek-copy is the identity on a persistent sequence and eseq-copy on an ephemeral one.

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 takes O(K log_K N + log_K² N) time, and 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

4.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; a pass that drops adjacent duplicates, and so drops every duplicate from a sorted sequence; and a stable merge of two sorted sequences.

4.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.

4.6 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.

5 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. An argument you do not supply keeps its current value.

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

overwrite? controls whether popping from an ephemeral sequence overwrites the slot it empties. 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. Popping from a persistent sequence never overwrites, so the popped value stays reachable for as long as the result does.

check? controls whether the library detects the use of an invalidated iterator at runtime. The check is on by default; with it off, using an invalidated iterator is undefined rather than an error.

Set the capacities and the threshold before building any sequences: a sequence built under other settings fails sek-validate-pseq and does not meet the bounds given here. Small capacities are useful mainly for testing.

6 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 paper’s runtime validation function. It costs O(N) and is meant for testing, not production use.

7 Differences from the paper🔗ℹ

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

The conformance directory holds a harness that checks this library against the OCaml library on generated scripts, the operation-by-operation mapping between the two APIs, and a record of what has been checked. The differences are these.

No operation takes a default value, where every constructor in the OCaml library does.
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.
sek-sub on a persistent sequence always shares the sequence’s chunks, where the OCaml library copies a slice of at most T elements.
pseq-edit takes O(1) time, and so does eseq-copy in 'share mode, where the OCaml library’s versions take O(K).
The settings are global and are changed at run time with sek-configure!, where the OCaml library fixes them when its functor Make is applied. The chunk capacity takes one value for the leaves and one for every level above them, where the OCaml library takes a function of the depth.
This library supports a #:short-threshold of 0, which the OCaml library rejects.

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	Iterators
4	Operations on either flavor
5	Configuration
6	Validation
7	Differences from the paper
	Bibliography