Racket

Sek: Catenable, Splittable, Transient Sequences🔗ℹ

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

package: sek-lib

A sequence is a finite ordered collection of elements that supports random access, pushing and popping at either end, concatenation and splitting. Sequences come in two flavors: a persistent sequence is immutable, so an operation on one produces a new sequence and leaves the original intact, and an ephemeral sequence is updated in place. The library implements the data structure of Charguéraud and Pottier [Chargueraud26].

Conversions between the two flavors are cheap: psek-edit produces an ephemeral sequence in constant time, and esek-snapshot produces a persistent sequence in logarithmic time, where snapshotting and editing other data structures typically take time linear in the size of the data. This approach is called transience, following terminology originally developed in Clojure.

Examples:

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

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 (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 (32). Unless otherwise specified, operations on a sequence of length N take O(logK N) time. As with treelists, the base of the log is large enough that it is effectively constant-time for many purposes: a sequence of up to a hundred million elements is at most six levels deep.

Sequences of either flavor can be used as single-valued sequences whose elements are the sequence’s elements, they are serializable?, and two sequences of the same flavor are equal? when their elements are. A persistent sequence can also be used as a stream. Any number of threads may use a persistent sequence at once, and an ephemeral sequence too as long as none of them updates it; Threads gives the rules.

1 Persistent Sequences🔗ℹ

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

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

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

Returns a persistent sequence with vs as its elements in order. This operation takes O(N + K) time.

Example:

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

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

Build a persistent sequence of n copies of v, of the results of proc on 0 through (sub1 n), of the elements of any Racket sequence (at most n of them, when n is given), or of the results of a comprehension. Each takes O(N + K) time.

Examples:

> (build-psek 4 (lambda (i) (* i i)))
(psek 0 1 4 9)
> (for/psek ([c "abc"]) (char-upcase c))
(psek #\A #\B #\C)

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

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

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

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

Example:

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

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

Return a persistent sequence with v added at the end (psek-add) or at the front (psek-cons). psek-push-back and psek-push-front are aliases for these operations, following the names in the paper.

These take O(K logK 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 (psek 1 2 3))
> (psek-cons s 0)
(psek 0 1 2 3)
> (psek-add s 4)
(psek 1 2 3 4)
> s
(psek 1 2 3)

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

Return the element at the given end and the rest of the sequence, or raise exn:fail:contract if s is empty. These operations take O(logK N) time in the worst case, and most take O(1); they take O(T) time when the result has at most T elements.

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

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

procedure
(psek-ref s i) → any/c
  s : psek?
  i : exact-nonnegative-integer?
procedure
(psek-set s i v) → psek?
  s : psek?
  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 (psek-length s).

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

Examples:

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

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

Returns a persistent sequence with the elements of s1 followed by those of s2. This operation takes O(K logK N + logK2 N) time.

Example:

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

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

Returns the first i elements and the rest. This operation takes O(K logK N + logK2 N) time.

Examples:

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

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

The two halves of psek-split separately: the first i elements, or all but the first i. Each takes the same time as psek-split.

Examples:

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

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

Conversion and iteration; see in-psek for iterating in a for clause. Each of these takes O(N) time.

syntax
(in-psek s)
(in-psek s dir)

A sequence over the elements of s, in 'forward order by default or 'backward. It is fastest written directly in a for clause. A full traversal takes O(N) time.

procedure
(psek-edit s) → esek?
s : psek?

Returns an ephemeral sequence with the contents of s, which is unaffected by later updates to the result. This operation takes O(1) time, or O(K) when s has at most T elements.

Examples:

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

2 Ephemeral Sequences🔗ℹ

An operation that changes an ephemeral sequence modifies the sequence it is given, where the corresponding operation on a persistent sequence returns a new one. Several threads may read an ephemeral sequence at once, but an update needs exclusive access; Threads lists the operations that count as updates.

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

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

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

Returns an ephemeral sequence with vs as its elements in order. This operation takes O(N + K) time.

Example:

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

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

Build an ephemeral sequence of n copies of v, of the results of proc on 0 through (sub1 n), of the elements of any Racket sequence (at most n of them, when n is given), or of the results of a comprehension. make-esek takes the same arguments as make-vector. Each takes O(N + K) time.

Examples:

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

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

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

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

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

Example:

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

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

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

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

Examples:

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

procedure
(esek-ref e i) → any/c
  e : esek?
  i : exact-nonnegative-integer?
procedure
(esek-set! e i v) → void?
  e : esek?
  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 (esek-length e).

esek-ref takes O(K logK N) time in general, and O(logK N) time for a sequence built without concatenation. esek-set! takes O(K logK N) time. For a sequence built without concatenation it takes O(logK N), except that after a snapshot or an edit the first update near each index costs the full O(K logK N).

Examples:

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

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

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

The six operations that follow rearrange ephemeral sequences in place, and they consume the sequences they are given, leaving each empty unless it holds the result. Use sek-take, sek-drop and sek-sub when the input must survive.

procedure
(esek-append! e other [side]) → void?
  e : esek?
  other : (or/c esek? psek?)
  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. This operation takes O(K logK N + logK2 N) time.

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

Returns a new sequence holding the concatenation, and empties both arguments, which must be distinct. This operation takes O(K logK N + logK2 N) time.

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

Returns two new sequences holding the first i elements and the rest, and empties e. This operation takes O(K logK N + logK2 N) time.

procedure
(esek-carve! e i [side]) → esek?
  e : esek?
  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. It saves an allocation over esek-split! when one part is going back into the same variable. This operation takes O(K logK N + logK2 N) time.

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

Truncate e at index i. esek-take! keeps the front part when side is 'front and the back part otherwise; esek-drop! keeps the other one. Each takes O(K logK N + logK2 N) time.

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

Moves the contents of e2 into e1 and empties e2, or does nothing if the two are the same sequence. This operation takes O(K logK N) time.

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

Empties e. This operation takes O(1) time.

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

Conversion and iteration; see in-esek for iterating in a for clause. Each of these takes O(N) time.

syntax
(in-esek e)
(in-esek e dir)

A sequence over the elements of e, in 'forward order by default or 'backward. It is fastest written directly in a for clause. Updating e during the loop is detected, as for an iterator. A full traversal takes O(N) time.

procedure
(esek-fill! e v [start end]) → void?
  e : esek?
  v : any/c
  start : exact-nonnegative-integer? = 0
  end : exact-nonnegative-integer? = (esek-length e)
procedure
(esek-copy! dst
dst-start
src
[ src-start
src-end]) → void?
  dst : esek?
  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: esek-fill! sets those from start to end to v, and esek-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, and only the destination is modified; esek-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 logK N) time, even after a snapshot, and O((size + K) logK N) in general.

Examples:

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

procedure
(esek-map! e proc) → void?
  e : esek?
  proc : (-> any/c any/c)
procedure
(esek-map/index! e proc) → void?
  e : esek?
  proc : (-> exact-nonnegative-integer? any/c any/c)

Replace each element of e, from first to last, with the result of proc on it, or on its index and it, as vector-map! and mutable-treelist-map! do. Updating e in proc is an error, detected as for an iterator. Each takes the same time as esek-fill! over the whole sequence, plus the cost of the calls to proc.

Examples:

> (define s (psek 1 2 3))
> (define e (psek-edit s))
> (esek-map/index! e (lambda (i x) (+ x i)))
> (esek-snapshot e)
(psek 1 3 5)
> s
(psek 1 2 3)

procedure
(esek-snapshot e) → psek?
e : esek?

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, and later updates to e may cost more than they otherwise would.

Examples:

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

procedure
(esek-snapshot-and-clear! e) → psek?
e : esek?

Returns a snapshot of e and empties e. Unlike esek-snapshot, it does not make later updates to e more expensive. This operation takes O(K logK N) time in the worst case.

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

Returns an independent ephemeral copy of e. In 'copy mode, the default, the copy takes O(N) time and leaves no later cost. In 'share mode it takes O(1) time, but later updates to either sequence, e included, cost more than they otherwise would.

3 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. Each takes the same time as the corresponding operation on that flavor.

syntax
(in-sek s)
(in-sek s dir)

A sequence over the elements of s, like in-psek or in-esek. A full traversal takes O(N) time.

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

Apply proc to each element, or to each index and element, in the given direction. Each takes O(N) time plus the cost of the calls to proc.

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. Each takes O(N) time plus the cost of the calls to proc.

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

Conversions. Each takes O(N) time.

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. Each takes O(N) time in the worst case.

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. This operation takes O(N) time in the worst case.

Examples:

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

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. sek-append* concatenates a sequence of sequences; given an ephemeral one it empties both it and its elements. Each takes O(N) time plus the cost of the calls to proc or pred, where N counts the elements of both s and the result for sek-append* and sek-append-map; on an ephemeral sequence sek-append* instead takes O(K logK N + logK2 N) time per element of s.

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

The size elements of s starting at start, the first n elements, all but the first n, or a copy. sek-copy is the identity on a persistent sequence and esek-copy on an ephemeral one. None of them modifies s.

sek-take and sek-drop take O(K logK N + logK2 N) time. So does sek-sub on a persistent sequence; on an ephemeral sequence it copies the slice instead, in O(size + K logK N) time, which does not make later updates to s more expensive.

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. Neither modifies s, and each takes the same time as sek-take and sek-drop.

Examples:

> (sek-take-right (psek 1 2 3 4 5) 2)
(psek 4 5)
> (sek-drop-right (psek 1 2 3 4 5) 2)
(psek 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. Neither modifies s, and each takes O(K logK N + logK2 N) time.

Examples:

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

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; a pass that drops adjacent duplicates, and so drops every duplicate from a sorted sequence; and a stable merge of two sorted sequences. sek-sort takes O(N log N) time, and the other two O(N).

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<? s1 s2 less-than?) → boolean?
  s1 : sek?
  s2 : sek?
  less-than? : (-> any/c any/c any/c)

Operations on two sequences at once. They stop at the end of the shorter sequence, except sek-equal?, which first compares lengths, and sek<?, which tests whether s1 comes before s2 in lexicographic order, with a proper prefix first and elements neither of which is less-than? the other taken as equal. sek-zip pairs elements with cons, and sek-unzip undoes it. Each takes O(N) time plus the cost of the calls to the procedure argument.

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 an iterator one step costs O(1) amortized, so a traversal by iterator costs O(N), where repeated sek-ref pays for a lookup at every element.

Any update to an ephemeral sequence invalidates every iterator on it, except that sek-iter-set! leaves the iterator it writes through usable. Using an invalidated iterator raises an exception; make a new one instead. Iterators on persistent sequences are never invalidated.

procedure
(sek-iterator s [i]) → sek-iter?
s : sek?
i : exact-integer? = 0

Returns an iterator on the element of s at index i, or on a sentinel when i is -1 or (sek-length s). Starting at either end takes O(1) time, and starting anywhere else at most as long as sek-ref.

Examples:

> (define s (psek 'a 'b 'c 'd))
> (define it (sek-iterator s 1))
> (sek-iter-get it)
'b
> (sek-iter-move! it)
> (sek-iter-get it)
'c
> (define backward (sek-iterator s (sub1 (sek-length s))))
> (let loop ([acc '()])
    (if (sek-iter-finished? backward)
        (reverse acc)
        (let ([x (sek-iter-get backward)])
          (sek-iter-move! backward 'backward)
          (loop (cons x acc)))))
'(d c b a)

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

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

procedure
(sek-iter-index it) → exact-integer?
it : sek-iter?
procedure
(sek-iter-finished? it) → boolean?
it : sek-iter?

The iterator’s current position, in [-1, N], and whether that position is a sentinel. Each takes O(1) time.

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

Returns the element under the iterator, or raises an exception at a sentinel. This operation takes O(1) time.

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

Moves the iterator one element in the given direction. Moving off the far sentinel raises an exception. This operation takes O(1) amortized time and O(logK N) in the worst case.

procedure
(sek-iter-reach! it i) → void?
it : sek-iter?
i : exact-integer?

Moves the iterator to index i, which may be -1 or the length of the sequence. Reaching either sentinel, or a position inside the run of storage the iterator is on, takes O(1) time; any other move takes at most as long as sek-ref.

procedure
(sek-iter-set! it v) → void?
it : sek-iter?
v : any/c

Replaces the element under it, which must be an iterator on an ephemeral sequence and not on a sentinel, with v. It invalidates every other iterator on that sequence. The first write into a chunk that is shared with a snapshot takes O(K logK N) time in the worst case, and later writes into the same chunk O(1); for a sequence built without concatenation, a sweep that writes every element takes O(N + K logK N) time, even after a snapshot.

5 Threads🔗ℹ

These rules apply to Racket threads, whether or not they run in parallel, and to futures.

Any number of threads may use a persistent sequence at once, with any operations, and without synchronization.

Any number of threads may use an ephemeral sequence at once as long as none of them updates it. An update needs exclusive access: while it runs, no other thread may use the sequence or an iterator over it. These operations update an ephemeral sequence:

every operation whose name begins with esek- and ends in !, on the sequence it modifies. esek-append!, esek-assign! and esek-concat! also update the ephemeral sequence that they empty; the source of esek-copy! is only read;
sek-iter-set!, on an iterator over the sequence; and
sek-append*, which updates an ephemeral sequence it is given and every ephemeral sequence in it, since it empties them.

Every other operation only reads the sequences it is given. In particular, iterating over a sequence, esek-snapshot, esek-copy, equal?, and the operations on either flavor that build a new sequence are all reads.

The two flavors can share structure – a snapshot shares with the ephemeral sequence it was taken from, and psek-edit returns an ephemeral sequence that shares with its argument – but the sharing needs no synchronization: one thread may update an ephemeral sequence while others use a persistent sequence that shares with it.

sek-iter-move!, sek-iter-reach! and sek-iter-set! change the iterator, so one iterator may be used by only one thread at a time. Each of several threads may have its own iterator over one sequence, subject to the rules above.

A program that breaks these rules gets unspecified results: an operation may return a wrong answer or raise exn:fail:sek, and the sequence may be left inconsistent. The program’s memory is not corrupted, however; no use of this library, correct or not, corrupts memory.

These rules assume that a sequence reaches another thread through an operation that synchronizes the two threads, such as a channel, a semaphore, or thread-wait.

struct
(struct exn:fail:sek exn:fail ()
#:extra-constructor-name make-exn:fail:sek)

Raised by an operation that finds the structure of a sequence inconsistent, which only a program that breaks the rules above can cause.

6 Comparison with Treelists🔗ℹ

Racket’s treelists solve a similar problem—efficient, persistent data structures with fast indexing, implemented using wide trees (RRB trees [Stucki15], in their case). 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 psek-add for when a persistent push costs O(K)). In the worst case a push takes O(K logK N) time and a pop O(logK N), and a series of pushes and pops on an ephemeral sequence takes amortized O(logK 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 psek-edit takes O(1) and esek-snapshot O(K logK N). Likewise mutable-treelist-append! takes O(N) time in the length of its second argument, where esek-append! takes O(K logK N + logK2 N).

Traversal is O(N) for both.

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	Persistent Sequences
2	Ephemeral Sequences
3	Operations on Either Flavor
4	Iterators
5	Threads
6	Comparison with Treelists
	Bibliography