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.1Immutable Treelists🔗 i

(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 sizev)→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 tlpos)→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 items0)

1
> (treelist-ref items2)

'apple
> (treelist-ref items3)

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 tlposv)→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 items1"alpha")

(treelist 1 "alpha" "a" 'apple)
> (treelist-insert items3"alpha")

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

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

procedure
( treelist-cons tlv)→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 tlpos)→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 items1)

(treelist 1 'apple)
> (treelist-delete items3)

treelist-delete: index is out of range

index: 3

valid range: [0, 2]

treelist: (treelist 1 "a" 'apple)

procedure
( treelist-set tlposv)→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 tlpos)posv).

Examples:

> (define items(treelist 1"a"'apple))
> (treelist-set items1"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 itemsitems)

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

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

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

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

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

procedure
( treelist-drop-right tln)→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 items2)

(treelist 1 "a")
> (treelist-drop items2)

(treelist 'apple)
> (treelist-take-right items2)

(treelist "a" 'apple)
> (treelist-drop-right items2)

(treelist 1)

procedure
( treelist-sublist tlnm)→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 items13)

(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 tlproc)→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 itemsbox )

(treelist '#&1 '#&"a" '#&apple)

procedure
( treelist-for-each tlproc)→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 itemsprintln )

1

"a"

'apple

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

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

Examples:

> (treelist-filter even? (treelist 1232452))

(treelist 2 2 4 2)
> (treelist-filter odd? (treelist 1232452))

(treelist 1 3 5)
> (treelist-filter (λ (x)(not (even? x)))(treelist 1232452))

(treelist 1 3 5)
> (treelist-filter (λ (x)(not (odd? x)))(treelist 1232452))

(treelist 2 2 4 2)

Added in version 8.15.0.6 of package base.

procedure
( treelist-member? tlv[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? items1.0= )

#t
> (treelist-member? items2.0= )

=: contract violation

expected: number?

given: "a"

procedure
( treelist-find tlpred)→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 itemsstring? )

"a"
> (treelist-find itemssymbol? )

'apple
> (treelist-find itemsnumber->string )

1

procedure
( treelist-index-of tlv[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 items1)

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?
[ #:keykey
#: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 itemsstring<? )

(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 12345)))

(treelist 1 2 3 4 5)
> (sequence->treelist (in-range 010))

(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
#:statestate
[ #:state-keystate-key]
#:refref-proc
#:setset-proc
#:insertinsert-proc
#:deletedelete-proc
#:taketake-proc
#:dropdrop-proc
#:appendappend-proc
#:prependprepend-proc
[ #:append2append2-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(λ (tlposvstate)
v)
#:set(λ (tlposvstate)
(values vstate))
#:insert(λ (tlposvstate)
(values vstate))
#:delete(λ (tlposstate)
state)
#:take(λ (tlposstate)
state)
#:drop(λ (tlposstate)
state)
#:append2(λ (tlotherstateother-state);or #f
(values otherstate))
#:append(λ (tlotherstate)
(values otherstate))
#:prepend(λ (othertlstate)
(values otherstate)))

(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.2Mutable Treelists🔗 i

(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?

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

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

Examples:

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

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

(mutable-treelist 3 "a")

procedure
( mutable-treelist-snapshot tl[nm])→treelist?
tl:mutable-treelist?
n:exact-nonnegative-integer? =0
m:(or/c #fexact-nonnegative-integer? )=#f

Produces an immutable treelist that has the same elements as tl at position n (inclusive) through position m (exclusive). If m is #f, then the length of tl is used, instead. Creating the immutable treelist takes O(N) time for N elements of the resulting treelist, on top of the cost of treelist-sublist if the result is a sublist.

Examples:

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

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

(treelist "a" 'apple)
> (mutable-treelist-snapshot items12)

(treelist "a")
> (mutable-treelist-drop! items2)
> 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 tlpos)→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 items0)

1
> (mutable-treelist-ref items2)

'apple
> (mutable-treelist-ref items3)

mutable-treelist-ref: index is out of range

index: 3

valid range: [0, 2]

mutable treelist: (mutable-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! tlposv)→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! items1"alpha")
> items

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

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

procedure
( mutable-treelist-add! tlv)→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! tlpos)→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! items1)
> items

(mutable-treelist 1 'apple)

procedure
( mutable-treelist-set! tlposv)→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! items1"b")
> items

(mutable-treelist 1 "b" 'apple)

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

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

Modifies tl by appending or prepending 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 O(N) time if other-tl has N elements. If other-tl is an immutable treelist but chaperoned, then appending or prepending 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-prepend! items(treelist 0"b"'banana))
> items

(mutable-treelist 0 "b" 'banana 1 "a" 'apple 'more 'things)
> (mutable-treelist-append! itemsitems)
> items

(mutable-treelist

0

"b"

'banana

1

"a"

'apple

'more

'things

0

"b"

'banana

1

"a"

'apple

'more

'things)

Changed in version 8.15.0.11 of package base: Added mutable-treelist-prepend! .

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

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

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

procedure
( mutable-treelist-drop-right! tln)→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! items2)
> items

(mutable-treelist 1 "a")
> (mutable-treelist-drop-right! items1)
> items

(mutable-treelist 1)

procedure
( mutable-treelist-sublist! tlnm)→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! items13)
> 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! tlproc)→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! itemsbox )
> items

(mutable-treelist '#&1 '#&"a" '#&apple)

procedure
( mutable-treelist-for-each tlproc)→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 itemsprintln )

1

"a"

'apple

procedure
( mutable-treelist-member? tlv[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? items1.0= )

#t

procedure
( mutable-treelist-find tlpred)→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 itemsstring? )

"a"
> (mutable-treelist-find itemssymbol? )

'apple

procedure
( mutable-treelist-sort! tl
less-than?
[ #:keykey
#: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! itemsstring<? )
> 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 maybe-length(for-clause...)body-or-break...body)

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

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

Examples:

> (for/mutable-treelist ([i(in-range 10)])i)

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

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

(mutable-treelist 0 1 2 3 4 5 6 7 8 9 'a 'a 'a 'a 'a)

procedure
( chaperone-mutable-treelist tl
#:refref-proc
#:setset-proc
#:insertinsert-proc
#:appendappend-proc
[ #:prependprepend-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? )

prepend-proc :
(treelist? mutable-treelist?
. -> .treelist? )
= (λ (ot)(append-procto))
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
#:refref-proc
#:setset-proc
#:insertinsert-proc
#:appendappend-proc
[ #:prependprepend-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? )

prepend-proc :
(treelist? mutable-treelist?
. -> .treelist? )
= (λ (ot)(append-procto))
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.

top ← prev up next →