-
-
Notifications
You must be signed in to change notification settings - Fork 645
/
sets.scrbl
947 lines (715 loc) · 36.5 KB
/
sets.scrbl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
#lang scribble/doc
@(require "mz.rkt" (for-label racket/set))
@title[#:tag "sets"]{Sets}
@(define set-eval (make-base-eval))
@examples[#:hidden #:eval set-eval (require racket/set)]
A @deftech{set} represents a collection of distinct elements. The following
datatypes are all sets:
@itemize[
@item{@techlink{hash sets};}
@item{@techlink{lists} using @racket[equal?] to compare elements; and}
@item{@techlink{structures} whose types implement the @racket[gen:set]
@tech{generic interface}.}
]
@note-lib[racket/set]
@section{Hash Sets}
A @deftech{hash set} is a set whose elements are compared via @racket[equal?],
@racket[eqv?], or @racket[eq?] and partitioned via @racket[equal-hash-code],
@racket[eqv-hash-code], or @racket[eq-hash-code]. A hash set is either
immutable or mutable; mutable hash sets retain their elements either strongly
or weakly.
@margin-note{Like operations on immutable hash tables, ``constant time'' hash
set operations actually require @math{O(log N)} time for a set of size
@math{N}.}
A hash set can be used as a @tech{stream} (see @secref["streams"]) and thus as
a single-valued @tech{sequence} (see @secref["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 @racket[exn:fail:contract], or the iteration may skip or duplicate
elements. See also @racket[in-set].
Two hash sets are @racket[equal?] when they use the same element-comparison
procedure (@racket[equal?], @racket[eqv?], or @racket[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 @impl{implement} @racket[set->stream],
@racket[set-empty?], @racket[set-member?], @racket[set-count],
@racket[subset?], @racket[proper-subset?], @racket[set-map],
@racket[set-for-each], @racket[set-copy], @racket[set-copy-clear],
@racket[set->list], and @racket[set-first]. Immutable hash sets in
addition @impl{implement} @racket[set-add], @racket[set-remove],
@racket[set-clear], @racket[set-union], @racket[set-intersect],
@racket[set-subtract], and @racket[set-symmetric-difference]. Mutable
hash sets in addition @impl{implement} @racket[set-add!],
@racket[set-remove!], @racket[set-clear!], @racket[set-union!],
@racket[set-intersect!], @racket[set-subtract!], and
@racket[set-symmetric-difference!].
Operations on sets that contain elements that are mutated are
unpredictable in much the same way that @tech{hash table} operations are
unpredictable when keys are mutated.
@deftogether[(
@defproc[(set-equal? [x any/c]) boolean?]
@defproc[(set-eqv? [x any/c]) boolean?]
@defproc[(set-eq? [x any/c]) boolean?]
)]{
Returns @racket[#t] if @racket[x] is a @tech{hash set} that compares
elements with @racket[equal?], @racket[eqv?], or @racket[eq?], respectively;
returns @racket[#f] otherwise.
}
@deftogether[(
@defproc[(set? [x any/c]) boolean?]
@defproc[(set-mutable? [x any/c]) boolean?]
@defproc[(set-weak? [x any/c]) boolean?]
)]{
Returns @racket[#t] if @racket[x] is a @tech{hash set} that is respectively
immutable, mutable with strongly-held keys, or mutable with weakly-held keys;
returns @racket[#f] otherwise.
}
@deftogether[(
@defproc[(set [v any/c] ...) (and/c generic-set? set-equal? set?)]
@defproc[(seteqv [v any/c] ...) (and/c generic-set? set-eqv? set?)]
@defproc[(seteq [v any/c] ...) (and/c generic-set? set-eq? set?)]
@defproc[(mutable-set [v any/c] ...) (and/c generic-set? set-equal? set-mutable?)]
@defproc[(mutable-seteqv [v any/c] ...) (and/c generic-set? set-eqv? set-mutable?)]
@defproc[(mutable-seteq [v any/c] ...) (and/c generic-set? set-eq? set-mutable?)]
@defproc[(weak-set [v any/c] ...) (and/c generic-set? set-equal? set-weak?)]
@defproc[(weak-seteqv [v any/c] ...) (and/c generic-set? set-eqv? set-weak?)]
@defproc[(weak-seteq [v any/c] ...) (and/c generic-set? set-eq? set-weak?)]
)]{
Creates a @tech{hash set} with the given @racket[v]s as elements. The
elements are added in the order that they appear as arguments, so in the case
of sets that use @racket[equal?] or @racket[eqv?], an earlier element may be
replaced by a later element that is @racket[equal?] or @racket[eqv?] but not
@racket[eq?].
}
@deftogether[(
@defproc[(list->set [lst list?]) (and/c generic-set? set-equal? set?)]
@defproc[(list->seteqv [lst list?]) (and/c generic-set? set-eqv? set?)]
@defproc[(list->seteq [lst list?]) (and/c generic-set? set-eq? set?)]
@defproc[(list->mutable-set [lst list?]) (and/c generic-set? set-equal? set-mutable?)]
@defproc[(list->mutable-seteqv [lst list?]) (and/c generic-set? set-eqv? set-mutable?)]
@defproc[(list->mutable-seteq [lst list?]) (and/c generic-set? set-eq? set-mutable?)]
@defproc[(list->weak-set [lst list?]) (and/c generic-set? set-equal? set-weak?)]
@defproc[(list->weak-seteqv [lst list?]) (and/c generic-set? set-eqv? set-weak?)]
@defproc[(list->weak-seteq [lst list?]) (and/c generic-set? set-eq? set-weak?)]
)]{
Creates a @tech{hash set} with the elements of the given @racket[lst] as
the elements of the set. Equivalent to @racket[(apply set lst)],
@racket[(apply seteqv lst)], @racket[(apply seteq lst)], and so on,
respectively.
}
@deftogether[(
@defform[(for/set (for-clause ...) body ...+)]
@defform[(for/seteq (for-clause ...) body ...+)]
@defform[(for/seteqv (for-clause ...) body ...+)]
@defform[(for*/set (for-clause ...) body ...+)]
@defform[(for*/seteq (for-clause ...) body ...+)]
@defform[(for*/seteqv (for-clause ...) body ...+)]
@defform[(for/mutable-set (for-clause ...) body ...+)]
@defform[(for/mutable-seteq (for-clause ...) body ...+)]
@defform[(for/mutable-seteqv (for-clause ...) body ...+)]
@defform[(for*/mutable-set (for-clause ...) body ...+)]
@defform[(for*/mutable-seteq (for-clause ...) body ...+)]
@defform[(for*/mutable-seteqv (for-clause ...) body ...+)]
@defform[(for/weak-set (for-clause ...) body ...+)]
@defform[(for/weak-seteq (for-clause ...) body ...+)]
@defform[(for/weak-seteqv (for-clause ...) body ...+)]
@defform[(for*/weak-set (for-clause ...) body ...+)]
@defform[(for*/weak-seteq (for-clause ...) body ...+)]
@defform[(for*/weak-seteqv (for-clause ...) body ...+)]
)]{
Analogous to @racket[for/list] and @racket[for*/list], but to
construct a @tech{hash set} instead of a list.
}
@deftogether[(
@defproc[(in-immutable-set [st set?]) sequence?]
@defproc[(in-mutable-set [st set-mutable?]) sequence?]
@defproc[(in-weak-set [st set-weak?]) sequence?]
)]{
Explicitly converts a specific kind of @tech{hash set} to a sequence for
use with @racket[for] forms.
As with @racket[in-list] and some other sequence constructors,
@racket[in-immutable-set] performs better when it appears directly in a
@racket[for] clause.
These sequence constructors are compatible with
@secref["Custom_Hash_Sets" #:doc '(lib "scribblings/reference/reference.scrbl")].
}
@section{Set Predicates and Contracts}
@defproc[(generic-set? [v any/c]) boolean?]{
Returns @racket[#t] if @racket[v] is a @tech{set}; returns @racket[#f]
otherwise.
@examples[
#:eval set-eval
(generic-set? (list 1 2 3))
(generic-set? (set 1 2 3))
(generic-set? (mutable-seteq 1 2 3))
(generic-set? (vector 1 2 3))
]
}
@defproc[(set-implements? [st generic-set?] [sym symbol?] ...) boolean?]{
Returns @racket[#t] if @racket[st] implements all of the methods from
@racket[gen:set] named by the @racket[sym]s; returns @racket[#f] otherwise.
Fallback implementations do not affect the result; @racket[st] may support the
given methods via fallback implementations yet produce @racket[#f].
@examples[
#:eval set-eval
(set-implements? (list 1 2 3) 'set-add)
(set-implements? (list 1 2 3) 'set-add!)
(set-implements? (set 1 2 3) 'set-add)
(set-implements? (set 1 2 3) 'set-add!)
(set-implements? (mutable-seteq 1 2 3) 'set-add)
(set-implements? (mutable-seteq 1 2 3) 'set-add!)
(set-implements? (weak-seteqv 1 2 3) 'set-remove 'set-remove!)
]
}
@defproc[(set-implements/c [sym symbol?] ...) flat-contract?]{
Recognizes sets that support all of the methods from @racket[gen:set]
named by the @racket[sym]s.
}
@defproc[(set/c [elem/c chaperone-contract?]
[#:cmp cmp
(or/c 'dont-care 'equal 'eqv 'eq)
'dont-care]
[#:kind kind
(or/c 'dont-care 'immutable 'mutable 'weak 'mutable-or-weak)
'immutable]
[#:lazy? lazy? any/c
(not (and (equal? kind 'immutable)
(flat-contract? elem/c)))]
[#:equal-key/c equal-key/c contract? any/c])
contract?]{
Constructs a contract that recognizes sets whose elements match
@racket[elem/c].
If @racket[kind] is @racket['immutable], @racket['mutable], or
@racket['weak], the resulting contract accepts only @tech{hash sets} that
are respectively immutable, mutable with strongly-held keys, or mutable with
weakly-held keys. If @racket[kind] is @racket['mutable-or-weak], the
resulting contract accepts any mutable @tech{hash sets}, regardless of
key-holding strength.
If @racket[cmp] is @racket['equal], @racket['eqv], or @racket['eq], the
resulting contract accepts only @tech{hash sets} that compare elements
using @racket[equal?], @racket[eqv?], or @racket[eq?], respectively.
If @racket[cmp] is @racket['eqv] or @racket['eq], then @racket[elem/c] must
be a @tech{flat contract}.
If @racket[cmp] and @racket[kind] are both @racket['dont-care], then the
resulting contract will accept any kind of set, not just @tech{hash
sets}.
If @racket[lazy?] is not @racket[#f], then the elements of the set are not checked
immediately by the contract and only the set itself is checked (according to the
@racket[cmp] and @racket[kind] arguments). If @racket[lazy?] is
@racket[#f], then the elements are checked immediately by the contract.
The @racket[lazy?] argument is ignored when the set contract accepts generic sets
(i.e., when @racket[cmp] and @racket[kind] are both @racket['dont-care]); in that
case, the value being checked in that case is a @racket[list?], then the contract
is not lazy otherwise the contract is lazy.
If @racket[kind] allows mutable sets (i.e., is @racket['dont-care],
@racket['mutable], @racket['weak], or
@racket['mutable-or-weak]) and @racket[lazy?] is @racket[#f], then the elements
are checked both immediately and when they are accessed from the set.
The @racket[equal-key/c] contract is used when values are passed to the comparison
and hashing functions used internally.
The result contract will be a @tech{flat contract} when @racket[elem/c]
and @racket[equal-key/c] are both @tech{flat contracts},
@racket[lazy?] is @racket[#f], and @racket[kind] is @racket['immutable].
The result will be a @tech{chaperone contract} when @racket[elem/c] is a
@tech{chaperone contract}.
}
@section{Generic Set Interface}
@defidform[gen:set]{
A @tech{generic interface} (see @secref["struct-generics"]) that
supplies set method implementations for a structure type via the
@racket[#:methods] option of @racket[struct] definitions. This interface can
be used to implement any of the methods documented as
@secref["set-methods"].
@examples[
#:eval set-eval
(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
(generic-set? bset)
(set-member? bset 0)
(set-member? bset 1)
(set-member? bset 2)
(set-add bset 4)
(set-remove bset 2)
]
}
@subsection[#:tag "set-methods"]{Set Methods}
@(define (supp . args) (apply tech #:key "supported generic method" args))
@(define (impl . args) (apply tech #:key "implemented generic method" args))
The methods of @racket[gen:set] can be classified into three categories, as determined by their fallback implementations:
@itemlist[#:style 'ordered
@item{methods with no fallbacks,}
@item{methods whose fallbacks depend on other, non-fallback methods,}
@item{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 @racket[gen:set] would at least have a fallback method:
@itemlist[@item{@racket[set-member?]}
@item{@racket[set-add]}
@item{@racket[set-add!]}
@item{@racket[set-remove]}
@item{@racket[set-remove!]}
@item{@racket[set-first]}
@item{@racket[set-empty?]}
@item{@racket[set-copy-clear]}]
There may be other such subsets of methods that would guarantee at least a fallback for every method.
@defproc[(set-member? [st generic-set?] [v any/c]) boolean?]{
Returns @racket[#t] if @racket[v] is in @racket[st], @racket[#f]
otherwise. Has no fallback.
}
@defproc[(set-add [st generic-set?] [v any/c]) generic-set?]{
Produces a set that includes @racket[v] plus all elements of
@racket[st]. This operation runs in constant time for @tech{hash sets}. Has no fallback.
}
@defproc[(set-add! [st generic-set?] [v any/c]) void?]{
Adds the element @racket[v] to @racket[st]. This operation runs in constant
time for @tech{hash sets}. Has no fallback.
}
@defproc[(set-remove [st generic-set?] [v any/c]) generic-set?]{
Produces a set that includes all elements of @racket[st] except
@racket[v]. This operation runs in constant time for @tech{hash sets}. Has no fallback.
}
@defproc[(set-remove! [st generic-set?] [v any/c]) void?]{
Removes the element @racket[v] from @racket[st]. This operation runs in constant
time for @tech{hash sets}. Has no fallback.
}
@defproc[(set-empty? [st generic-set?]) boolean?]{
Returns @racket[#t] if @racket[st] has no members; returns @racket[#f]
otherwise.
Supported for any @racket[st] that @impl{implements} @racket[set->stream] or
@racket[set-count].
}
@defproc[(set-count [st generic-set?]) exact-nonnegative-integer?]{
Returns the number of elements in @racket[st].
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
}
@defproc[(set-first [st (and/c generic-set? (not/c set-empty?))]) any/c]{
Produces an unspecified element of @racket[st]. Multiple uses of
@racket[set-first] on @racket[st] produce the same result.
Supported for any @racket[st] that @impl{implements} @racket[set->stream].
}
@defproc[(set-rest [st (and/c generic-set? (not/c set-empty?))]) generic-set?]{
Produces a set that includes all elements of @racket[st] except
@racket[(set-first st)].
Supported for any @racket[st] that @impl{implements} @racket[set-remove] and either
@racket[set-first] or @racket[set->stream].
}
@defproc[(set->stream [st generic-set?]) stream?]{
Produces a stream containing the elements of @racket[st].
Supported for any @racket[st] that @impl{implements}:
@itemlist[@item{@racket[set->list]}
@item{@racket[in-set]}
@item{@racket[set-empty?], @racket[set-first], @racket[set-rest]}
@item{@racket[set-empty?], @racket[set-first], @racket[set-remove]}
@item{@racket[set-count], @racket[set-first], @racket[set-rest]}
@item{@racket[set-count], @racket[set-first], @racket[set-remove]}]
}
@defproc[(set-copy [st generic-set?]) generic-set?]{
Produces a new, mutable set of the same type and with the same elements as
@racket[st].
Supported for any @racket[st] that @supp{supports} @racket[set->stream] and
@impl{implements} @racket[set-copy-clear] and @racket[set-add!].
}
@defproc[(set-copy-clear [st generic-set?]) (and/c generic-set? set-empty?)]{
Produces a new, empty set of the same type, mutability, and key strength as
@racket[st].
A difference between @racket[set-copy-clear] and @racket[set-clear] is
that the latter conceptually iterates @racket[set-remove] on the given
set, and so it preserves any contract on the given set. The
@racket[set-copy-clear] function produces a new set without any
contracts.
The @racket[set-copy-clear] function must call concrete set constructors
and thus has no generic fallback.
}
@defproc[(set-clear [st generic-set?]) (and/c generic-set? set-empty?)]{
Produces a set like @racket[st] but with all elements removed.
Supported for any @racket[st] that @impl{implements} @racket[set-remove] and @supp{supports}
@racket[set->stream].
}
@defproc[(set-clear! [st generic-set?]) void?]{
Removes all elements from @racket[st].
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and either
@supp{supports} @racket[set->stream] or @impl{implements} @racket[set-first] and either @racket[set-count] or @racket[set-empty?].
}
@defproc[(set-union [st0 generic-set?] [st generic-set?] ...) generic-set?]{
Produces a set of the same type as @racket[st0] that includes the elements from
@racket[st0] and all of the @racket[st]s.
If @racket[st0] is a list, each @racket[st] must also be a list. This
operation runs on lists in time proportional to the total size of the
@racket[st]s times the size of the result.
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[set-union] to determine the type
of the resulting set (list, hash set, etc.). If there is a case where
@racket[set-union] may be applied to zero arguments, instead pass an empty set
of the intended type as the first argument.
Supported for any @racket[st] that @impl{implements} @racket[set-add] and @supp{supports} @racket[set->stream].
@examples[#:eval set-eval
(set-union (set))
(set-union (seteq))
(set-union (set 1 2) (set 2 3))
(set-union (list 1 2) (list 2 3))
(eval:error (set-union (set 1 2) (seteq 2 3))) (code:comment "Sets of different types cannot be unioned")
]}
@defproc[(set-union! [st0 generic-set?] [st generic-set?] ...) void?]{
Adds the elements from all of the @racket[st]s to @racket[st0].
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st]s.
Supported for any @racket[st] that @impl{implements} @racket[set-add!] and @supp{supports} @racket[set->stream].
}
@defproc[(set-intersect [st0 generic-set?] [st generic-set?] ...) generic-set?]{
Produces a set of the same type as @racket[st0] that includes the elements from
@racket[st0] that are also contained by all of the @racket[st]s.
If @racket[st0] is a list, each @racket[st] must also be a list. This
operation runs on lists in time proportional to the total size of the
@racket[st]s times the size of @racket[st0].
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st] that @impl{implements} either @racket[set-remove] or
both @racket[set-clear] and @racket[set-add], and @supp{supports} @racket[set->stream].
}
@defproc[(set-intersect! [st0 generic-set?] [st generic-set?] ...) void?]{
Removes every element from @racket[st0] that is not contained by all of the
@racket[st]s.
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st0].
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and @supp{supports} @racket[set->stream].
}
@defproc[(set-subtract [st0 generic-set?] [st generic-set?] ...) generic-set?]{
Produces a set of the same type as @racket[st0] that includes the elements from
@racket[st0] that are not contained by any of the @racket[st]s.
If @racket[st0] is a list, each @racket[st] must also be a list. This
operation runs on lists in time proportional to the total size of the
@racket[st]s times the size of @racket[st0].
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st0].
Supported for any @racket[st] that @impl{implements} either @racket[set-remove] or
both @racket[set-clear] and @racket[set-add], and @supp{supports} @racket[set->stream].
}
@defproc[(set-subtract! [st0 generic-set?] [st generic-set?] ...) void?]{
Removes every element from @racket[st0] that is contained by any of the
@racket[st]s.
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st0].
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and @supp{supports} @racket[set->stream].
}
@defproc[(set-symmetric-difference [st0 generic-set?] [st generic-set?] ...) generic-set?]{
Produces a set of the same type as @racket[st0] that includes all of the
elements contained an odd number of times in @racket[st0] and the
@racket[st]s.
If @racket[st0] is a list, each @racket[st] must also be a list. This
operation runs on lists in time proportional to the total size of the
@racket[st]s times the size of @racket[st0].
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st] that @impl{implements} @racket[set-remove] or both @racket[set-clear] and @racket[set-add], and @supp{supports} @racket[set->stream].
@examples[#:eval set-eval
(set-symmetric-difference (set 1) (set 1 2) (set 1 2 3))
]
}
@defproc[(set-symmetric-difference! [st0 generic-set?] [st generic-set?] ...) void?]{
Adds and removes elements of @racket[st0] so that it includes all of the
elements contained an odd number of times in the @racket[st]s and the
original contents of @racket[st0].
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st]s.
Supported for any @racket[st] that @impl{implements} @racket[set-remove!] and @supp{supports} @racket[set->stream].
}
@defproc[(set=? [st generic-set?] [st2 generic-set?]) boolean?]{
Returns @racket[#t] if @racket[st] and @racket[st2] contain the same
members; returns @racket[#f] otherwise.
If @racket[st0] is a list, each @racket[st] must also be a list. This
operation runs on lists in time proportional to the size of @racket[st] times
the size of @racket[st2].
If @racket[st0] is a @tech{hash set}, each @racket[st] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st] plus the size of @racket[st2].
Supported for any @racket[st] and @racket[st2] that both @supp{support}
@racket[subset?]; also supported for any if @racket[st2] that @impl{implements}
@racket[set=?] regardless of @racket[st].
@examples[#:eval set-eval
(set=? (list 1 2) (list 2 1))
(set=? (set 1) (set 1 2 3))
(set=? (set 1 2 3) (set 1))
(set=? (set 1 2 3) (set 1 2 3))
(set=? (seteq 1 2) (mutable-seteq 2 1))
(eval:error (set=? (seteq 1 2) (seteqv 1 2))) (code:comment "Sets of different types cannot be compared")
]
}
@defproc[(subset? [st generic-set?] [st2 generic-set?]) boolean?]{
Returns @racket[#t] if @racket[st2] contains every member of @racket[st];
returns @racket[#f] otherwise.
If @racket[st] is a list, then @racket[st2] must also be a list. This
operation runs on lists in time proportional to the size of @racket[st] times
the size of @racket[st2].
If @racket[st] is a @tech{hash set}, then @racket[st2] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st].
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
@examples[#:eval set-eval
(subset? (set 1) (set 1 2 3))
(subset? (set 1 2 3) (set 1))
(subset? (set 1 2 3) (set 1 2 3))
]
}
@defproc[(proper-subset? [st generic-set?] [st2 generic-set?]) boolean?]{
Returns @racket[#t] if @racket[st2] contains every member of @racket[st] and at
least one additional element; returns @racket[#f] otherwise.
If @racket[st] is a list, then @racket[st2] must also be a list. This
operation runs on lists in time proportional to the size of @racket[st] times
the size of @racket[st2].
If @racket[st] is a @tech{hash set}, then @racket[st2] must also be a
@tech{hash set} that uses the same comparison function (@racket[equal?],
@racket[eqv?], or @racket[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 @racket[st] plus the size of @racket[st2].
Supported for any @racket[st] and @racket[st2] that both @supp{support}
@racket[subset?].
@examples[#:eval set-eval
(proper-subset? (set 1) (set 1 2 3))
(proper-subset? (set 1 2 3) (set 1))
(proper-subset? (set 1 2 3) (set 1 2 3))
]
}
@defproc[(set->list [st generic-set?]) list?]{
Produces a list containing the elements of @racket[st].
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
}
@defproc[(set-map [st generic-set?]
[proc (any/c . -> . any/c)])
(listof any/c)]{
Applies the procedure @racket[proc] to each element in
@racket[st] in an unspecified order, accumulating the results
into a list.
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
}
@defproc[(set-for-each [st generic-set?]
[proc (any/c . -> . any)])
void?]{
Applies @racket[proc] to each element in @racket[st] (for the
side-effects of @racket[proc]) in an unspecified order.
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
}
@defproc[(in-set [st generic-set?]) sequence?]{
Explicitly converts a set to a sequence for use with @racket[for] and
other forms.
Supported for any @racket[st] that @supp{supports} @racket[set->stream].
}
@defproc[(impersonate-hash-set [st (or/c mutable-set? weak-set?)]
[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] ... ...)
(and/c (or/c mutable-set? weak-set?) impersonator?)]{
Impersonates @racket[st], redirecting various set operations via the given procedures.
The @racket[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 @racket[(set-member? s e)], @racket[e] will be passed to the
@racket[inject-proc] before comparing it with other elements of @racket[s].
The @racket[add-proc] procedure is called when adding an element to a set, e.g.,
via @racket[set-add] or @racket[set-add!]. The result of the @racket[add-proc] is
stored in the set.
The @racket[shrink-proc] procedure is called when building a new set with
one fewer element. For example, when evaluating @racket[(set-remove s e)]
or @racket[(set-remove! s e)],
an element is removed from a set, e.g.,
via @racket[set-remove] or @racket[set-remove!]. The result of the @racket[shrink-proc]
is the element actually removed from the set.
The @racket[extract-proc] procedure is called when an element is pulled out of
a set, e.g., by @racket[set-first]. The result of the @racket[extract-proc] is
the element actually produced by from the set.
The @racket[clear-proc] is called by @racket[set-clear] and @racket[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 @racket[clear-proc]
is @racket[#f], then clearing is done element by element (via calls into the other
supplied procedures).
The @racket[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
@racket[equal-key-proc] is used when computing the hash or comparing for equality.
If any of the @racket[inject-proc], @racket[add-proc], @racket[shrink-proc], or
@racket[extract-proc] arguments are @racket[#f], then they all must be @racket[#f],
the @racket[clear-proc] and @racket[equal-key-proc] must also be @racket[#f],
and there must be at least one property supplied.
Pairs of @racket[prop] and @racket[prop-val] (the number of arguments to
@racket[impersonate-hash-set] must be odd) add @tech{impersonator properties} or
override impersonator property values of @racket[st].
}
@defproc[(chaperone-hash-set [st (or/c set? mutable-set? weak-set?)]
[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] ... ...)
(and/c (or/c set? mutable-set? weak-set?) chaperone?)]{
Chaperones @racket[st]. Like @racket[impersonate-hash-set] but with
the constraints that the results of the @racket[inject-proc],
@racket[add-proc], @racket[shrink-proc], @racket[extract-proc], and
@racket[equal-key-proc] must be
@racket[chaperone-of?] their second arguments. Also, the input
may be an @racket[immutable?] set.
}
@section{Custom Hash Sets}
@defform[(define-custom-set-types name
optional-predicate
comparison-expr
optional-hash-functions)
#:grammar ([optional-predicate
(code:line)
(code:line #:elem? predicate-expr)]
[optional-hash-functions
(code:line)
(code:line hash1-expr)
(code:line hash1-expr hash2-expr)])]{
Creates a new hash set type based on the given comparison @racket[comparison-expr],
hash functions @racket[hash1-expr] and @racket[hash2-expr], and element
predicate @racket[predicate-expr]; the interfaces for these functions are the
same as in @racket[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:
@itemize[
@item{@racket[name]@racketidfont{?} recognizes instances of the new type,}
@item{@racketidfont{immutable-}@racket[name]@racketidfont{?} recognizes
immutable instances of the new type,}
@item{@racketidfont{mutable-}@racket[name]@racketidfont{?} recognizes
mutable instances of the new type with strongly-held elements,}
@item{@racketidfont{weak-}@racket[name]@racketidfont{?} recognizes
mutable instances of the new type with weakly-held elements,}
@item{@racketidfont{make-immutable-}@racket[name] constructs
immutable instances of the new type,}
@item{@racketidfont{make-mutable-}@racket[name] constructs
mutable instances of the new type with strongly-held elements, and}
@item{@racketidfont{make-weak-}@racket[name] constructs
mutable instances of the new type with weakly-held elements.}
]
The constructors all accept a stream as an optional argument, providing
initial elements.
@examples[
#:eval set-eval
(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)
(generic-set? mut)
(set? imm)
(generic-set? imm)
(string-set? imm)
(string-set? mut)
(immutable-string-set? imm)
(immutable-string-set? mut)
(set-member? imm "apple")
(set-member? mut "banana")
(equal? imm mut)
(set=? imm mut)
(set-remove! mut "banana")
(set-member? mut "banana")
(equal? (set-remove (set-remove imm "apple") "banana")
(make-immutable-string-set))
]
}
@defproc[(make-custom-set-types
[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? elem? (any/c . -> . boolean?) (const #true)]
[#:name name symbol? 'custom-set]
[#:for who symbol? 'make-custom-set-types])
(values (any/c . -> . boolean?)
(any/c . -> . boolean?)
(any/c . -> . boolean?)
(any/c . -> . boolean?)
(->* [] [stream?] generic-set?)
(->* [] [stream?] generic-set?)
(->* [] [stream?] generic-set?))]{
Creates a new set type based on the given comparison function @racket[eql?],
hash functions @racket[hash1] and @racket[hash2], and predicate @racket[elem?].
The new set type has variants that are immutable, mutable with strongly-held
elements, and mutable with weakly-held elements. The given @racket[name] is
used when printing instances of the new set type, and the symbol @racket[who]
is used for reporting errors.
The comparison function @racket[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 @racket[hash1] and @racket[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 @racket[elem?] must accept 1 argument and is used to recognize
valid elements for the new set type.
Produces seven values:
@itemize[
@item{a predicate recognizing all instances of the new set type,}
@item{a predicate recognizing immutable instances,}
@item{a predicate recognizing mutable instances,}
@item{a predicate recognizing weak instances,}
@item{a constructor for immutable instances,}
@item{a constructor for mutable instances, and}
@item{a constructor for weak instances.}
]
See @racket[define-custom-hash-types] for an example.
}
@close-eval[set-eval]