1 USING: assocs hashtables help.markup help.syntax kernel
5 ARTICLE: "sets" "Set-theoretic operations on sequences"
6 "Set-theoretic operations on sequences are defined on the " { $vocab-link "sets" } " vocabulary. All of these operations use hashtables internally to achieve linear running time."
10 "Test for duplicates:"
11 { $subsection all-unique? }
12 { $subsection duplicates }
13 "Set operations on sequences:"
15 { $subsection intersect }
17 "Set-theoretic predicates:"
18 { $subsection intersects? }
19 { $subsection subset? }
21 "A word used to implement the above:"
22 { $subsection unique }
23 "Adding elements to sets:"
24 { $subsection adjoin }
25 { $subsection conjoin }
26 { $see-also member? memq? any? all? "assocs-sets" } ;
31 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
32 { $description "Removes all elements equal to " { $snippet "elt" } ", and adds " { $snippet "elt" } " at the end of the sequence." }
35 "USING: namespaces prettyprint sets ;"
36 "V{ \"beans\" \"salsa\" \"cheese\" } \"v\" set"
37 "\"nachos\" \"v\" get adjoin"
38 "\"salsa\" \"v\" get adjoin"
40 "V{ \"beans\" \"cheese\" \"nachos\" \"salsa\" }"
43 { $side-effects "seq" } ;
46 { $values { "elt" object } { "assoc" assoc } }
47 { $description "Stores a key/value pair, both equal to " { $snippet "elt" } ", into the assoc." }
50 "USING: kernel prettyprint sets ;"
51 "H{ } clone 1 over conjoin ."
55 { $side-effects "assoc" } ;
58 { $values { "seq" "a sequence" } { "assoc" assoc } }
59 { $description "Outputs a new assoc where the keys and values are equal." }
61 { $example "USING: sets prettyprint ;" "{ 1 1 2 2 3 3 } unique ." "H{ { 1 1 } { 2 2 } { 3 3 } }" }
65 { $values { "seq" "a sequence" } { "newseq" "a sequence" } }
66 { $description "Outputs a new sequence with each distinct element of " { $snippet "seq" } " appearing only once. Elements are compared for equality using " { $link = } " and elements are ordered according to their position in " { $snippet "seq" } "." }
68 { $example "USING: sets prettyprint ;" "{ 1 1 t 3 t } prune ." "V{ 1 t 3 }" }
72 { $values { "seq" "a sequence" } { "newseq" "a sequence" } }
73 { $description "Outputs a new sequence consisting of elements which occur more than once in " { $snippet "seq" } "." }
75 { $example "USING: sets prettyprint ;" "{ 1 2 3 1 2 1 } duplicates ." "{ 1 2 1 }" }
79 { $values { "seq" sequence } { "?" "a boolean" } }
80 { $description "Tests whether a sequence contains any repeated elements." }
82 "USING: sets prettyprint ;"
83 "{ 0 1 1 2 3 5 } all-unique? ."
88 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
89 { $description "Outputs a sequence consisting of elements present in " { $snippet "seq1" } " but not " { $snippet "seq2" } ", comparing elements for equality."
91 { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } diff ." "{ 1 }" }
95 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
96 { $description "Outputs a sequence consisting of elements present in both " { $snippet "seq1" } " and " { $snippet "seq2" } "." }
98 { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } intersect ." "{ 2 3 }" }
102 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
103 { $description "Outputs a sequence consisting of elements present in " { $snippet "seq1" } " and " { $snippet "seq2" } " which does not contain duplicate values." }
105 { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } union ." "V{ 1 2 3 4 }" }
108 { diff intersect union } related-words
111 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
112 { $description "Tests if " { $snippet "seq1" } " and " { $snippet "seq2" } " have any elements in common." }
113 { $notes "If one of the sequences is empty, the result is always " { $link f } "." } ;
116 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
117 { $description "Tests if every element of " { $snippet "seq1" } " is contained in " { $snippet "seq2" } "." }
118 { $notes "If " { $snippet "seq1" } " is empty, the result is always " { $link t } "." } ;
121 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
122 { $description "Tests if both sequences contain the same elements, disregrading order and duplicates." } ;
126 { "seq" sequence } { "quot" quotation }
127 { "newseq" sequence } }
128 { $description "Maps a quotation onto a sequence, concatenates the results of the mapping, and removes duplicates." } ;