4.16 Treelists (original) (raw)
8.17
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 thelog 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 viaracket/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 byracket/mutable-treelist, where a mutable treelist can be a convenient alternative to putting an immutable treelist into abox. 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 andin-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🔗ℹ
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.
Returns #t if v is a treelist, #fotherwise.
Returns a treelist with vs as its elements in order.
This operation takes O(N log N) time to construct a treelist ofN elements.
Example:
> (treelist 1 "a" 'apple) (treelist 1 "a" 'apple)
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.
A predicate and constant for a treelist of length 0.
Although every empty treelist is equal? toempty-treelist, since a treelist can be chaperoned viachaperone-treelist, not every empty treelist is eq?to empty-treelist.
Returns the number of elements in tl. This operation takesO(1) time.
Examples:
> (define items (treelist 1 "a" 'apple)) > (treelist-length items) 3
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)
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
Produces a treelist like tl, except that v is inserted as an element before the element at pos. Ifpos 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")
Shorthands for using treelist-insert to insert at the end or beginning of a treelist.
Although the main operation to extend a pair list iscons to add to the front, treelists are intended to be extended by adding to the end with treelist-add, andtreelist-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)
Produces a treelist like tl, except that the element atpos 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)
Produces a treelist like tl, except that the element atpos 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)
(treelist-append tl ...) → treelist? tl : treelist?
Appends the elements of the given tls into a singletreelist. 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)
Produces a treelist like tl but with only the firstn 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)
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)
Produces a treelist like tl but with its elements reversed, equivalent to using treelist-take to keep0 elements (but also any chaperone on the treelist) and then adding each element back in reverse order. Reversing takesO(N log N) time.
Examples:
> (define items (treelist 1 "a" 'apple)) > (treelist-reverse items) (treelist 'apple "a" 1)
A shorthand for using treelist-drop to drop the first element of a treelist.
The treelist-rest operation is efficient, but not as fast asrest or cdr. For iterating through a treelist, consider using treelist-ref or a for form within-treelist, instead.
Examples:
> (define items (treelist 1 "a" 'apple)) > (treelist-rest items) (treelist "a" 'apple)
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)
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)
Applies proc to each element of tl, ignoring the results. For a constant-time proc, this operation takesO(N) time.
Examples:
Produces a treelist with only members of tl that satisfykeep.
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.
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"
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-timepred, this operation takes O(N) time.
Examples:
Returns the index of the first element in tl that iseql? 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.
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.
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.
Like sort, but operates on a treelist to produce a sorted treelist. Sorting takes O(N log N) time.
Examples:
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")) '("x!" "a!" "q!")
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:
Added in version 8.15.0.6 of package base.
(for/treelist (for-clause ...) body-or-break ... body) (for*/treelist (for-clause ...) body-or-break ... body)
Example:
(treelist 0 1 2 3 4 5 6 7 8 9)
(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) prop : impersonator-property? prop-val : any/c
Analogous to chaperone-vector, returns a chaperone oftl, which redirects the treelist-ref,treelist-set, treelist-insert,treelist-append, treelist-delete,treelist-take, and treelist-dropoperations, 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-keyis provided, it can be used with treelist-chaperone-stateto 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 thattreelist-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 totreelist-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-procprocedures 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-appendon the chaperone, and an updated state. The result oftreelist-append is chaperoned with the same procedures and properties as tl, but with the updated state.
The append2-proc procedure is optional and similar toappend-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 toappend2-proc is the second argument with a state-keychaperone wrapper removed, and with that chaperone’s state as the last argument to append2-proc.
When two chaperoned treelists are given to treelist-appendand append2-proc is not used, then the append-procof 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’sappend-proc is used, and so on. If prepend-proc andappend-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)
Extracts state associated with a treelist chaperone wherestate-key (compared using eq?) was provided along with the initial state tochaperone-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🔗ℹ
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 oftreelist?, 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.
Returns #t if v is a mutable treelist,#f otherwise.
Returns a mutable treelist with vs as its elements in order.
Example:
> (mutable-treelist 1 "a" 'apple) (mutable-treelist 1 "a" 'apple)
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")
Creates a mutable treelist that contains the same elements astl. Creating the mutable treelist takes O(N) time forN elements.
Examples:
> (treelist-copy (treelist 3 "a")) (mutable-treelist 3 "a") > (mutable-treelist-copy (mutable-treelist 3 "a")) (mutable-treelist 3 "a")
Produces an immutable treelist that has the same elements astl at position n (inclusive) through positionm (exclusive). If m is #f, then the length of tl is used, instead. Creating the immutable treelist takesO(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 items 1) (treelist "a" 'apple) > (mutable-treelist-snapshot items 1 2) (treelist "a") > (mutable-treelist-drop! items 2) > items (mutable-treelist 'apple) > snap (treelist 1 "a" 'apple)
Returns #t for mutable treelist that is currently of length 0, #f otherwise.
Returns the number of elements currently in tl.
Examples:
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] mutable treelist: (mutable-treelist 1 "a" 'apple)
Shorthands for using mutable-treelist-ref to access the first or last element of a treelist.
Examples:
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)
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")
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)
Modifies tl to change the element at pos tov.
Examples:
> (define items (mutable-treelist 1 "a" 'apple)) > (mutable-treelist-set! items 1 "b") > items (mutable-treelist 1 "b" 'apple)
Modifies tl by appending or prepending all of the elements ofother-tl. If other-tl is a mutable treelist, it is first converted to an immutable treelist withmutable-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 takesO(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! items items) > 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!.
Modifies tl to remove all but the first n elements, to remove the first n elements, to remove all but the lastn 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)
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)
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)
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)
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)
Like treelist-for-each, but for a mutable treelist.
Examples:
Like treelist-member?, but for a mutable treelist.
Examples:
Like treelist-find, but for a mutable treelist.
Examples:
Examples:
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")) '("x!" "a!" "q!")
(for/mutable-treelist maybe-length (for-clause ...) body-or-break ... body) (for*/mutable-treelist maybe-length (for-clause ...) body-or-break ... body)
Examples:
> (for/mutable-treelist ([i (in-range 10)]) i) (mutable-treelist 0 1 2 3 4 5 6 7 8 9) > (for/mutable-treelist #:length 15 ([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 #:length 15 #:fill 'a ([i (in-range 10)]) i) (mutable-treelist 0 1 2 3 4 5 6 7 8 9 'a 'a 'a 'a 'a)
Similar to chaperone-treelist, but for mutable treelists. For example, the given set-proc is used formutable-treelist-set!, and the resulting value is installed into the mutable treelist instead of the one provided toset-proc. Mutable treelist chaperones do not have state separate from the treelist itself, and procedures likeset-proc do not consume or return a state.
Like chaperone-mutable-treelist, but ref-proc,set-proc, insert-proc, and append-procare not obligated to produce chaperones.