집합

집합 (Sets)

집합은 서로 다른(distinct) 요소들의 모임을 나타냅니다. 해시 집합, equal?로 요소를 비교하는 리스트, 그리고 gen:set 제네릭 인터페이스를 구현하는 구조체의 타입이 모두 집합입니다.

출처: Racket Reference

본문

집합은 서로 다른 요소들의 모임을 나타냅니다. 다음 데이터 타입들이 모두 집합입니다:

해시 집합(hash set);
equal?로 요소를 비교하는 리스트;
gen:set 제네릭 인터페이스를 구현하는 타입의 구조체.

(require racket/set) ; package: base

이 섹션에 문서화된 바인딩은 racket/set과 racket 라이브러리가 제공하지만, racket/base는 제공하지 않습니다.

Hash Sets

해시 집합은 equal?, equal-always?, eqv?, eq?로 요소를 비교하고, equal-hash-code, equal-always-hash-code, eqv-hash-code, eq-hash-code로 분할하는 집합입니다. 해시 집합은 불변이거나 가변이며, 가변 해시 집합은 요소를 강하게(strongly) 또는 약하게(weakly) 보유합니다.

불변 해시 테이블에 대한 연산처럼, "상수 시간" 해시 집합 연산은 실제로 크기 N의 집합에 대해 O(log N) 시간이 걸립니다.

해시 집합은 스트림(Streams 참고)으로 사용될 수 있고, 따라서 단일 값 시퀀스(Sequences 참고)로도 사용될 수 있습니다. 집합의 요소들이 스트림 또는 시퀀스의 요소 역할을 합니다. 반복 중에 요소가 해시 집합에 추가되거나 제거되면, 반복 단계가 exn:fail:contract로 실패하거나, 반복이 요소를 건너뛰거나 중복할 수 있습니다. in-set도 참고하세요.

두 해시 집합은 같은 요소-비교 절차(equal?, equal-always?, eqv?, eq?)를 사용하고, 둘 다 요소를 강하게 또는 약하게 보유하며, 같은 가변성을 갖고, 동등한 요소들을 가질 때 서로 equal?입니다.

불변 해시 집합은 가변 해시 집합처럼 사실상 상수 시간 접근과 갱신을 지원합니다. 불변 연산의 상수는 보통 더 크지만, 불변 해시 집합의 함수형 특성은 특정 알고리즘에서 이점을 줄 수 있습니다.

모든 해시 집합은 set->stream, set-empty?, set-member?, set-count, subset?, proper-subset?, set-map, set-for-each, set-copy, set-copy-clear, set->list, set-first를 구현합니다. 불변 해시 집합은 추가로 set-add, set-remove, set-clear, set-union, set-intersect, set-subtract, set-symmetric-difference를 구현합니다. 가변 해시 집합은 추가로 set-add!, set-remove!, set-clear!, set-union!, set-intersect!, set-subtract!, set-symmetric-difference!를 구현합니다.

변이되는 요소를 포함하는 집합에 대한 연산은, 키가 변이될 때 해시 테이블 연산이 예측 불가능한 것과 같은 방식으로 예측 불가능합니다.

procedure

(set-equal? x) → boolean?
  x : any/c

procedure

(set-equal-always? x) → boolean?
  x : any/c

procedure

(set-eqv? x) → boolean?
  x : any/c

procedure

(set-eq? x) → boolean?
  x : any/c

각각 x가 equal?, equal-always?, eqv?, eq?로 요소를 비교하는 해시 집합이면 #t를, 그렇지 않으면 #f를 반환합니다.

base 패키지의 8.5.0.3 버전에서 변경됨: set-equal-always? 추가.

procedure

(set? x) → boolean?
  x : any/c

procedure

(set-mutable? x) → boolean?
  x : any/c

procedure

(set-weak? x) → boolean?
  x : any/c

각각 x가 불변이거나, 키를 강하게 보유한 가변이거나, 키를 약하게 보유한 가변인 해시 집합이면 #t를, 그렇지 않으면 #f를 반환합니다.

procedure

(set v ...) → (and/c generic-set? set-equal? set?)
  v : any/c

procedure

(setalw v ...) → (and/c generic-set? set-equal-always? set?)
  v : any/c

procedure

(seteqv v ...) → (and/c generic-set? set-eqv? set?)
  v : any/c

procedure

(seteq v ...) → (and/c generic-set? set-eq? set?)
  v : any/c

procedure

(mutable-set v ...)
→ (and/c generic-set? set-equal? set-mutable?)
  v : any/c

procedure

(mutable-setalw v ...)
→ (and/c generic-set? set-equal-always? set-mutable?)
  v : any/c

procedure

(mutable-seteqv v ...)
→ (and/c generic-set? set-eqv? set-mutable?)
  v : any/c

procedure

(mutable-seteq v ...)
→ (and/c generic-set? set-eq? set-mutable?)
  v : any/c

procedure

(weak-set v ...) → (and/c generic-set? set-equal? set-weak?)
  v : any/c

procedure

(weak-setalw v ...)
→ (and/c generic-set? set-equal-always? set-weak?)
  v : any/c

procedure

(weak-seteqv v ...) → (and/c generic-set? set-eqv? set-weak?)
  v : any/c

procedure

(weak-seteq v ...) → (and/c generic-set? set-eq? set-weak?)
  v : any/c

주어진 v들을 요소로 하는 해시 집합을 만듭니다. 요소들은 인자로 나타난 순서대로 추가되므로, equal?, equal-always?, eqv?를 사용하는 집합의 경우, 앞선 요소가 그 뒤에 나오는 equal?, equal-always?, eqv?이지만 eq?는 아닌 요소로 대체될 수 있습니다.

base 패키지의 8.5.0.3 버전에서 변경됨: setalw, mutable-setalw, weak-setalw 추가.

procedure

(list->set lst) → (and/c generic-set? set-equal? set?)
  lst : list?

procedure

(list->setalw lst)
→ (and/c generic-set? set-equal-always? set?)
  lst : list?

procedure

(list->seteqv lst) → (and/c generic-set? set-eqv? set?)
  lst : list?

procedure

(list->seteq lst) → (and/c generic-set? set-eq? set?)
  lst : list?

procedure

(list->mutable-set lst)
→ (and/c generic-set? set-equal? set-mutable?)
  lst : list?

procedure

(list->mutable-setalw lst)
→ (and/c generic-set? set-equal-always? set-mutable?)
  lst : list?

procedure

(list->mutable-seteqv lst)
→ (and/c generic-set? set-eqv? set-mutable?)
  lst : list?

procedure

(list->mutable-seteq lst)
→ (and/c generic-set? set-eq? set-mutable?)
  lst : list?

procedure

(list->weak-set lst)
→ (and/c generic-set? set-equal? set-weak?)
  lst : list?

procedure

(list->weak-setalw lst)
→ (and/c generic-set? set-equal-always? set-weak?)
  lst : list?

procedure

(list->weak-seteqv lst)
→ (and/c generic-set? set-eqv? set-weak?)
  lst : list?

procedure

(list->weak-seteq lst) → (and/c generic-set? set-eq? set-weak?)
  lst : list?

주어진 lst의 요소들을 집합의 요소로 하는 해시 집합을 만듭니다. 각각 (apply set lst), (apply setalw lst), (apply seteqv lst), (apply seteq lst) 등과 동등합니다.

base 패키지의 8.5.0.3 버전에서 변경됨: list->setalw, list->mutable-setalw, list->weak-setalw 추가.

syntax

(for/set (for-clause ...) body ...+)

syntax

(for/seteq (for-clause ...) body ...+)

syntax

(for/seteqv (for-clause ...) body ...+)

syntax

(for/setalw (for-clause ...) body ...+)

syntax

(for*/set (for-clause ...) body ...+)

syntax

(for*/seteq (for-clause ...) body ...+)

syntax

(for*/seteqv (for-clause ...) body ...+)

syntax

(for*/setalw (for-clause ...) body ...+)

syntax

(for/mutable-set (for-clause ...) body ...+)

syntax

(for/mutable-seteq (for-clause ...) body ...+)

syntax

(for/mutable-seteqv (for-clause ...) body ...+)

syntax

(for/mutable-setalw (for-clause ...) body ...+)

syntax

(for*/mutable-set (for-clause ...) body ...+)

syntax

(for*/mutable-seteq (for-clause ...) body ...+)

syntax

(for*/mutable-seteqv (for-clause ...) body ...+)

syntax

(for*/mutable-setalw (for-clause ...) body ...+)

syntax

(for/weak-set (for-clause ...) body ...+)

syntax

(for/weak-seteq (for-clause ...) body ...+)

syntax

(for/weak-seteqv (for-clause ...) body ...+)

syntax

(for/weak-setalw (for-clause ...) body ...+)

syntax

(for*/weak-set (for-clause ...) body ...+)

syntax

(for*/weak-seteq (for-clause ...) body ...+)

syntax

(for*/weak-seteqv (for-clause ...) body ...+)

syntax

(for*/weak-setalw (for-clause ...) body ...+)

for/list과 for*/list와 유사하지만, 리스트 대신 해시 집합을 만든다는 점이 다릅니다.

base 패키지의 8.5.0.3 버전에서 변경됨: for/setalw, for/mutable-setalw, for/weak-setalw 추가.

procedure

(in-immutable-set st) → sequence?
  st : set?

procedure

(in-mutable-set st) → sequence?
  st : set-mutable?

procedure

(in-weak-set st) → sequence?
  st : set-weak?

특정 종류의 해시 집합을 for 폼과 함께 쓰기 위해 명시적으로 시퀀스로 변환합니다.

in-list와 다른 일부 시퀀스 생성자처럼, in-immutable-set은 for 절에 직접 나타나면 더 좋은 성능을 냅니다.

이 시퀀스 생성자들은 Custom Hash Sets와 호환됩니다.

base 패키지의 6.4.0.7 버전에서 추가되었습니다.

Set Predicates and Contracts

procedure

(generic-set? v) → boolean?
  v : any/c

v가 집합이면 #t를, 그렇지 않으면 #f를 반환합니다.

예시:

> (generic-set? (list 1 2 3))

#t
> (generic-set? (set 1 2 3))

#t
> (generic-set? (mutable-seteq 1 2 3))

#t
> (generic-set? (vector 1 2 3))

#f

procedure

(set-implements? st sym ...) → boolean?
  st : generic-set?
  sym : symbol?

st가 sym들이 이름 짓는 gen:set의 모든 메서드를 구현하면 #t를, 그렇지 않으면 #f를 반환합니다. 폴백(fallback) 구현은 결과에 영향을 주지 않습니다. st가 폴백 구현을 통해 주어진 메서드들을 지원하면서도 #f를 만들어낼 수 있습니다.

예시:

> (set-implements? (list 1 2 3) 'set-add)

#t
> (set-implements? (list 1 2 3) 'set-add!)

#f
> (set-implements? (set 1 2 3) 'set-add)

#t
> (set-implements? (set 1 2 3) 'set-add!)

#t
> (set-implements? (mutable-seteq 1 2 3) 'set-add)

#t
> (set-implements? (mutable-seteq 1 2 3) 'set-add!)

#t
> (set-implements? (weak-seteqv 1 2 3) 'set-remove 'set-remove!)

#t

procedure

(set-implements/c sym ...) → flat-contract?
  sym : symbol?

sym들이 이름 짓는 gen:set의 모든 메서드를 지원하는 집합들을 인식합니다.

procedure

(set/c elem/c
  [#:cmp cmp
  #:kind kind
  #:lazy? lazy?
  #:equal-key/c equal-key/c]) → contract?

  elem/c : chaperone-contract?
  cmp : (or/c 'dont-care 'equal 'equal-always 'eqv 'eq)
   = 'dont-care

  kind : (or/c 'dont-care 'immutable 'mutable 'weak 'mutable-or-weak)
   = 'immutable

  lazy? : any/c = (not (and (equal? kind 'immutable)
          (flat-contract? elem/c)))

  equal-key/c : contract? = any/c

요소들이 elem/c와 일치하는 집합들을 인식하는 계약을 구성합니다.

kind가 'immutable, 'mutable, 'weak이면, 결과 계약은 각각 불변이거나, 키를 강하게 보유한 가변이거나, 키를 약하게 보유한 가변인 해시 집합만 받아들입니다. kind가 'mutable-or-weak이면, 결과 계약은 키 보유 강도와 관계없이 어떤 가변 해시 집합이든 받아들입니다.

cmp가 'equal, 'equal-always, 'eqv, 'eq이면, 결과 계약은 각각 equal?, equal-always?, eqv?, eq?로 요소를 비교하는 해시 집합만 받아들입니다.

cmp가 'eqv 또는 'eq이면, elem/c는 플랫 계약이어야 합니다.

cmp와 kind가 둘 다 'dont-care이면, 결과 계약은 해시 집합뿐 아니라 어떤 종류의 집합이든 받아들입니다.

lazy?가 #f가 아니면, 집합의 요소들은 계약이 즉시 검사하지 않고 집합 자체만(기타 cmp와 kind 인자에 따라) 검사합니다. lazy?가 #f이면, 요소들이 계약에 의해 즉시 검사됩니다. lazy? 인자는 집합 계약이 제네릭 집합을 받아들일 때(즉 cmp와 kind가 둘 다 'dont-care일 때) 무시됩니다. 그 경우, 그때 검사되는 값이 list?이면 계약은 lazy 하지 않고, 그렇지 않으면 lazy 합니다.

kind가 가변 집합을 허용하고('dont-care, 'mutable, 'weak, 'mutable-or-weak) lazy?가 #f이면, 요소들은 즉시 그리고 집합에서 접근될 때 모두 검사됩니다.

equal-key/c 계약은 값들이 내부적으로 사용되는 비교 및 해싱 함수에 전달될 때 사용됩니다.

결과 계약은 elem/c와 equal-key/c가 둘 다 플랫 계약이고, lazy?가 #f이며, kind가 'immutable일 때 플랫 계약이 됩니다. elem/c가 채퍼론 계약이면 결과는 채퍼론 계약이 됩니다.

base 패키지의 8.3.0.9 버전에서 변경됨: 무작위 생성(random generation) 지원 추가. 8.5.0.3 버전에서 변경됨: cmp에 대한 'equal-always 지원 추가.

Generic Set Interface

syntax

gen:set

struct 정의의 #:methods 옵션을 통해 구조체 타입에 집합 메서드 구현을 공급하는 제네릭 인터페이스(Generic Interfaces 참고)입니다. 이 인터페이스는 Set Methods로 문서화된 메서드들 중 어떤 것이든 구현하는 데 사용될 수 있습니다.

집합은 또한 시퀀스여야 하지만, gen:set 그 자체는 prop:sequence를 함의하지 않습니다. gen:set의 사용은 보통 in-set과 함께 prop:sequence의 사용과 결합되어야 합니다. in-set은 set->stream(예: set->stream을 구현하거나, set-first, set-remove, set-empty? 같은 다른 지원 조합)을 지원해야 합니다.

예시:

> (struct binary-set [integer]
    #:transparent
    #:methods gen:set
    [(define (set-member? st i)
       (bitwise-bit-set? (binary-set-integer st) i))
     (define (set-add st i)
       (binary-set (bitwise-ior (binary-set-integer st)
                                (arithmetic-shift 1 i))))
     (define (set-remove st i)
       (binary-set (bitwise-and (binary-set-integer st)
                                (bitwise-not (arithmetic-shift 1 i)))))
     (define (set-first st)
       (sub1 (integer-length (binary-set-integer st))))
     (define (set-empty? st)
       (= (binary-set-integer st) 0))]
    #:property prop:sequence in-set)

> (define bset (binary-set 5))
> bset

(binary-set 5)
> (generic-set? bset)

#t
> (set-member? bset 0)

#t
> (set-member? bset 1)

#f
> (set-member? bset 2)

#t
> (set-add bset 4)

(binary-set 21)
> (set-remove bset 2)

(binary-set 1)
> (set-first bset)

2
> (require racket/sequence)
> (sequence->list bset)

'(2 0)

Set Methods

gen:set의 메서드들은 폴백 구현에 따라 세 범주로 분류될 수 있습니다:

폴백이 없는 메서드,
폴백이 다른 비-폴백 메서드에 의존하는 메서드,
그리고 폴백이 폴백 또는 비-폴백 메서드 어느 쪽에든 의존할 수 있는 메서드.

예를 들어, 다음 메서드들을 구현하면 gen:set의 모든 메서드가 적어도 폴백 메서드를 갖도록 보장할 수 있습니다:

set-member?
set-add
set-add!
set-remove
set-remove!
set-first
set-empty?
set-copy-clear

모든 메서드에 적어도 폴백을 보장하는 다른 메서드 부분 집합들도 있을 수 있습니다.

procedure

(set-member? st v) → boolean?
  st : generic-set?
  v : any/c

v가 st에 있으면 #t를, 그렇지 않으면 #f를 반환합니다. 폴백이 없습니다.

procedure

(set-add st v) → generic-set?
  st : generic-set?
  v : any/c

v에 st의 모든 요소를 더한 집합을 만들어냅니다. 이 연산은 해시 집합에 대해 상수 시간으로 동작합니다. 폴백이 없습니다.

procedure

(set-add! st v) → void?
  st : generic-set?
  v : any/c

요소 v를 st에 추가합니다. 이 연산은 해시 집합에 대해 상수 시간으로 동작합니다. 폴백이 없습니다.

해시 집합의 경우, 해시 테이블의 동시 수정(concurrent modification)에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set-remove st v) → generic-set?
  st : generic-set?
  v : any/c

v를 제외한 st의 모든 요소를 포함하는 집합을 만들어냅니다. 이 연산은 해시 집합에 대해 상수 시간으로 동작합니다. 폴백이 없습니다.

procedure

(set-remove! st v) → void?
  st : generic-set?
  v : any/c

st에서 요소 v를 제거합니다. 이 연산은 해시 집합에 대해 상수 시간으로 동작합니다. 폴백이 없습니다.

해시 집합의 경우, 해시 테이블의 동시 수정에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set-empty? st) → boolean?
  st : generic-set?

st에 구성원이 없으면 #t를, 그렇지 않으면 #f를 반환합니다.

set->stream이나 set-count를 구현하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-count st) → exact-nonnegative-integer?
  st : generic-set?

st의 요소 수를 반환합니다.

set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-first st) → any/c
  st : (and/c generic-set? (not/c set-empty?))

st의 불특정 요소를 만들어냅니다. st에 대한 set-first의 여러 사용은 같은 결과를 만들어냅니다.

set->stream을 구현하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-rest st) → generic-set?
  st : (and/c generic-set? (not/c set-empty?))

(set-first st)를 제외한 st의 모든 요소를 포함하는 집합을 만들어냅니다.

set-remove와 set-first 또는 set->stream 중 하나를 구현하는 어떤 st에 대해서도 지원됩니다.

procedure

(set->stream st) → stream?
  st : generic-set?

st의 요소들을 포함하는 스트림을 만들어냅니다.

다음을 구현하는 어떤 st에 대해서도 지원됩니다:

set->list
in-set
set-empty?, set-first, set-rest
set-empty?, set-first, set-remove
set-count, set-first, set-rest
set-count, set-first, set-remove

procedure

(set-copy st) → generic-set?
  st : generic-set?

st와 같은 타입이고 같은 요소를 가진 새 가변 집합을 만들어냅니다.

set->stream을 지원하고 set-copy-clear와 set-add!를 구현하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-copy-clear st) → (and/c generic-set? set-empty?)
  st : generic-set?

st와 같은 타입, 같은 가변성, 같은 키 강도를 가진 새 빈 집합을 만들어냅니다.

set-copy-clear와 set-clear의 차이는, 후자가 개념적으로 주어진 집합에 대해 set-remove를 반복하므로 주어진 집합의 어떤 계약도 보존한다는 것입니다. set-copy-clear 함수는 계약 없이 새 집합을 만들어냅니다.

set-copy-clear 함수는 구체적인 집합 생성자를 호출해야 하므로 제네릭 폴백이 없습니다.

procedure

(set-clear st) → (and/c generic-set? set-empty?)
  st : generic-set?

st와 같지만 모든 요소가 제거된 집합을 만들어냅니다.

set-remove를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-clear! st) → void?
  st : generic-set?

st에서 모든 요소를 제거합니다.

set-remove!를 구현하고 set->stream을 지원하거나, set-first와 set-count 또는 set-empty? 중 하나를 구현하는 어떤 st에 대해서도 지원됩니다.

해시 집합의 경우, 해시 테이블의 동시 수정에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set-union st0 st ...) → generic-set?
  st0 : generic-set?
  st : generic-set?

st0와 같은 타입이고 st0와 모든 st의 요소들을 포함하는 집합을 만들어냅니다.

st0가 리스트이면 각 st도 리스트여야 합니다. 이 연산은 리스트에 대해 st들의 총 크기 곱하기 결과 크기에 비례하는 시간으로 동작합니다.

st0가 해시 집합이면 각 st도 같은 비교 함수(equal?, equal-always?, eqv?, eq?)를 사용하는 해시 집합이어야 합니다. 해시 집합의 가변성과 키 강도는 달라도 됩니다. 이 연산은 해시 집합에 대해 가장 큰 불변 집합을 제외한 모든 집합의 총 크기에 비례하는 시간으로 동작합니다.

결과 집합의 타입(리스트, 해시 집합 등)을 결정하려면 set-union에 적어도 하나의 집합이 제공되어야 합니다. set-union이 인자 0개로 적용될 수 있는 경우가 있다면, 대신 의도된 타입의 빈 집합을 첫 번째 인자로 전달하세요.

set-add를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

예시:

> (set-union (set))

(set)
> (set-union (seteq))

(seteq)
> (set-union (set 1 2) (set 2 3))

(set 1 2 3)
> (set-union (list 1 2) (list 2 3))

'(3 1 2)
> (set-union (set 1 2) (seteq 2 3))

set-union: set arguments have incompatible equivalence

predicates

  first set: (set 1 2)

  incompatible set: (seteq 2 3)
; Sets of different types cannot be unioned

procedure

(set-union! st0 st ...) → void?
  st0 : generic-set?
  st : generic-set?

모든 st에서 온 요소들을 st0에 추가합니다.

st0가 해시 집합이면 각 st도 같은 비교 함수(equal?, equal-always?, eqv?, eq?)를 사용하는 해시 집합이어야 합니다. 해시 집합의 가변성과 키 강도는 달라도 됩니다. 이 연산은 해시 집합에 대해 st들의 총 크기에 비례하는 시간으로 동작합니다.

set-add!를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

해시 집합의 경우, 해시 테이블의 동시 수정에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set-intersect st0 st ...) → generic-set?
  st0 : generic-set?
  st : generic-set?

st0와 같은 타입이고 모든 st에도 포함된 st0의 요소들을 포함하는 집합을 만들어냅니다.

st0가 리스트이면 각 st도 리스트여야 합니다. 이 연산은 리스트에 대해 st들의 총 크기 곱하기 st0의 크기에 비례하는 시간으로 동작합니다.

st0가 해시 집합이면 각 st도 같은 비교 함수(equal?, equal-always?, eqv?, eq?)를 사용하는 해시 집합이어야 합니다. 해시 집합의 가변성과 키 강도는 달라도 됩니다. 이 연산은 해시 집합에 대해 가장 작은 불변 집합의 크기에 비례하는 시간으로 동작합니다.

set-remove 또는 set-clear와 set-add 둘 다를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-intersect! st0 st ...) → void?
  st0 : generic-set?
  st : generic-set?

모든 st에 포함되지 않은 st0의 모든 요소를 제거합니다.

st0가 해시 집합이면 각 st도 같은 비교 함수(equal?, equal-always?, eqv?, eq?)를 사용하는 해시 집합이어야 합니다. 해시 집합의 가변성과 키 강도는 달라도 됩니다. 이 연산은 해시 집합에 대해 st0의 크기에 비례하는 시간으로 동작합니다.

set-remove!를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

해시 집합의 경우, 해시 테이블의 동시 수정에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set-subtract st0 st ...) → generic-set?
  st0 : generic-set?
  st : generic-set?

st0와 같은 타입이고 어떤 st에도 포함되지 않은 st0의 요소들을 포함하는 집합을 만들어냅니다.

st0가 리스트이면 각 st도 리스트여야 합니다. 이 연산은 리스트에 대해 st들의 총 크기 곱하기 st0의 크기에 비례하는 시간으로 동작합니다.

set-remove 또는 set-clear와 set-add 둘 다를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-subtract! st0 st ...) → void?
  st0 : generic-set?
  st : generic-set?

어떤 st에 포함된 st0의 모든 요소를 제거합니다.

set-remove!를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

해시 집합의 경우, 해시 테이블의 동시 수정에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set-symmetric-difference st0 st ...) → generic-set?
  st0 : generic-set?
  st : generic-set?

st0와 같은 타입이고 st0와 st들에서 홀수 번 포함된 모든 요소를 포함하는 집합을 만들어냅니다.

st0가 리스트이면 각 st도 리스트여야 합니다. 이 연산은 리스트에 대해 st들의 총 크기 곱하기 st0의 크기에 비례하는 시간으로 동작합니다.

set-remove 또는 set-clear와 set-add 둘 다를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

예시:

> (set-symmetric-difference (set 1) (set 1 2) (set 1 2 3))

(set 1 3)

procedure

(set-symmetric-difference! st0 st ...) → void?
  st0 : generic-set?
  st : generic-set?

st0가 st들과 st0의 원래 내용에서 홀수 번 포함된 모든 요소를 포함하도록 st0의 요소를 추가하고 제거합니다.

set-remove!를 구현하고 set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

해시 집합의 경우, 해시 테이블의 동시 수정에 대한 주의 사항들을 참고하세요. 이는 해시 집합에도 적용됩니다.

procedure

(set=? st st2) → boolean?
  st : generic-set?
  st2 : generic-set?

st와 st2가 같은 구성원을 포함하면 #t를, 그렇지 않으면 #f를 반환합니다.

st가 리스트이면 st2도 리스트여야 합니다. 이 연산은 리스트에 대해 st의 크기 곱하기 st2의 크기에 비례하는 시간으로 동작합니다.

st가 해시 집합이면 st2도 같은 비교 함수(equal?, equal-always?, eqv?, eq?)를 사용하는 해시 집합이어야 합니다. 해시 집합의 가변성과 키 강도는 달라도 됩니다. 이 연산은 해시 집합에 대해 st의 크기 더하기 st2의 크기에 비례하는 시간으로 동작합니다.

둘 다 subset?를 지원하는 어떤 st와 st2에 대해서도 지원됩니다. st와 무관하게 set=?를 구현하는 st2에 대해서도 지원됩니다.

예시:

> (set=? (list 1 2) (list 2 1))

#t
> (set=? (set 1) (set 1 2 3))

#f
> (set=? (set 1 2 3) (set 1))

#f
> (set=? (set 1 2 3) (set 1 2 3))

#t
> (set=? (seteq 1 2) (mutable-seteq 2 1))

#t
> (set=? (seteq 1 2) (seteqv 1 2))

set=?: set arguments have incompatible equivalence

predicates

  first set: (seteq 1 2)

  incompatible set: (seteqv 1 2)
; Sets of different types cannot be compared

procedure

(subset? st st2) → boolean?
  st : generic-set?
  st2 : generic-set?

st2가 st의 모든 구성원을 포함하면 #t를, 그렇지 않으면 #f를 반환합니다.

st가 리스트이면 st2도 리스트여야 합니다. 이 연산은 리스트에 대해 st의 크기 곱하기 st2의 크기에 비례하는 시간으로 동작합니다.

st가 해시 집합이면 st2도 같은 비교 함수(equal?, equal-always?, eqv?, eq?)를 사용하는 해시 집합이어야 합니다. 해시 집합의 가변성과 키 강도는 달라도 됩니다. 이 연산은 해시 집합에 대해 st의 크기에 비례하는 시간으로 동작합니다.

set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

예시:

> (subset? (set 1) (set 1 2 3))

#t
> (subset? (set 1 2 3) (set 1))

#f
> (subset? (set 1 2 3) (set 1 2 3))

#t

procedure

(proper-subset? st st2) → boolean?
  st : generic-set?
  st2 : generic-set?

st2가 st의 모든 구성원과 적어도 하나의 추가 요소를 포함하면 #t를, 그렇지 않으면 #f를 반환합니다.

st가 리스트이면 st2도 리스트여야 합니다. 이 연산은 리스트에 대해 st의 크기 곱하기 st2의 크기에 비례하는 시간으로 동작합니다.

둘 다 subset?를 지원하는 어떤 st와 st2에 대해서도 지원됩니다.

예시:

> (proper-subset? (set 1) (set 1 2 3))

#t
> (proper-subset? (set 1 2 3) (set 1))

#f
> (proper-subset? (set 1 2 3) (set 1 2 3))

#f

procedure

(set->list st) → list?
  st : generic-set?

st의 요소들을 포함하는 리스트를 만들어냅니다.

set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-map st proc) → (listof any/c)
  st : generic-set?
  proc : (any/c . -> . any/c)

절차 proc을 st의 각 요소에 불특정 순서로 적용하고, 결과들을 리스트로 모읍니다.

set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(set-for-each st proc) → void?
  st : generic-set?
  proc : (any/c . -> . any)

proc을 st의 각 요소에(proc의 부수 효과를 위해) 불특정 순서로 적용합니다.

set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(in-set st) → sequence?
  st : generic-set?

집합을 for와 다른 폼과 함께 쓰기 위해 명시적으로 시퀀스로 변환합니다.

set->stream을 지원하는 어떤 st에 대해서도 지원됩니다.

procedure

(impersonate-hash-set st
  inject-proc
  add-proc
  shrink-proc
  extract-proc
  [clear-proc
  equal-key-proc]
  prop
  prop-val ...
  ...)

→ (and/c (or/c set-mutable? set-weak?) impersonator?)
  st : (or/c set-mutable? set-weak?)
  inject-proc : (or/c #f (-> set? any/c any/c))
  add-proc : (or/c #f (-> set? any/c any/c))
  shrink-proc : (or/c #f (-> set? any/c any/c))
  extract-proc : (or/c #f (-> set? any/c any/c))
  clear-proc : (or/c #f (-> set? any)) = #f
  equal-key-proc : (or/c #f (-> set? any/c any/c)) = #f
  prop : impersonator-property?
  prop-val : any/c

st를 임퍼서네이트하며, 주어진 절차들을 통해 다양한 집합 연산을 리다이렉트합니다.

inject-proc 절차는 어떤 요소가 이미 집합에 있을 수 있는 다른 요소들과 비교하기 위해 집합에 임시로 넣어질 때마다 호출됩니다. 예를 들어 (set-member? s e)를 평가할 때, e는 s의 다른 요소들과 비교되기 전에 inject-proc에 전달됩니다.

add-proc 절차는 요소를 집합에 추가할 때(예: set-add 또는 set-add!를 통해) 호출됩니다. add-proc의 결과가 집합에 저장됩니다.

shrink-proc 절차는 요소가 하나 적은 새 집합을 만들 때 호출됩니다. 예를 들어 (set-remove s e) 또는 (set-remove! s e)를 평가할 때, 요소는 (예: set-remove 또는 set-remove!를 통해) 집합에서 제거됩니다. shrink-proc의 결과는 실제로 집합에서 제거된 요소입니다.

extract-proc 절차는 요소가 (예: set-first로) 집합에서 끌려나올 때 호출됩니다. extract-proc의 결과는 집합에서 실제로 만들어낸 요소입니다.

clear-proc는 set-clear와 set-clear!에 의해 호출되며, (예: 예외를 일으켜) 탈출하지 않고 반환하면 지우는 연산이 허용됩니다. 그 결과는 무시됩니다. clear-proc가 #f이면, 지우기는 (다른 제공된 절차들로의 호출을 통해) 요소별로 수행됩니다.

equal-key-proc는 요소의 해시 코드가 필요하거나 요소가 집합의 밑바탕 동등성(equality)에 제공될 때 호출됩니다. 해시를 계산하거나 동등성을 비교할 때 equal-key-proc의 결과가 사용됩니다.

inject-proc, add-proc, shrink-proc, extract-proc 인자 중 어떤 것이 #f이면, 모두 #f여야 하며, clear-proc와 equal-key-proc도 #f여야 하고, 적어도 하나의 속성이 제공되어야 합니다.

prop와 prop-val의 쌍들(impersonate-hash-set의 인자 수는 홀수여야 함)은 st의 임퍼서네이터 속성을 추가하거나 임퍼서네이터 속성 값을 대체합니다.

procedure

(chaperone-hash-set st
  inject-proc
  add-proc
  shrink-proc
  extract-proc
  [clear-proc
  equal-key-proc]
  prop
  prop-val ...
  ...)

→ (and/c (or/c set? set-mutable? set-weak?) chaperone?)
  st : (or/c set? set-mutable? set-weak?)
  inject-proc : (or/c #f (-> set? any/c any/c))
  add-proc : (or/c #f (-> set? any/c any/c))
  shrink-proc : (or/c #f (-> set? any/c any/c))
  extract-proc : (or/c #f (-> set? any/c any/c))
  clear-proc : (or/c #f (-> set? any)) = #f
  equal-key-proc : (or/c #f (-> set? any/c any/c)) = #f
  prop : impersonator-property?
  prop-val : any/c

st를 채퍼론합니다. impersonate-hash-set와 같지만, inject-proc, add-proc, shrink-proc, extract-proc, equal-key-proc의 결과가 두 번째 인자의 chaperone-of?여야 한다는 제약이 있습니다. 또한 입력은 불변 set?일 수 있습니다.

Custom Hash Sets

syntax

(define-custom-set-types name
                         optional-predicate
                         comparison-expr
                         optional-hash-functions)

optional-predicate =

  | #:elem? predicate-expr

optional-hash-functions =

  | hash1-expr
  | hash1-expr hash2-expr

주어진 비교식 comparison-expr, 해시 함수 hash1-expr과 hash2-expr, 요소 술어 predicate-expr에 기반해 새 해시 집합 타입을 만듭니다. 이 함수들의 인터페이스는 make-custom-set-types와 같습니다. 새 집합 타입은 세 가지 변형이 있습니다: 불변, 요소를 강하게 보유한 가변, 요소를 약하게 보유한 가변.

일곱 개의 이름을 정의합니다:

name?는 새 타입의 인스턴스들을 인식하고,
immutable-name?는 새 타입의 불변 인스턴스들을 인식하고,
mutable-name?는 요소를 강하게 보유한 새 타입의 가변 인스턴스들을 인식하고,
weak-name?는 요소를 약하게 보유한 새 타입의 가변 인스턴스들을 인식하고,
make-immutable-name은 새 타입의 불변 인스턴스들을 구성하고,
make-mutable-name은 요소를 강하게 보유한 새 타입의 가변 인스턴스들을 구성하고,
make-weak-name은 요소를 약하게 보유한 새 타입의 가변 인스턴스들을 구성합니다.

생성자들은 모두 스트림을 선택적 인자로 받아 초기 요소를 제공합니다.

예시:

> (define-custom-set-types string-set
                           #:elem? string?
                           string=?
                           string-length)

> (define imm
    (make-immutable-string-set '("apple" "banana")))

> (define mut
    (make-mutable-string-set '("apple" "banana")))

> (generic-set? imm)

#t
> (generic-set? mut)

#t
> (set? imm)

#t
> (generic-set? imm)

#t
> (string-set? imm)

#t
> (string-set? mut)

#t
> (immutable-string-set? imm)

#t
> (immutable-string-set? mut)

#f
> (set-member? imm "apple")

#t
> (set-member? mut "banana")

#t
> (equal? imm mut)

#f
> (set=? imm mut)

#t
> (set-remove! mut "banana")
> (set-member? mut "banana")

#f
> (equal? (set-remove (set-remove imm "apple") "banana")
          (make-immutable-string-set))

#t

procedure

(make-custom-set-types eql?
  [hash1
  hash2
  #:elem? elem?
  #:name name
  #:for who])

→ (any/c . -> . boolean?)
(any/c . -> . boolean?)
(any/c . -> . boolean?)
(any/c . -> . boolean?)
(->* [] [stream?] generic-set?)
(->* [] [stream?] generic-set?)
(->* [] [stream?] generic-set?)

  eql? : (or/c (any/c any/c . -> . any/c)
      (any/c any/c (any/c any/c . -> . any/c) . -> . any/c))

  hash1 : (or/c (any/c . -> . exact-integer?)
      (any/c (any/c . -> . exact-integer?) . -> . exact-integer?))

   = (const 1)

  hash2 : (or/c (any/c . -> . exact-integer?)
      (any/c (any/c . -> . exact-integer?) . -> . exact-integer?))

   = (const 1)

  elem? : (any/c . -> . boolean?) = (const #true)
  name : symbol? = 'custom-set
  who : symbol? = 'make-custom-set-types

주어진 비교 함수 eql?, 해시 함수 hash1과 hash2, 술어 elem?에 기반해 새 집합 타입을 만듭니다. 새 집합 타입은 불변이거나, 요소를 강하게 보유한 가변이거나, 요소를 약하게 보유한 가변인 변형이 있습니다. 주어진 name은 새 집합 타입의 인스턴스를 출력할 때 사용되고, 기호 who는 오류를 보고할 때 사용됩니다.

비교 함수 eql?는 2개 또는 3개의 인자를 받을 수 있습니다. 2개 인자를 받으면 두 요소가 주어져 비교합니다. 3개 인자를 받고 2개 인자는 받지 않으면, 요소들의 하위 부분을 비교할 때 데이터 순환을 처리하는 재귀 비교 함수도 받습니다.

해시 함수 hash1과 hash2는 1개 또는 2개의 인자를 받을 수 있습니다. 어떤 해시 함수가 1개 인자를 받으면, 요소에 적용되어 대응하는 해시 값을 계산합니다. 어떤 해시 함수가 2개 인자를 받고 1개 인자는 받지 않으면, 요소들의 하위 부분의 해시 값을 계산할 때 데이터 순환을 처리하는 재귀 해시 함수도 받습니다.

술어 elem?는 1개 인자를 받아야 하며, 새 집합 타입에 대한 유효한 요소를 인식하는 데 사용됩니다.

일곱 값을 만들어냅니다:

새 집합 타입의 모든 인스턴스를 인식하는 술어,
약한 인스턴스를 인식하는 술어,
가변 인스턴스를 인식하는 술어,
불변 인스턴스를 인식하는 술어,
약한 인스턴스를 위한 생성자,
가변 인스턴스를 위한 생성자,
불변 인스턴스를 위한 생성자.

예시는 define-custom-set-types를 참고하세요.

더 알아보기

해시 테이블(Hash Tables) 관련 문서
시퀀스(Sequences)와 스트림(Streams) 관련 문서
제네릭 인터페이스(Generic Interfaces) 관련 문서