Treelists

Treelists

트리리스트(treelist)는 많은 연산을 O(log N) 시간에 지원하는 방식으로 요소들의 시퀀스를 나타내요: 인덱스로 리스트 요소 접근, 리스트 앞에 추가, 리스트 끝에 추가, 인덱스로 요소 제거, 인덱스로 요소 교체, 리스트 이어붙이기, 시작이나 끝에서 요소 버리기, 하위 리스트 추출 등이 모두 가능하죠. 더 일반적으로, 달리 명시되지 않는 한 길이 N인 트리리스트에 대한 연산은 O(log N) 시간이 걸려요. O(log N)에서 log의 밑은 충분히 커서 많은 목적에서 사실상 상수 시간이에요. 트리리스트는 현재 RRB 트리 [Stucki15]로 구현돼요.

트리리스트는 주로 racket/treelist를 통해 불변 형태로 사용되도록 의도되며, 트리리스트에 추가 같은 연산은 새 트리리스트를 만들어내고 옛 트리리스트는 그대로 유지돼요. 트리리스트의 가변 변형은 racket/mutable-treelist로 제공되며, 가변 트리리스트는 불변 트리리스트를 박스에 넣는 것의 편리한 대안이 될 수 있어요. 달리 명시되지 않는 한 가변 트리리스트 연산은 불변 트리리스트 연산과 같은 시간이 걸려요. "트리리스트"라는 용어가 단독으로 사용되면 불변 트리리스트를 가리켜요.

불변 또는 가변 트리리스트는 단일 값 시퀀스(Sequences 문서 참고)로 사용될 수 있어요. 리스트의 요소들은 시퀀스의 요소로 기능해요. in-treelist와 in-mutable-treelist도 참고하세요. 불변 트리리스트는 스트림으로도 사용될 수 있어요.

base 패키지 8.15.0.3 버전에서 변경됨: 트리리스트를 직렬화(serializable)할 수 있게 만들었어요.

출처: Racket Reference

본문

Immutable Treelists

이 절에 문서화된 바인딩들은 racket/treelist 라이브러리가 제공하며, racket/base나 racket이 제공하는 게 아니에요.

(require racket/treelist) ; package: base

base 패키지 8.12.0.7 버전에서 추가되었어요.

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

procedure

v가 트리리스트이면 #t, 그렇지 않으면 #f를 돌려줘요.

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

procedure

v들을 순서대로 요소로 갖는 트리리스트를 돌려줘요.

이 연산은 N개의 요소로 트리리스트를 만드는 데 O(N log N) 시간이 걸려요.

> (treelist 1 "a" 'apple)

(treelist 1 "a" 'apple)

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

procedure

크기가 size인 트리리스트를 돌려주며, 모든 요소가 v예요. 이 연산은 N개의 요소로 트리리스트를 만드는 데 O(log N) 시간이 걸려요.

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

(treelist 'pear 'pear 'pear)

base 패키지 8.12.0.11 버전에서 추가되었어요.

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

procedure

empty-treelist : (and/c treelist? treelist-empty?)

value

길이가 0인 트리리스트에 대한 술어와 상수예요.

모든 빈 트리리스트는 empty-treelist와 equal?하지만, 트리리스트는 chaperone-treelist를 통해 chaperon 될 수 있으므로 모든 빈 트리리스트가 empty-treelist와 eq?한 것은 아니에요.

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

procedure

tl의 요소 수를 돌려줘요. 이 연산은 O(1) 시간이 걸려요.

> (treelist-length items)

3

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

procedure

tl의 pos번째 요소를 돌려줘요. 첫 번째 요소는 위치 0이고, 마지막 위치는 (treelist-length tl)보다 하나 작아요.

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

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

procedure

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

procedure

트리리스트의 첫 번째 또는 마지막 요소에 접근하기 위해 treelist-ref를 사용하는 단축 표기예요.

> (treelist-last items)

'apple

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

procedure

pos의 요소 앞에 v가 요소로 삽입된 것을 제외하면 tl과 같은 트리리스트를 만들어요. pos가 (treelist-length tl)이면 v가 트리리스트의 끝에 추가돼요.

> (treelist-insert items 3 "alpha")

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

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

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

procedure

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

procedure

트리리스트의 끝이나 시작에 삽입하기 위해 treelist-insert를 사용하는 단축 표기예요.

페어 리스트를 확장하는 주요 연산은 앞에 추가하는 cons이지만, 트리리스트는 treelist-add로 끝에 추가하여 확장하도록 의도되며, treelist-add가 treelist-cons보다 빠른 경향이 있어요.

> (treelist-cons items "alpha")

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

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

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

procedure

pos의 요소가 제거된 것을 제외하면 tl과 같은 트리리스트를 만들어요.

> (treelist-delete items 3)

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

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

procedure

pos의 요소가 v로 교체된 것을 제외하면 tl과 같은 트리리스트를 만들어요. 그 결과는 (treelist-insert (treelist-delete tl pos) pos v)와 동등해요.

> (treelist-set items 1 "b")

(treelist 1 "b" 'apple)

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

procedure

주어진 tl들의 요소들을 단일 트리리스트로 이어붙여요. M개의 트리리스트가 주어지고 결과 트리리스트의 길이가 N이면, 이어붙이는 것은 O(M log N) 시간이 걸려요.

> (treelist-append items (treelist "middle") items)

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

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

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

procedure

각각 처음 n개 요소만 있거나, 처음 n개 요소 없이, 마지막 n개 요소만 있거나, 마지막 n개 요소 없이 tl과 같은 트리리스트를 만들어요.

> (treelist-drop 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)

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

procedure

n 위치(포함)부터 m 위치(제외)까지의 요소만 가진 것을 제외하면 tl과 같은 트리리스트를 만들어요.

> (treelist-sublist items 1 3)

(treelist "a" 'apple)

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

procedure

요소가 뒤집힌 것을 제외하면 tl과 같은 트리리스트를 만들어요. 이는 treelist-take로 0개 요소를 유지한 다음(트리리스트의 chaperone도 함께) 각 요소를 역순으로 다시 추가하는 것과 동등해요. 뒤집기는 O(N log N) 시간이 걸려요.

> (treelist-reverse items)

(treelist 'apple "a" 1)

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

procedure

트리리스트의 첫 번째 요소를 버리기 위해 treelist-drop을 사용하는 단축 표기예요.

treelist-rest 연산은 효율적이지만 rest나 cdr만큼 빠르지는 않아요. 트리리스트를 순회할 때는 대신 treelist-ref 또는 in-treelist가 있는 for 폼을 고려하세요.

> (treelist-rest items)

(treelist "a" 'apple)

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

procedure

트리리스트, 리스트, 벡터 사이를 변환하는 편의 함수예요. 각 변환은 O(N) 시간이 걸려요.

> (treelist->vector items)

'#(1 "a" 'apple)

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

procedure

proc을 tl의 각 요소에 적용하고 그 결과들을 새 트리리스트에 모아 트리리스트를 만들어요. 상수 시간 proc의 경우 이 연산은 O(N) 시간이 걸려요.

> (treelist-map items box)

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

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

procedure

proc을 tl의 각 요소에 적용하고 결과를 무시해요. 상수 시간 proc의 경우 이 연산은 O(N) 시간이 걸려요.

> (treelist-for-each items (λ (x) (displayln x)))

1
"a"
'apple

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

procedure

keep를 만족하는 tl의 멤버만 가진 트리리스트를 만들어요.

> (treelist-filter odd? (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)

base 패키지 8.15.0.6 버전에서 추가되었어요.

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

procedure

eql?와 v(v가 두 번째 인자)로 tl의 각 요소를 결과가 참 값이 될 때까지 검사한 다음 #t를 돌려줘요. 그런 요소가 없으면 결과는 #f예요. 상수 시간 eql?의 경우 이 연산은 O(N) 시간이 걸려요.

> (treelist-member? items "a")

#t
> (treelist-member? items 1.0 =)

#t
> (treelist-member? items 2.0 =)

=: contract violation
  expected: number?
  given: "a"

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

procedure

pred로 tl의 각 요소를 결과가 참 값이 될 때까지 검사한 다음 그 요소를 돌려줘요. 그런 요소가 없으면 결과는 #f예요. 상수 시간 pred의 경우 이 연산은 O(N) 시간이 걸려요.

> (treelist-find items string?)

"a"
> (treelist-find items symbol?)

'apple
> (treelist-find items number->string)

1

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

procedure

tl에서 v에 eql?한 첫 번째 요소의 인덱스를 돌려줘요. 그런 요소가 없으면 결과는 #f예요.

> (treelist-index-of items "a")

0
> (treelist-index-of items 'apple)

1
> (treelist-index-of items 'unicorn)

2
> (treelist-index-of items 'unicorn)

#f

base 패키지 8.15.0.6 버전에서 추가되었어요.

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

procedure

중첩된 트리리스트들의 트리를 단일 트리리스트로 평탄화해요.

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

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

(treelist "a")

base 패키지 8.15.0.6 버전에서 추가되었어요.

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

procedure

트리리스트들의 트리리스트의 요소들을 하나의 트리리스트로 이어붙이고, 더 중첩된 트리리스트들은 그대로 두어요.

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

(treelist "a" "b" "c" (treelist "d") "e")

base 패키지 8.15.0.6 버전에서 추가되었어요.

(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

procedure

sort와 같지만 트리리스트에 대해 동작해 정렬된 트리리스트를 만들어요. 정렬은 O(N log N) 시간이 걸려요.

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

(treelist "a" "q" "x")

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

procedure

tl과 동등한 시퀀스를 돌려줘요. in-treelist 응용이 for 절에 직접 나타나면 트리리스트 순회에 더 나은 성능을 제공할 수 있어요.

> (for/list ([e (in-treelist items)])
    (string-append e "!"))

'("x!" "a!" "q!")

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

procedure

요소들이 s의 요소들인 트리리스트를 돌려주며, 각 요소는 단일 값이어야 해요. s가 무한하면 이 함수는 종료되지 않아요.

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

base 패키지 8.15.0.6 버전에서 추가되었어요.

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

syntax

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

syntax

for/list와 for*/list와 같지만 트리리스트를 생성해요.

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

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

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

procedure

chaperone-vector와 유사하게, tl의 chaperone을 돌려주며, 이는 treelist-ref, treelist-set, treelist-insert, treelist-append, treelist-delete, treelist-take, treelist-drop 연산뿐 아니라 그것들로부터 파생된 연산도 리다이렉트해요. state 인자는 초기 상태이며, 상태 값은 연산을 리다이렉트하는 각 프로시저에 전달되고, (ref-proc는 트리리스트를 갱신하지 않는 유일한 연산에 해당하므로 그것을 제외하면) 갱신된 트리리스트와 연관될 새 상태가 돌려져요. state-key가 제공되면 treelist-chaperone-state와 함께 사용해 원래 트리리스트나 갱신된 트리리스트에서 상태를 추출할 수 있어요.

ref-proc 프로시저는 tl, treelist-ref에 전달된 인덱스, 주어진 인덱스에 대해 tl에 대한 treelist-ref가 만들어내는 값, 그리고 현재 chaperone 상태를 받아들여야 해요. 그리고 chaperone에 대한 treelist-ref의 결과인 그 값에 대한 chaperone 교체물을 만들어야 해요.

set-proc 프로시저는 tl, treelist-set에 전달된 인덱스, treelist-set에 제공된 값, 그리고 현재 chaperone 상태를 받아들여야 해요. 두 값을 만들어야 해요: chaperone에 대한 treelist-set의 결과에서 사용되는 값의 chaperone 교체물과 갱신된 상태. treelist-set의 결과는 tl과 같은 프로시저와 속성으로, 하지만 갱신된 상태로 chaperone 되어요.

insert-proc 프로시저는 set-proc와 같지만 treelist-insert를 통한 삽입용이에요.

delete-proc, take-proc, drop-proc 프로시저는 삭제, 취득, 버리기에 대한 tl, 인덱스 또는 개수, 그리고 현재 chaperone 상태를 받아들여야 하고, 갱신된 상태를 만들어야 해요. treelist-delete, treelist-take, treelist-drop의 결과는 tl과 같은 프로시저와 속성으로, 하지만 갱신된 상태로 chaperone 되어요.

append-proc 프로시저는 tl, tl에 이어붙일 트리리스트, 그리고 현재 chaperone 상태를 받아들여야 해요. chaperone에 대한 treelist-append의 결과로 이어붙여지는 두 번째 트리리스트의 chaperone 교체물과 갱신된 상태를 만들어야 해요. treelist-append의 결과는 tl과 같은 프로시저와 속성으로, 하지만 갱신된 상태로 chaperone 되어요.

prepend-proc 프로시저는 tl과 이어붙일(앞에 둘) 트리리스트, tl, 그리고 현재 chaperone 상태를 받아들여야 해요. chaperone에 대한 treelist-append의 결과로 앞에 놓이는 첫 번째 트리리스트의 chaperone 교체물과 갱신된 상태를 만들어야 해요. treelist-append의 결과는 tl과 같은 프로시저와 속성으로, 하지만 갱신된 상태로 chaperone 되어요.

append2-proc 프로시저는 선택적이며 append-proc와 비슷하지만, 그것이 #f가 아닐 때 treelist-append의 두 번째 인자가 같은 state-key로 chaperone 되면 append-proc 대신 append2-proc가 사용돼요. 그 경우 append2-proc의 두 번째 인자는 state-key chaperone 래퍼가 제거된 두 번째 인자이고, 그 chaperone의 상태가 append2-proc의 마지막 인자예요.

두 개의 chaperone 된 트리리스트가 treelist-append에 주어지고 append2-proc가 사용되지 않으면 첫 번째 트리리스트의 append-proc가 사용되고, append-proc의 결과는 여전히 그 prepend-proc가 사용되는 chaperone이에요. prepend-proc의 결과가 chaperone이면 그 chaperone의 append-proc가 사용되는 식이에요. prepend-proc와 append-proc가 계속 chaperone을 돌려주면 진행이 되지 않을 수도 있어요.

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

(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

procedure

state-key(eq?로 비교)가 초기 상태와 함께 chaperone-treelist에 제공된 트리리스트 chaperone과 연관된 상태를 추출해요. tl이 state-key로 키 지정된 상태를 가진 chaperone이 아니면 fail-k가 호출되고, 기본 fail-k는 exn:fail:contract을 일으켜요.

Mutable Treelists

이 절에 문서화된 바인딩들은 racket/mutable-treelist 라이브러리가 제공하며, racket/base나 racket이 제공하는 게 아니에요.

(require racket/mutable-treelist) ; package: base

가변 트리리스트는 박스 안의 불변 트리리스트와 같으며, 가변 트리리스트를 변경하는 연산은 박스 안의 트리리스트를 교체해요. 특수한 경우로, impersonate 되지 않은 가변 트리리스트에 대한 mutable-treelist-set!은 박스 안 값의 트리리스트 표현을 수정해요. 이 가변 트리리스트 모델은 동시 수정의 경우에서 그 동작을 설명해요: 서로 다른 위치에 대한 동시 mutable-treelist-set! 연산은 간섭하지 않지만, 다른 연산과의 경쟁이나 impersonate 된 가변 트리리스트에 대한 경쟁은 때때로 수정 중 하나를 무효화해요. 따라서 동시 수정은 다소 예측 불가능하지만 여전히 안전하며, 잠금으로 관리되지 않아요.

가변 트리리스트는 treelist?의 의미에서 트리리스트가 아니며, treelist?는 불변 트리리스트만 인식해요. 달리 명시되지 않는 한 가변 트리리스트에 대한 연산은 불변 트리리스트에 대한 대응 연산과 같은 시간 복잡도를 가져요.

base 패키지 8.12.0.7 버전에서 추가되었어요.

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

procedure

v가 가변 트리리스트이면 #t, 그렇지 않으면 #f를 돌려줘요.

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

procedure

v들을 순서대로 요소로 갖는 가변 트리리스트를 돌려줘요.

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

(mutable-treelist 1 "a" 'apple)

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

procedure

n개의 요소를 포함하는 가변 트리리스트를 만들며, 각 요소는 v로 초기화돼요. 가변 트리리스트를 만드는 것은 N개의 요소에 대해 O(N) 시간이 걸려요.

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

(mutable-treelist "a" "a" "a")

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

procedure

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

procedure

tl과 같은 요소를 포함하는 가변 트리리스트를 만들어요. 가변 트리리스트를 만드는 것은 N개의 요소에 대해 O(N) 시간이 걸려요.

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

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

(mutable-treelist 3 "a")

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

procedure

n 위치(포함)부터 m 위치(제외)까지 tl과 같은 요소를 가진 불변 트리리스트를 만들어요. m이 #f이면 대신 tl의 길이가 사용돼요. 불변 트리리스트를 만드는 것은 결과 트리리스트의 N개 요소에 대해, 결과가 하위 리스트라면 treelist-sublist 비용에 더해 O(N) 시간이 걸려요.

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

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

(treelist "a" 'apple)
> (mutable-treelist-drop! items 2)
> items

(mutable-treelist 'apple)
> snap

(treelist 1 "a" 'apple)

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

procedure

현재 길이가 0인 가변 트리리스트에 대해 #t, 그렇지 않으면 #f를 돌려줘요.

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

procedure

현재 tl에 있는 요소의 수를 돌려줘요.

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

3
> (mutable-treelist-add! items 'extra)
> (mutable-treelist-length items)

4

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

procedure

tl의 pos번째 요소를 돌려줘요. 첫 번째 요소는 위치 0이고, 마지막 위치는 (mutable-treelist-length tl)보다 하나 작아요.

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-ref items 2)

'apple
> (mutable-treelist-ref items 3)

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

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

procedure

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

procedure

트리리스트의 첫 번째 또는 마지막 요소에 접근하기 위해 mutable-treelist-ref를 사용하는 단축 표기예요.

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

'apple

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

procedure

pos 위치 전에 v를 리스트에 삽입하도록 tl을 수정해요. pos가 (mutable-treelist-length tl)이면 v가 트리리스트의 끝에 추가돼요.

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

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

(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

procedure

트리리스트의 시작 또는 끝에 삽입하기 위해 mutable-treelist-insert!를 사용하는 단축 표기예요.

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

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

procedure

pos의 요소를 제거하도록 tl을 수정해요.

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

(mutable-treelist 1 'apple)

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

procedure

pos의 요소를 v로 바꾸도록 tl을 수정해요.

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

(mutable-treelist 1 "b" 'apple)

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

procedure

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

procedure

other-tl의 모든 요소를 이어붙이거나 앞에 놓도록 tl을 수정하며, other-tl이 N개의 요소를 가진다면 O(N) 시간이 걸려요.

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

base 패키지 8.15.0.11 버전에서 변경됨: mutable-treelist-prepend!가 추가되었어요. 9.2.0.2 버전에서 변경됨: 구현 수선으로 항상 O(N) 시간이 된다는 의미가 되었어요.

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

procedure

각각 처음 n개 요소를 제외한 모두를 제거하거나, 처음 n개 요소를 제거하거나, 마지막 n개 요소를 제외한 모두를 제거하거나, 마지막 n개 요소를 제거하도록 tl을 수정해요.

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

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

(mutable-treelist 1)

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

procedure

n 위치(포함)부터 m 위치(제외)까지의 요소 이외의 요소를 제거하도록 tl을 수정해요.

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

(mutable-treelist "a" 'apple)

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

procedure

모든 요소를 뒤집도록 tl을 수정해요.

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

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

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

procedure

가변 트리리스트, 리스트, 벡터 사이를 변환하는 편의 함수예요. 각 변환은 O(N) 시간이 걸려요.

> (mutable-treelist->vector items)

'#(1 "a" 'apple)

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

procedure

proc을 tl의 각 요소에 적용하고 그 결과를 요소 자리에 설치하도록 tl을 수정해요.

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

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

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

procedure

treelist-for-each와 같지만 가변 트리리스트용이에요.

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-for-each items (λ (x) (displayln x)))

1
"a"
'apple

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

procedure

treelist-member?와 같지만 가변 트리리스트용이에요.

> (define items (mutable-treelist 1 "a" 'apple))
> (mutable-treelist-member? items "a")

#t
> (mutable-treelist-member? items 1.0 =)

#t

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

procedure

treelist-find와 같지만 가변 트리리스트용이에요.

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

"a"
> (mutable-treelist-find items symbol?)

'apple

(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

procedure

vector-sort!와 같지만 가변 트리리스트에 대해 동작해요.

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

(mutable-treelist "a" "q" "x")

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

procedure

tl과 동등한 시퀀스를 돌려줘요. in-mutable-treelist 응용이 for 절에 직접 나타나면 가변 트리리스트 순회에 더 나은 성능을 제공할 수 있어요.

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

'("x!" "a!" "q!")

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

syntax

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

syntax

for/vector와 for*/vector와 같지만 가변 트리리스트를 생성해요.

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

(chaperone-mutable-treelist tl
                           #:ref ref-proc
                           #:set set-proc
                           #:insert insert-proc
                           #:append append-proc
                           [#:prepend prepend-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?)
          = (λ (o t) (append-proc t o))
prop        : impersonator-property?
prop-val    : any/c

procedure

chaperone-treelist와 비슷하지만 가변 트리리스트용이에요. 예를 들어 주어진 set-proc가 mutable-treelist-set!에 사용되고, 결과 값이 set-proc에 제공된 것 대신 가변 트리리스트에 설치돼요. 가변 트리리스트 chaperone은 트리리스트 자신과 분리된 상태를 가지지 않으며, set-proc 같은 프로시저가 상태를 소비하거나 돌려주지 않아요.

(impersonate-mutable-treelist tl
                              #:ref ref-proc
                              #:set set-proc
                              #:insert insert-proc
                              #:append append-proc
                              [#:prepend prepend-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?)
          = (λ (o t) (append-proc t o))
prop        : impersonator-property?
prop-val    : any/c

procedure

chaperone-mutable-treelist와 같지만 ref-proc, set-proc, insert-proc, append-proc가 chaperone을 만들어야 할 의무가 없어요.

더 알아보기