4.16 Treelists

8.15.0.6

4.16 Treelists🔗ℹ

A treelist represents a sequence of elements in a way that supports many operations in O(log N) time: accessing an element of the list by index, adding to the front of the list, adding to the end of the list, removing an element by index, replacing an element by index, appending lists, dropping elements from the start or end of the list, and extracting a sublist. More generally, unless otherwise specified, operations on a treelist of length N take O(log N) time. The base for the log in O(log N) is large enough that it’s effectively constant-time for many purposes. Treelists are currently implemented as RRB trees [Stucki15].

Treelists are primarily intended to be used in immutable form via racket/treelist, where an operation such as adding to the treelist produces a new treelist while the old one remains intact. A mutable variant of treelists is provided by racket/mutable-treelist, where a mutable treelist can be a convenient alternative to putting an immutable treelist into a box. Mutable treelist operations take the same time as immutable treelist operations, unless otherwise specified. Where the term “treelist” is used by itself, it refers to an immutable treelist.

An immutable or mutable treelist can be used as a single-valued sequence (see Sequences). The elements of the list serve as elements of the sequence. See also in-treelist and in-mutable-treelist. An immutable treelist can also be used as a stream.

Changed in version 8.15.0.3 of package base: Made treelists serializable.

4.16.1 Immutable Treelists🔗ℹ

(require racket/treelist)

package: base

The bindings documented in this section are provided by the racket/treelist library, not racket/base or racket.

Added in version 8.12.0.7 of package base.

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

Returns #t if v is a treelist, #f otherwise.

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

Returns a treelist with vs as its elements in order.

This operation takes O(N log N) time to construct a treelist of N elements.

Example:

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

procedure
(make-treelist size v) → treelist?
size : exact-nonnegative-integer?
v : any/c

Returns a treelist with size size, where every element is v. This operation takes O(log N) time to construct a treelist of N elements.

Examples:

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

Added in version 8.12.0.11 of package base.

procedure
(treelist-empty? tl) → boolean?
tl : treelist?
value
empty-treelist : (and/c treelist? treelist-empty?)

A predicate and constant for a treelist of length 0.

Although every empty treelist is equal? to empty-treelist, since a treelist can be chaperoned via chaperone-treelist, not every empty treelist is eq? to empty-treelist.

procedure
(treelist-length tl) → exact-nonnegative-integer?
tl : treelist?

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

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-length items)
3

procedure
(treelist-ref tl pos) → any/c
tl : treelist?
pos : exact-nonnegative-integer?

Returns the posth element of tl. The first element is position 0, and the last position is one less than (treelist-length tl).

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-ref items 0)
1
> (treelist-ref items 2)
'apple
> (treelist-ref items 3)
treelist-ref: index is out of range
  index: 3
  valid range: [0, 2]
  treelist: (treelist 1 "a" 'apple)

procedure
(treelist-first tl) → any/c
tl : treelist?
procedure
(treelist-last tl) → any/c
tl : treelist?

Shorthands for using treelist-ref to access the first or last element of a treelist.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-first items)
1
> (treelist-last items)
'apple

procedure
(treelist-insert tl pos v) → treelist?
  tl : treelist?
  pos : exact-nonnegative-integer?
  v : any/c

Produces a treelist like tl, except that v is inserted as an element before the element at pos. If pos is (treelist-length tl), then v is added to the end of the treelist.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-insert items 1 "alpha")
(treelist 1 "alpha" "a" 'apple)
> (treelist-insert items 3 "alpha")
(treelist 1 "a" 'apple "alpha")

procedure
(treelist-add tl v) → treelist?
  tl : treelist?
  v : any/c
procedure
(treelist-cons tl v) → treelist?
  tl : treelist?
  v : any/c

Shorthands for using treelist-insert to insert at the end or beginning of a treelist.

Although the main operation to extend a pair list is cons to add to the front, treelists are intended to be extended by adding to the end with treelist-add, and treelist-add tends to be faster than treelist-cons.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-add items "alpha")
(treelist 1 "a" 'apple "alpha")
> (treelist-cons items "alpha")
(treelist "alpha" 1 "a" 'apple)

procedure
(treelist-delete tl pos) → treelist?
tl : treelist?
pos : exact-nonnegative-integer?

Produces a treelist like tl, except that the element at pos is removed.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-delete items 1)
(treelist 1 'apple)
> (treelist-delete items 3)
treelist-delete: index is out of range
  index: 3
  valid range: [0, 2]
  treelist: (treelist 1 "a" 'apple)

procedure
(treelist-set tl pos v) → treelist?
  tl : treelist?
  pos : exact-nonnegative-integer?
  v : any/c

Produces a treelist like tl, except that the element at pos is replaced with v. The result is equivalent to (treelist-insert (treelist-delete tl pos) pos v).

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-set items 1 "b")
(treelist 1 "b" 'apple)

procedure
(treelist-append tl ...) → treelist?
tl : treelist?

Appends the elements of the given tls into a single treelist. If M treelists are given and the resulting treelist’s length is N, then appending takes O(M log N) time.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-append items items)
(treelist 1 "a" 'apple 1 "a" 'apple)
> (treelist-append items (treelist "middle") items)
(treelist 1 "a" 'apple "middle" 1 "a" 'apple)

procedure
(treelist-take tl n) → treelist?
  tl : treelist?
  n : exact-nonnegative-integer?
procedure
(treelist-drop tl n) → treelist?
  tl : treelist?
  n : exact-nonnegative-integer?
procedure
(treelist-take-right tl n) → treelist?
  tl : treelist?
  n : exact-nonnegative-integer?
procedure
(treelist-drop-right tl n) → treelist?
  tl : treelist?
  n : exact-nonnegative-integer?

Produces a treelist like tl but with only the first n elements, without the first n elements, with only the last n elements, or without the last n elements, respectively.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-take items 2)
(treelist 1 "a")
> (treelist-drop items 2)
(treelist 'apple)
> (treelist-take-right items 2)
(treelist "a" 'apple)
> (treelist-drop-right items 2)
(treelist 1)

procedure
(treelist-sublist tl n m) → treelist?
  tl : treelist?
  n : exact-nonnegative-integer?
  m : exact-nonnegative-integer?

Produces a treelist like tl but with only elements at position n (inclusive) through position m (exclusive).

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-sublist items 1 3)
(treelist "a" 'apple)

procedure
(treelist-reverse tl) → treelist?
tl : treelist?

Produces a treelist like tl but with its elements reversed, equivalent to using treelist-take to keep 0 elements (but also any chaperone on the treelist) and then adding each element back in reverse order. Reversing takes O(N log N) time.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-reverse items)
(treelist 'apple "a" 1)

procedure
(treelist-rest tl) → treelist?
tl : treelist?

A shorthand for using treelist-drop to drop the first element of a treelist.

The treelist-rest operation is efficient, but not as fast as rest or cdr. For iterating through a treelist, consider using treelist-ref or a for form with in-treelist, instead.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-rest items)
(treelist "a" 'apple)

procedure
(treelist->vector tl) → vector?
  tl : treelist?
procedure
(treelist->list tl) → list?
  tl : treelist?
procedure
(vector->treelist vec) → treelist?
  vec : vector?
procedure
(list->treelist lst) → treelist?
  lst : list?

Convenience functions for converting between treelists, lists, and vectors. Each conversion takes O(N) time.

Examples:

> (define items (list->treelist '(1 "a" 'apple)))
> (treelist->vector items)
'#(1 "a" 'apple)

procedure
(treelist-map tl proc) → treelist?
tl : treelist?
proc : (any/c . -> . any/c)

Produces a treelist by applying proc to each element of tl and gathering the results into a new treelist. For a constant-time proc, this operation takes O(N) time.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-map items box)
(treelist '#&1 '#&"a" '#&apple)

procedure
(treelist-for-each tl proc) → void?
tl : treelist?
proc : (any/c . -> . any)

Applies proc to each element of tl, ignoring the results. For a constant-time proc, this operation takes O(N) time.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-for-each items println)
1
"a"
'apple

procedure
(treelist-filter keep tl) → treelist?
keep : (any/c . -> . any/c)
tl : treelist?

Produces a treelist with only members of tl that satisfy keep.

Examples:

> (treelist-filter even? (treelist 1 2 3 2 4 5 2))
(treelist 2 2 4 2)
> (treelist-filter odd? (treelist 1 2 3 2 4 5 2))
(treelist 1 3 5)
> (treelist-filter (λ (x) (not (even? x))) (treelist 1 2 3 2 4 5 2))
(treelist 1 3 5)
> (treelist-filter (λ (x) (not (odd? x))) (treelist 1 2 3 2 4 5 2))
(treelist 2 2 4 2)

Added in version 8.15.0.6 of package base.

procedure
(treelist-member? tl v [eql?]) → boolean?
  tl : treelist?
  v : any/c
  eql? : (any/c any/c . -> . any/c) = equal?

Checks each element of tl with eql? and v (with v the second argument) until the result is a true value, and then returns #t. If no such element is found, the result is #f. For a constant-time eql?, this operation takes O(N) time.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-member? items "a")
#t
> (treelist-member? items 1.0 =)
#t
> (treelist-member? items 2.0 =)
=: contract violation
expected: number?
given: "a"

procedure
(treelist-find tl pred) → any/c
tl : treelist?
pred : (any/c . -> . any/c)

Checks each element of tl with pred until the result is a true value, and then returns that element. If no such element is found, the result is #f. For a constant-time pred, this operation takes O(N) time.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-find items string?)
"a"
> (treelist-find items symbol?)
'apple
> (treelist-find items number->string)
1

procedure
(treelist-index-of tl v [eql?])
→ (or/c exact-nonnegative-integer? #f)
  tl : treelist?
  v : any/c
  eql? : (any/c any/c . -> . any/c) = equal?

Returns the index of the first element in tl that is eql? to v. If no such element is found, the result is #f.

Examples:

> (define items (treelist 1 "a" 'apple))
> (treelist-index-of items 1)
0
> (treelist-index-of items "a")
1
> (treelist-index-of items 'apple)
2
> (treelist-index-of items 'unicorn)
#f

Added in version 8.15.0.6 of package base.

procedure
(treelist-flatten v) → treelist?
v : any/c

Flattens a tree of nested treelists into a single treelist.

Examples:

> (treelist-flatten
(treelist (treelist "a") "b" (treelist "c" (treelist "d") "e") (treelist)))
(treelist "a" "b" "c" "d" "e")
> (treelist-flatten "a")
(treelist "a")

Added in version 8.15.0.6 of package base.

procedure
(treelist-append* tlotl) → treelist?
tlotl : (treelist/c treelist?)

Appends elements of a treelist of treelists together into one treelist, leaving any further nested treelists alone.

Example:

> (treelist-append*
(treelist (treelist "a" "b") (treelist "c" (treelist "d") "e") (treelist)))
(treelist "a" "b" "c" (treelist "d") "e")

Added in version 8.15.0.6 of package base.

procedure
(treelist-sort tl
less-than?
[ #:key key
#:cache-keys? cache-keys?]) → treelist?
  tl : treelist?
  less-than? : (any/c any/c . -> . any/c)
  key : (or/c #f (any/c . -> . any/c)) = #f
  cache-keys? : boolean? = #f

Like sort, but operates on a treelist to produce a sorted treelist. Sorting takes O(N log N) time.

Examples:

> (define items (treelist "x" "a" "q"))
> (treelist-sort items string<?)
(treelist "a" "q" "x")

procedure
(in-treelist tl) → sequence?
tl : treelist?

Returns a sequence equivalent to tl.

An in-treelist application can provide better performance for treelist iteration when it appears directly in a for clause.

Examples:

> (define items (treelist "x" "a" "q"))
> (for/list ([e (in-treelist items)])
(string-append e "!"))
'("x!" "a!" "q!")

procedure
(sequence->treelist s) → treelist?
s : sequence?

Returns a treelist whose elements are the elements of s, each of which must be a single value. If s is infinite, this function does not terminate.

Examples:

> (sequence->treelist (list 1 "a" 'apple))
(treelist 1 "a" 'apple)
> (sequence->treelist (vector 1 "a" 'apple))
(treelist 1 "a" 'apple)
> (sequence->treelist (stream 1 "a" 'apple))
(treelist 1 "a" 'apple)
> (sequence->treelist (open-input-bytes (bytes 1 2 3 4 5)))
(treelist 1 2 3 4 5)
> (sequence->treelist (in-range 0 10))
(treelist 0 1 2 3 4 5 6 7 8 9)

Added in version 8.15.0.6 of package base.

syntax
(for/treelist (for-clause ...) body-or-break ... body)
syntax
(for*/treelist (for-clause ...) body-or-break ... body)

Like for/list and for*/list, but generating treelists.

Example:

> (for/treelist ([i (in-range 10)])
i)
(treelist 0 1 2 3 4 5 6 7 8 9)

procedure
(chaperone-treelist tl
#:state state
[ #:state-key state-key]
#:ref ref-proc
#:set set-proc
#:insert insert-proc
#:delete delete-proc
#:take take-proc
#:drop drop-proc
#:append append-proc
#:prepend prepend-proc
[ #:append2 append2-proc]
prop
prop-val ...
...)
→ (and/c treelist? chaperone?)
  tl : treelist?
  state : any/c
  state-key : any/c = (list 'fresh)
   ref-proc :
(treelist? exact-nonnegative-integer? any/c any/c
. -> . any/c)
   set-proc :
(treelist? exact-nonnegative-integer? any/c any/c
. -> . (values any/c any/c))
   insert-proc :
(treelist? exact-nonnegative-integer? any/c any/c
. -> . (values any/c any/c))
   delete-proc :
(treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   take-proc :
(treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   drop-proc :
(treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   append-proc :
(treelist? treelist? any/c
. -> . (values treelist? any/c))
   prepend-proc :
(treelist? treelist? any/c
. -> . (values treelist? any/c))
   append2-proc :
(or/c #f (treelist? treelist? any/c any/c
          . -> . (values treelist? any/c any/c)))
= #f
  prop : impersonator-property?
  prop-val : any/c

Analogous to chaperone-vector, returns a chaperone of tl, which redirects the treelist-ref, treelist-set, treelist-insert, treelist-append, treelist-delete, treelist-take, and treelist-drop operations, as well as operations derived from those. The state argument is an initial state, where a state value is passed to each procedure that redirects an operation, and except for ref-proc (which corresponds to the one operation that does not update a treelist), a new state is returned to be associated with the updated treelist. When state-key is provided, it can be used with treelist-chaperone-state to extract the state from the original treelist or an updated treelist.

The ref-proc procedure must accept tl, an index passed to treelist-ref, the value that treelist-ref on tl produces for the given index, and the current chaperone state; it must produce a chaperone replacement for the value, which is the result of treelist-ref on the chaperone.

The set-proc procedure must accept tl, an index passed to treelist-set, the value provided to treelist-set, and the current chaperone state; it must produce two values: a chaperone replacement for the value, which is used in the result of treelist-set on the chaperone, and an updated state. The result of treelist-set is chaperoned with the same procedures and properties as tl, but with the updated state.

The insert-proc procedure is like set-proc, but for inserting via treelist-insert.

The delete-proc, take-proc, and drop-proc procedures must accept tl, the index or count for deleting, taking or dropping, and the current chaperone state; they must produce an updated state. The result of treelist-delete, treelist-take, or treelist-drop is chaperoned with the same procedures and properties as tl, but with the updated state.

The append-proc procedure must accept tl, a treelist to append onto tl, and the current chaperone state; it must produce a chaperone replacement for the second treelist, which is appended for the result of treelist-append on the chaperone, and an updated state. The result of treelist-append is chaperoned with the same procedures and properties as tl, but with the updated state.

The prepend-proc procedure must accept a treelist being append with tl, tl, and the current chaperone state; it must produce a chaperone replacement for the first treelist, which is prepended for the result of treelist-append on the chaperone, and an updated state. The result of treelist-append is chaperoned with the same procedures and properties as tl, but with the updated state.

The append2-proc procedure is optional and similar to append-proc, but when it is non-#f, append2-proc is used instead of append-proc when a second argument to treelist-append is chaperoned with the same state-key. In that case, the second argument to append2-proc is the second argument with a state-key chaperone wrapper removed, and with that chaperone’s state as the last argument to append2-proc.

When two chaperoned treelists are given to treelist-append and append2-proc is not used, then the append-proc of the first treelist is used, and the result of append-proc will still be a chaperone whose prepend-proc is used. If the result of prepend-proc is a chaperone, then that chaperone’s append-proc is used, and so on. If prepend-proc and append-proc keep returning chaperones, it is possible that no progress will be made.

Example:

> (chaperone-treelist
   (treelist 1 "a" 'apple)
   #:state 'ignored-state
   #:ref (λ (tl pos v state)
           v)
   #:set (λ (tl pos v state)
           (values v state))
   #:insert (λ (tl pos v state)
              (values v state))
   #:delete (λ (tl pos state)
              state)
   #:take (λ (tl pos state)
            state)
   #:drop (λ (tl pos state)
            state)
   #:append2 (λ (tl other state other-state) ; or #f
               (values other state))
   #:append (λ (tl other state)
              (values other state))
   #:prepend (λ (other tl state)
               (values other state)))
(treelist 1 "a" 'apple)

procedure
(treelist-chaperone-state tl
state-key
[ fail-k]) → any/c
  tl : treelist?
  state-key : any/c
  fail-k : (procedure-arity-includes/c 0) = key-error

Extracts state associated with a treelist chaperone where state-key (compared using eq?) was provided along with the initial state to chaperone-treelist. If tl is not a chaperone with state keyed by state-key, then fail-k is called, and the default fail-k raises exn:fail:contract.

4.16.2 Mutable Treelists🔗ℹ

(require racket/mutable-treelist)

package: base

The bindings documented in this section are provided by the racket/mutable-treelist library, not racket/base or racket.

A mutable treelist is like an immutable treelist in a box, where operations that change the mutable treelist replace the treelist in the box. As a special case, mutable-treelist-set! on an unimpersonated mutable treelist modifies the treelist representation within the boxed value. This model of a mutable treelist explains its behavior in the case of concurrent modification: concurrent mutable-treelist-set! operations for different positions will not interefere, but races with other operations or on impersonated mutable treelists will sometimes negate one of the modifications. Concurrent modification is thus somewhat unpredictable but still safe, and it is not managed by a lock.

A mutable treelist is not a treelist in the sense of treelist?, which recognizes only immutable treelists. Operations on a mutable treelist have the same time complexity as corresponding operations on an immutable treelist unless otherwise noted.

Added in version 8.12.0.7 of package base.

procedure
(mutable-treelist? v) → boolean?
v : any/c

Returns #t if v is a mutable treelist, #f otherwise.

procedure
(mutable-treelist v ...) → mutable-treelist?
v : any/c

Returns a mutable treelist with vs as its elements in order.

Example:

> (mutable-treelist 1 "a" 'apple)
(mutable-treelist 1 "a" 'apple)

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

Creates a mutable treelist that contains n elements, each initialized as v. Creating the mutable treelist takes O(N) time for N elements.

Example:

> (make-mutable-treelist 3 "a")
(mutable-treelist "a" "a" "a")

procedure
(treelist-copy tl) → mutable-treelist?
tl : treelist?

Creates a mutable treelist that contains the same elements as tl. Creating the mutable treelist takes O(N) time for N elements.

Example:

> (treelist-copy (treelist 3 "a"))
(mutable-treelist 3 "a")

procedure
(mutable-treelist-snapshot tl) → treelist?
tl : mutable-treelist?

Produces an immutable treelist that has the same elements as tl. Creating the immutable treelist takes O(N) time for N elements.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (define snap (mutable-treelist-snapshot items))
> (mutable-treelist-drop! items 2)
> items
(mutable-treelist 'apple)
> snap
(treelist 1 "a" 'apple)

procedure
(mutable-treelist-empty? tl) → boolean?
tl : mutable-treelist?

Returns #t for mutable treelist that is currently of length 0, #f otherwise.

procedure
(mutable-treelist-length tl) → exact-nonnegative-integer?
tl : mutable-treelist?

Returns the number of elements currently in tl.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-length items)
3
> (mutable-treelist-add! items 'extra)
> (mutable-treelist-length items)
4

procedure
(mutable-treelist-ref tl pos) → any/c
tl : mutable-treelist?
pos : exact-nonnegative-integer?

Returns the posth element of tl. The first element is position 0, and the last position is one less than (mutable-treelist-length tl).

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-ref items 0)
1
> (mutable-treelist-ref items 2)
'apple
> (mutable-treelist-ref items 3)
mutable-treelist-ref: index is out of range
  index: 3
  valid range: [0, 2]
  treelist: (treelist 1 "a" 'apple)

procedure
(mutable-treelist-first tl) → any/c
tl : mutable-treelist?
procedure
(mutable-treelist-last tl) → any/c
tl : mutable-treelist?

Shorthands for using mutable-treelist-ref to access the first or last element of a treelist.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-first items)
1
> (mutable-treelist-last items)
'apple

procedure
(mutable-treelist-insert! tl pos v) → void?
  tl : mutable-treelist?
  pos : exact-nonnegative-integer?
  v : any/c

Modifies tl to insert v into the list before position pos. If pos is (mutable-treelist-length tl), then v is added to the end of the treelist.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-insert! items 1 "alpha")
> items
(mutable-treelist 1 "alpha" "a" 'apple)

procedure
(mutable-treelist-cons! tl v) → void?
  tl : mutable-treelist?
  v : any/c
procedure
(mutable-treelist-add! tl v) → void?
  tl : mutable-treelist?
  v : any/c

Shorthands for using mutable-treelist-insert! to insert at the beginning or end of a treelist.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-cons! items "before")
> (mutable-treelist-add! items "after")
> items
(mutable-treelist "before" 1 "a" 'apple "after")

procedure
(mutable-treelist-delete! tl pos) → void?
tl : mutable-treelist?
pos : exact-nonnegative-integer?

Modifies tl to remove the element at pos.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-delete! items 1)
> items
(mutable-treelist 1 'apple)

procedure
(mutable-treelist-set! tl pos v) → void?
  tl : mutable-treelist?
  pos : exact-nonnegative-integer?
  v : any/c

Modifies tl to change the element at pos to v.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-set! items 1 "b")
> items
(mutable-treelist 1 "b" 'apple)

procedure
(mutable-treelist-append! tl other-tl) → void?
tl : mutable-treelist?
other-tl : (or/c treelist? mutable-treelist?)

Modifies tls by appending all of the elements of other-tl. If other-tl is a mutable treelist, it is first converted to an immutable treelist with mutable-treelist-snapshot, which takes takes O(N) time if other-tl has N elements. If other-tl is an immutable treelist but chaperoned, then appending takes O(N) time for N elements.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-append! items (treelist 'more 'things))
> items
(mutable-treelist 1 "a" 'apple 'more 'things)
> (mutable-treelist-append! items items)
> items
(mutable-treelist 1 "a" 'apple 'more 'things 1 "a" 'apple 'more 'things)

procedure
(mutable-treelist-take! tl n) → void?
  tl : mutable-treelist?
  n : exact-nonnegative-integer?
procedure
(mutable-treelist-drop! tl n) → void?
  tl : mutable-treelist?
  n : exact-nonnegative-integer?
procedure
(mutable-treelist-take-right! tl n) → void?
  tl : mutable-treelist?
  n : exact-nonnegative-integer?
procedure
(mutable-treelist-drop-right! tl n) → void?
  tl : mutable-treelist?
  n : exact-nonnegative-integer?

Modifies tl to remove all but the first n elements, to remove the first n elements, to remove all but the last n elements, or to remove the last n elements, respectively.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-take! items 2)
> items
(mutable-treelist 1 "a")
> (mutable-treelist-drop-right! items 1)
> items
(mutable-treelist 1)

procedure
(mutable-treelist-sublist! tl n m) → void?
  tl : mutable-treelist?
  n : exact-nonnegative-integer?
  m : exact-nonnegative-integer?

Modifies tl to remove elements other than elements at position n (inclusive) through position m (exclusive).

Examples:

> (define items (mutable-treelist 1 "a" 'apple 'pie))
> (mutable-treelist-sublist! items 1 3)
> items
(mutable-treelist "a" 'apple)

procedure
(mutable-treelist-reverse! tl) → void?
tl : mutable-treelist?

Modifies tl to reverse all of its elements.

Examples:

> (define items (mutable-treelist 1 "a" 'apple 'pie))
> (mutable-treelist-reverse! items)
> items
(mutable-treelist 'pie 'apple "a" 1)

procedure
(mutable-treelist->vector tl) → vector?
  tl : mutable-treelist?
procedure
(mutable-treelist->list tl) → list?
  tl : mutable-treelist?
procedure
(vector->mutable-treelist vec) → mutable-treelist?
  vec : vector?
procedure
(list->mutable-treelist lst) → mutable-treelist?
  lst : list?

Convenience functions for converting between mutable treelists, lists, and vectors. Each conversion takes O(N) time.

Examples:

> (define items (list->mutable-treelist '(1 "a" 'apple)))
> (mutable-treelist->vector items)
'#(1 "a" 'apple)

procedure
(mutable-treelist-map! tl proc) → void?
tl : mutable-treelist?
proc : (any/c . -> . any/c)

Modifies tl by applying proc to each element of tl and installing the result in place of the element.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-map! items box)
> items
(mutable-treelist '#&1 '#&"a" '#&apple)

procedure
(mutable-treelist-for-each tl proc) → void?
tl : mutable-treelist?
proc : (any/c . -> . any)

Like treelist-for-each, but for a mutable treelist.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-for-each items println)
1
"a"
'apple

procedure
(mutable-treelist-member? tl v [eql?]) → boolean?
  tl : mutable-treelist?
  v : any/c
  eql? : (any/c any/c . -> . any/c) = equal?

Like treelist-member?, but for a mutable treelist.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-member? items "a")
#t
> (mutable-treelist-member? items 1.0 =)
#t

procedure
(mutable-treelist-find tl pred) → any/c
tl : mutable-treelist?
pred : (any/c . -> . any/c)

Like treelist-find, but for a mutable treelist.

Examples:

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-find items string?)
"a"
> (mutable-treelist-find items symbol?)
'apple

procedure
(mutable-treelist-sort! tl
less-than?
[ #:key key
#:cache-keys? cache-keys?]) → void?
  tl : mutable-treelist?
  less-than? : (any/c any/c . -> . any/c)
  key : (or/c #f (any/c . -> . any/c)) = #f
  cache-keys? : boolean? = #f

Like vector-sort!, but operates on a mutable treelist.

Examples:

> (define items (mutable-treelist "x" "a" "q"))
> (mutable-treelist-sort! items string<?)
> items
(mutable-treelist "a" "q" "x")

procedure
(in-mutable-treelist tl) → sequence?
tl : mutable-treelist?

Returns a sequence equivalent to tl.

An in-mutable-treelist application can provide better performance for mutable treelist iteration when it appears directly in a for clause.

Examples:

> (define items (mutable-treelist "x" "a" "q"))
> (for/list ([e (in-mutable-treelist items)])
(string-append e "!"))
'("x!" "a!" "q!")

syntax
(for/mutable-treelist (for-clause ...) body-or-break ... body)
syntax
(for*/mutable-treelist (for-clause ...) body-or-break ... body)

Like for/list and for*/list, but generating mutable treelists.

Example:

> (for/mutable-treelist ([i (in-range 10)])
i)
(mutable-treelist 0 1 2 3 4 5 6 7 8 9)

procedure
(chaperone-mutable-treelist tl
#:ref ref-proc
#:set set-proc
#:insert insert-proc
#:append append-proc
prop
prop-val ...
...)
→ (and/c mutable-treelist? chaperone?)
  tl : mutable-treelist?
   ref-proc :
(mutable-treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   set-proc :
(mutable-treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   insert-proc :
(mutable-treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   append-proc :
(mutable-treelist? treelist?
. -> . treelist?)
  prop : impersonator-property?
  prop-val : any/c

Similar to chaperone-treelist, but for mutable treelists. For example, the given set-proc is used for mutable-treelist-set!, and the resulting value is installed into the mutable treelist instead of the one provided to set-proc. Mutable treelist chaperones do not have state separate from the treelist itself, and procedures like set-proc do not consume or return a state.

procedure
(impersonate-mutable-treelist tl
#:ref ref-proc
#:set set-proc
#:insert insert-proc
#:append append-proc
prop
prop-val ...
...)
→ (and/c mutable-treelist? impersonator?)
  tl : mutable-treelist?
   ref-proc :
(mutable-treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   set-proc :
(mutable-treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   insert-proc :
(mutable-treelist? exact-nonnegative-integer? any/c
. -> . any/c)
   append-proc :
(mutable-treelist? treelist?
. -> . treelist?)
  prop : impersonator-property?
  prop-val : any/c

Like chaperone-mutable-treelist, but ref-proc, set-proc, insert-proc, and append-proc are not obligated to produce chaperones.

1	Language Model
2	Notation for Documentation
3	Syntactic Forms
4	Datatypes
5	Structures
6	Classes and Objects
7	Units
8	Contracts
9	Pattern Matching
10	Control Flow
11	Concurrency and Parallelism
12	Macros
13	Input and Output
14	Reflection and Security
15	Operating System
16	Memory Management
17	Unsafe Operations
18	Running Racket
	Bibliography
	Index

4.1	Equality
4.2	Booleans
4.3	Numbers
4.4	Strings
4.5	Byte Strings
4.6	Characters
4.7	Symbols
4.8	Regular Expressions
4.9	Keywords
4.10	Pairs and Lists
4.11	Mutable Pairs and Lists
4.12	Vectors
4.13	Stencil Vectors
4.14	Boxes
4.15	Hash Tables
4.16	Treelists
4.17	Sequences and Streams
4.18	Dictionaries
4.19	Sets
4.20	Procedures
4.21	Void
4.22	Undefined