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.
4.16.1 Immutable Treelists
(require racket/treelist) | package: base |
Added in version 8.12.0.7 of package base.
This operation takes O(N log N) time to construct a treelist of N elements.
> (treelist 1 "a" 'apple) (treelist 1 "a" 'apple)
procedure
(make-treelist size v) → treelist?
size : exact-nonnegative-integer? v : any/c
> (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
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
tl : treelist?
> (define items (treelist 1 "a" 'apple)) > (treelist-length items) 3
procedure
(treelist-ref tl pos) → any/c
tl : treelist? pos : exact-nonnegative-integer?
> (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?
> (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
> (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
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.
> (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?
> (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
> (define items (treelist 1 "a" 'apple)) > (treelist-set items 1 "b") (treelist 1 "b" 'apple)
procedure
(treelist-append tl ...) → treelist?
tl : treelist?
> (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?
> (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?
> (define items (treelist 1 "a" 'apple)) > (treelist-sublist items 1 3) (treelist "a" 'apple)
procedure
(treelist-reverse tl) → treelist?
tl : treelist?
> (define items (treelist 1 "a" 'apple)) > (treelist-reverse items) (treelist 'apple "a" 1)
procedure
(treelist-rest tl) → treelist?
tl : 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.
> (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?
> (define items (list->treelist '(1 "a" 'apple))) > (treelist->vector items) '#(1 "a" 'apple)
> (define items (treelist 1 "a" 'apple)) > (treelist-map items box) (treelist '#&1 '#&"a" '#&apple)
> (define items (treelist 1 "a" 'apple)) > (treelist-for-each items println)
1
"a"
'apple
procedure
(treelist-member? tl v [eql?]) → boolean?
tl : treelist? v : any/c eql? : (any/c any/c . -> . any/c) = equal?
> (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"
> (define items (treelist 1 "a" 'apple)) > (treelist-find items string?) "a"
> (treelist-find items symbol?) 'apple
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
> (define items (treelist "x" "a" "q")) > (treelist-sort items string<?) (treelist "a" "q" "x")
procedure
(in-treelist tl) → sequence?
tl : treelist?
> (define items (treelist "x" "a" "q"))
> (for/list ([e (in-treelist items)]) (string-append e "!")) '("x!" "a!" "q!")
syntax
(for/treelist (for-clause ...) body-or-break ... body)
syntax
(for*/treelist (for-clause ...) body-or-break ... body)
> (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
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.
> (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
4.16.2 Mutable Treelists
(require racket/mutable-treelist) | package: base |
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
procedure
(mutable-treelist v ...) → treelist?
v : any/c
> (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
> (make-mutable-treelist 3 "a") (mutable-treelist "a" "a" "a")
procedure
(treelist-copy tl) → mutable-treelist?
tl : treelist?
> (treelist-copy (treelist 3 "a")) (mutable-treelist 3 "a")
procedure
tl : mutable-treelist?
> (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?
procedure
tl : mutable-treelist?
> (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?
> (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?
> (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
> (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
> (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?
> (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
> (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?)
> (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?
> (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?
> (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?
> (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
vec : vector?
procedure
lst : list?
> (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)
> (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)
> (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?
> (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)
> (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
> (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?
> (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)
> (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
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