►The Racket Reference
▼4 Datatypes
►4.17 Sets
On this page:
4.17.1 Hash Sets
set-equal?
set-eqv?
set-eq?
set?
set-mutable?
set-weak?
set
seteqv
seteq
mutable-set
mutable-seteqv
mutable-seteq
weak-set
weak-seteqv
weak-seteq
list->set
list->seteqv
list->seteq
list->mutable-set
list->mutable-seteqv
list->mutable-seteq
list->weak-set
list->weak-seteqv
list->weak-seteq
for/  set
for/  seteq
for/  seteqv
for*/  set
for*/  seteq
for*/  seteqv
for/  mutable-set
for/  mutable-seteq
for/  mutable-seteqv
for*/  mutable-set
for*/  mutable-seteq
for*/  mutable-seteqv
for/  weak-set
for/  weak-seteq
for/  weak-seteqv
for*/  weak-set
for*/  weak-seteq
for*/  weak-seteqv
in-immutable-set
in-mutable-set
in-weak-set
4.17.2 Set Predicates and Contracts
generic-set?
set-implements?
set-implements/  c
set/  c
4.17.3 Generic Set Interface
gen:  set
4.17.3.1 Set Methods
set-member?
set-add
set-add!
set-remove
set-remove!
set-empty?
set-count
set-first
set-rest
set->stream
set-copy
set-copy-clear
set-clear
set-clear!
set-union
set-union!
set-intersect
set-intersect!
set-subtract
set-subtract!
set-symmetric-difference
set-symmetric-difference!
set=?
subset?
proper-subset?
set->list
set-map
set-for-each
in-set
impersonate-hash-set
chaperone-hash-set
4.17.4 Custom Hash Sets
define-custom-set-types
make-custom-set-types
  top  ← prev  up  next → 

4.17 Sets

A set represents a collection of distinct elements. The following datatypes are all sets:

 (require racket/set) package: base
The bindings documented in this section are provided by the racket/set and racket libraries, but not racket/base.

4.17.1 Hash Sets

A hash set is a set whose elements are compared via equal?, eqv?, or eq? and partitioned via equal-hash-code, eqv-hash-code, or eq-hash-code. A hash set is either immutable or mutable; mutable hash sets retain their elements either strongly or weakly.

Like operations on immutable hash tables, “constant time” hash set operations actually require O(log N) time for a set of size N.

A hash set can be used as a stream (see Streams) and thus as a single-valued sequence (see Sequences). The elements of the set serve as elements of the stream or sequence. If an element is added to or removed from the hash set during iteration, then an iteration step may fail with exn:fail:contract, or the iteration may skip or duplicate elements. See also in-set.

Two hash sets are equal? when they use the same element-comparison procedure (equal?, eqv?, or eq?), both hold elements strongly or weakly, have the same mutability, and have equivalent elements. Immutable hash sets support effectively constant-time access and update, just like mutable hash sets; the constant on immutable operations is usually larger, but the functional nature of immutable hash sets can pay off in certain algorithms.

All hash sets implement set->stream, set-empty?, set-member?, set-count, subset?, proper-subset?, set-map, set-for-each, set-copy, set-copy-clear, set->list, and set-first. Immutable hash sets in addition implement set-add, set-remove, set-clear, set-union, set-intersect, set-subtract, and set-symmetric-difference. Mutable hash sets in addition implement set-add!, set-remove!, set-clear!, set-union!, set-intersect!, set-subtract!, and set-symmetric-difference!.

Operations on sets that contain elements that are mutated are unpredictable in much the same way that hash table operations are unpredictable when keys are mutated.

procedure

(set-equal? x) → boolean?

  x : any/c

procedure

(set-eqv? x) → boolean?

  x : any/c

procedure

(set-eq? x) → boolean?

  x : any/c
Returns #t if x is a hash set that compares elements with equal?, eqv?, or eq?, respectively; returns #f otherwise.

procedure

(set? x) → boolean?

  x : any/c

procedure

(set-mutable? x) → boolean?

  x : any/c

procedure

(set-weak? x) → boolean?

  x : any/c
Returns #t if x is a hash set that is respectively immutable, mutable with strongly-held keys, or mutable with weakly-held keys; returns #f otherwise.

procedure

(set v ...) → (and/c generic-set? set-equal? 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-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-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
Creates a hash set with the given vs as elements. The elements are added in the order that they appear as arguments, so in the case of sets that use equal? or eqv?, an earlier element may be replaced by a later element that is equal? or eqv? but not eq?.

procedure

(list->set lst) → (and/c generic-set? set-equal? 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-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-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?
Creates a hash set with the elements of the given lst as the elements of the set. Equivalent to (apply set lst), (apply seteqv lst), (apply seteq lst), and so on, respectively.

syntax

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

syntax

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

syntax

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

syntax

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

syntax

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

syntax

(for*/seteqv (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-set (for-clause ...) body ...+)

syntax

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

syntax

(for*/mutable-seteqv (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-set (for-clause ...) body ...+)

syntax

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

syntax

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

Analogous to for/list and for*/list, but to construct a hash set instead of a list.

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?
Explicitly converts a specific kind of hash set to a sequence for use with for forms.

As with in-list and some other sequence constructors, in-immutable-set performs better when it appears directly in a for clause.

These sequence constructors are compatible with Custom Hash Sets.

Added in version 6.4.0.7 of package base.

4.17.2 Set Predicates and Contracts

procedure

(generic-set? v) → boolean?

  v : any/c
Returns #t if v is a set; returns #f otherwise.

Examples:
> (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?
Returns #t if st implements all of the methods from gen:set named by the syms; returns #f otherwise. Fallback implementations do not affect the result; st may support the given methods via fallback implementations yet produce #f.

Examples:
> (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?
Recognizes sets that support all of the methods from gen:set named by the syms.

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 '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
Constructs a contract that recognizes sets whose elements match elem/c.

If kind is 'immutable, 'mutable, or 'weak, the resulting contract accepts only hash sets that are respectively immutable, mutable with strongly-held keys, or mutable with weakly-held keys. If kind is 'mutable-or-weak, the resulting contract accepts any mutable hash sets, regardless of key-holding strength.

If cmp is 'equal, 'eqv, or 'eq, the resulting contract accepts only hash sets that compare elements using equal?, eqv?, or eq?, respectively.

If cmp is 'eqv or 'eq, then elem/c must be a flat contract.

If cmp and kind are both 'dont-care, then the resulting contract will accept any kind of set, not just hash sets.

If lazy? is not #f, then the elements of the set are not checked immediately by the contract and only the set itself is checked (according to the cmp and kind arguments). If lazy? is #f, then the elements are checked immediately by the contract. The lazy? argument is ignored when the set contract accepts generic sets (i.e., when cmp and kind are both 'dont-care); in that case, the value being checked in that case is a list?, then the contract is not lazy otherwise the contract is lazy.

If kind allows mutable sets (i.e., is 'dont-care, 'mutable, 'weak, or 'mutable-or-weak) and lazy? is #f, then the elements are checked both immediately and when they are accessed from the set.

The equal-key/c contract is used when values are passed to the comparison and hashing functions used internally.

The result contract will be a flat contract when elem/c and equal-key/c are both flat contracts, lazy? is #f, and kind is 'immutable. The result will be a chaperone contract when elem/c is a chaperone contract.

4.17.3 Generic Set Interface

syntax

gen:set

A generic interface (see Generic Interfaces) that supplies set method implementations for a structure type via the #:methods option of struct definitions. This interface can be used to implement any of the methods documented as Set Methods.

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

4.17.3.1 Set Methods

The methods of gen:set can be classified into three categories, as determined by their fallback implementations:

  1. methods with no fallbacks,

  2. methods whose fallbacks depend on other, non-fallback methods,

  3. and methods whose fallbacks can depend on either fallback or non-fallback methods.

As an example, implementing the following methods would guarantee that all the methods in gen:set would at least have a fallback method:

There may be other such subsets of methods that would guarantee at least a fallback for every method.

procedure

(set-member? st v) → boolean?

  st : generic-set?
  v : any/c
Returns #t if v is in st, #f otherwise. Has no fallback.

procedure

(set-add st v) → generic-set?

  st : generic-set?
  v : any/c
Produces a set that includes v plus all elements of st. This operation runs in constant time for hash sets. Has no fallback.

procedure

(set-add! st v) → void?

  st : generic-set?
  v : any/c
Adds the element v to st. This operation runs in constant time for hash sets. Has no fallback.

procedure

(set-remove st v) → generic-set?

  st : generic-set?
  v : any/c
Produces a set that includes all elements of st except v. This operation runs in constant time for hash sets. Has no fallback.

procedure

(set-remove! st v) → void?

  st : generic-set?
  v : any/c
Removes the element v from st. This operation runs in constant time for hash sets. Has no fallback.

procedure

(set-empty? st) → boolean?

  st : generic-set?
Returns #t if st has no members; returns #f otherwise.

Supported for any st that implements set->stream or set-count.

procedure

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

  st : generic-set?
Returns the number of elements in st.

Supported for any st that supports set->stream.

procedure

(set-first st) → any/c

  st : (and/c generic-set? (not/c set-empty?))
Produces an unspecified element of st. Multiple uses of set-first on st produce the same result.

Supported for any st that implements set->stream.

procedure

(set-rest st) → generic-set?

  st : (and/c generic-set? (not/c set-empty?))
Produces a set that includes all elements of st except (set-first st).

Supported for any st that implements set-remove and either set-first or set->stream.

procedure

(set->stream st) → stream?

  st : generic-set?
Produces a stream containing the elements of st.

Supported for any st that implements:

procedure

(set-copy st) → generic-set?

  st : generic-set?
Produces a new, mutable set of the same type and with the same elements as st.

Supported for any st that supports set->stream and implements set-copy-clear and set-add!.

procedure

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

  st : generic-set?
Produces a new, empty set of the same type, mutability, and key strength as st.

A difference between set-copy-clear and set-clear is that the latter conceptually iterates set-remove on the given set, and so it preserves any contract on the given set. The set-copy-clear function produces a new set without any contracts.

The set-copy-clear function must call concrete set constructors and thus has no generic fallback.

procedure

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

  st : generic-set?
Produces a set like st but with all elements removed.

Supported for any st that implements set-remove and supports set->stream.

procedure

(set-clear! st) → void?

  st : generic-set?
Removes all elements from st.

Supported for any st that implements set-remove! and either supports set->stream or implements set-first and either set-count or set-empty?.

procedure

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

  st0 : generic-set?
  st : generic-set?
Produces a set of the same type as st0 that includes the elements from st0 and all of the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of the result.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the total size of all of the sets except the largest immutable set.

At least one set must be provided to set-union to determine the type of the resulting set (list, hash set, etc.). If there is a case where set-union may be applied to zero arguments, instead pass an empty set of the intended type as the first argument.

Supported for any st that implements set-add and supports set->stream.

Examples:
> (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?
Adds the elements from all of the sts to st0.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the total size of the sts.

Supported for any st that implements set-add! and supports set->stream.

procedure

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

  st0 : generic-set?
  st : generic-set?
Produces a set of the same type as st0 that includes the elements from st0 that are also contained by all of the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of st0.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of the smallest immutable set.

Supported for any st that implements either set-remove or both set-clear and set-add, and supports set->stream.

procedure

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

  st0 : generic-set?
  st : generic-set?
Removes every element from st0 that is not contained by all of the sts.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st0.

Supported for any st that implements set-remove! and supports set->stream.

procedure

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

  st0 : generic-set?
  st : generic-set?
Produces a set of the same type as st0 that includes the elements from st0 that are not contained by any of the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of st0.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st0.

Supported for any st that implements either set-remove or both set-clear and set-add, and supports set->stream.

procedure

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

  st0 : generic-set?
  st : generic-set?
Removes every element from st0 that is contained by any of the sts.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st0.

Supported for any st that implements set-remove! and supports set->stream.

procedure

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

  st0 : generic-set?
  st : generic-set?
Produces a set of the same type as st0 that includes all of the elements contained an odd number of times in st0 and the sts.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the total size of the sts times the size of st0.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the total size of all of the sets except the largest immutable set.

Supported for any st that implements set-remove or both set-clear and set-add, and supports set->stream.

Example:
> (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?
Adds and removes elements of st0 so that it includes all of the elements contained an odd number of times in the sts and the original contents of st0.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the total size of the sts.

Supported for any st that implements set-remove! and supports set->stream.

procedure

(set=? st st2) → boolean?

  st : generic-set?
  st2 : generic-set?
Returns #t if st and st2 contain the same members; returns #f otherwise.

If st0 is a list, each st must also be a list. This operation runs on lists in time proportional to the size of st times the size of st2.

If st0 is a hash set, each st must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st plus the size of st2.

Supported for any st and st2 that both support subset?; also supported for any if st2 that implements set=? regardless of st.

Examples:
> (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?
Returns #t if st2 contains every member of st; returns #f otherwise.

If st is a list, then st2 must also be a list. This operation runs on lists in time proportional to the size of st times the size of st2.

If st is a hash set, then st2 must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st.

Supported for any st that supports set->stream.

Examples:
> (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?
Returns #t if st2 contains every member of st and at least one additional element; returns #f otherwise.

If st is a list, then st2 must also be a list. This operation runs on lists in time proportional to the size of st times the size of st2.

If st is a hash set, then st2 must also be a hash set that uses the same comparison function (equal?, eqv?, or eq?). The mutability and key strength of the hash sets may differ. This operation runs on hash sets in time proportional to the size of st plus the size of st2.

Supported for any st and st2 that both support subset?.

Examples:
> (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?
Produces a list containing the elements of st.

Supported for any st that supports set->stream.

procedure

(set-map st proc) → (listof any/c)

  st : generic-set?
  proc : (any/c . -> . any/c)
Applies the procedure proc to each element in st in an unspecified order, accumulating the results into a list.

Supported for any st that supports set->stream.

procedure

(set-for-each st proc) → void?

  st : generic-set?
  proc : (any/c . -> . any)
Applies proc to each element in st (for the side-effects of proc) in an unspecified order.

Supported for any st that supports set->stream.

procedure

(in-set st) → sequence?

  st : generic-set?
Explicitly converts a set to a sequence for use with for and other forms.

Supported for any st that supports set->stream.

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
Impersonates st, redirecting various set operations via the given procedures.

The inject-proc procedure is called whenever an element is temporarily put into the set for the purposes of comparing it with other elements that may already be in the set. For example, when evaluating (set-member? s e), e will be passed to the inject-proc before comparing it with other elements of s.

The add-proc procedure is called when adding an element to a set, e.g., via set-add or set-add!. The result of the add-proc is stored in the set.

The shrink-proc procedure is called when building a new set with one fewer element. For example, when evaluating (set-remove s e) or (set-remove! s e), an element is removed from a set, e.g., via set-remove or set-remove!. The result of the shrink-proc is the element actually removed from the set.

The extract-proc procedure is called when an element is pulled out of a set, e.g., by set-first. The result of the extract-proc is the element actually produced by from the set.

The clear-proc is called by set-clear and set-clear! and if it returns (as opposed to escaping, perhaps via raising an exception), the clearing operation is permitted. Its result is ignored. If clear-proc is #f, then clearing is done element by element (via calls into the other supplied procedures).

The equal-key-proc is called when an element’s hash code is needed of when an element is supplied to the underlying equality in the set. The result of equal-key-proc is used when computing the hash or comparing for equality.

If any of the inject-proc, add-proc, shrink-proc, or extract-proc arguments are #f, then they all must be #f, the clear-proc and equal-key-proc must also be #f, and there must be at least one property supplied.

Pairs of prop and prop-val (the number of arguments to impersonate-hash-set must be odd) add impersonator properties or override impersonator property values of 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
Chaperones st. Like impersonate-hash-set but with the constraints that the results of the inject-proc, add-proc, shrink-proc, extract-proc, and equal-key-proc must be chaperone-of? their second arguments. Also, the input may be an immutable? set.

4.17.4 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
Creates a new hash set type based on the given comparison comparison-expr, hash functions hash1-expr and hash2-expr, and element predicate predicate-expr; the interfaces for these functions are the same as in make-custom-set-types. The new set type has three variants: immutable, mutable with strongly-held elements, and mutable with weakly-held elements.

Defines seven names:

The constructors all accept a stream as an optional argument, providing initial elements.

Examples:
> (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
Creates a new set type based on the given comparison function eql?, hash functions hash1 and hash2, and predicate elem?. The new set type has variants that are immutable, mutable with strongly-held elements, and mutable with weakly-held elements. The given name is used when printing instances of the new set type, and the symbol who is used for reporting errors.

The comparison function eql? may accept 2 or 3 arguments. If it accepts 2 arguments, it given two elements to compare them. If it accepts 3 arguments and does not accept 2 arguments, it is also given a recursive comparison function that handles data cycles when comparing sub-parts of the elements.

The hash functions hash1 and hash2 may accept 1 or 2 arguments. If either hash function accepts 1 argument, it is applied to a element to compute the corresponding hash value. If either hash function accepts 2 arguments and does not accept 1 argument, it is also given a recursive hash function that handles data cycles when computing hash values of sub-parts of the elements.

The predicate elem? must accept 1 argument and is used to recognize valid elements for the new set type.

Produces seven values:

See define-custom-set-types for an example.

  top  ← prev  up  next →