core/sets/sets-docs.factor

   1 USING: assocs help.markup help.syntax kernel
   2 sequences vectors ;
   3 IN: sets
   4
   5 ARTICLE: "sets" "Sets"
   6 "A set is an unordered collection of elements. Words for working with sets are in the " { $vocab-link "sets" } " vocabulary." $nl
   7 "All sets are instances of a mixin class:"
   8 { $subsections
   9     set
  10     set?
  11 }
  12 { $subsections "set-operations" "set-implementations" } ;
  13
  14 ABOUT: "sets"
  15
  16 ARTICLE: "set-operations" "Operations on sets"
  17 "To test if an object is a member of a set:"
  18 { $subsections in? }
  19 "All sets can be represented as a sequence, without duplicates, of their members:"
  20 { $subsections members }
  21 "To get the number of elements in a set:"
  22 { $subsections cardinality }
  23 "Sets can have members added or removed destructively:"
  24 { $subsections
  25     adjoin
  26     delete
  27     clear-set
  28     union!
  29     diff!
  30     intersect!
  31 }
  32 "To test if a set is the empty set:"
  33 { $subsections null? }
  34 "Basic mathematical operations, which any type of set may override for efficiency:"
  35 { $subsections
  36     diff
  37     intersect
  38     union
  39 }
  40 "Mathematical predicates on sets, which may be overridden for efficiency:"
  41 { $subsections
  42     intersects?
  43     subset?
  44     set=
  45 }
  46 "Operations on groups of sets:"
  47 { $subsections
  48     union-all
  49     intersect-all
  50 }
  51 "An optional generic word for creating sets of the same class as a given set:"
  52 { $subsections set-like }
  53 "An optional generic word for creating a set with a fast lookup operation, if the set itself has a slow lookup operation:"
  54 { $subsections fast-set }
  55 "For set types that allow duplicates, like sequence sets, some additional words test for duplication:"
  56 { $subsections
  57     all-unique?
  58     duplicates
  59 }
  60 "Utilities for sets and sequences:"
  61 { $subsections
  62      within
  63      without
  64 } ;
  65
  66 ARTICLE: "set-implementations" "Set implementations"
  67 "There are several implementations of sets in the Factor library. More can be added if they implement the words of the set protocol, the basic set operations."
  68 { $subsections
  69     "sequence-sets"
  70     "hash-sets"
  71     "bit-sets"
  72 } ;
  73
  74 ARTICLE: "sequence-sets" "Sequences as sets"
  75 "Any sequence can be used as a set. The members of this set are the elements of the sequence. Calling the word " { $link members } " on a sequence returns a copy of the sequence with only one listing of each member. Destructive operations " { $link adjoin } " and " { $link delete } " only work properly on growable sequences like " { $link vector } "s."
  76 $nl
  77 "Care must be taken in writing efficient code using sequence sets. Testing for membership with " { $link in? } ", as well as the destructive set operations, take time proportional to the size of the sequence. Another representation, like " { $link "hash-sets" } ", would take constant time for membership tests. But binary operations like " { $link union } " are asymptotically optimal, taking time proportional to the sum of the size of the inputs."
  78 $nl
  79 "As one particular example, " { $link POSTPONE: f } " is a representation of the empty set, since it is an empty sequence." ;
  80
  81 HELP: set
  82 { $class-description "The class of all sets. Custom implementations of the set protocol should be declared as instances of this mixin for all set implementation to work correctly." } ;
  83
  84 HELP: adjoin
  85 { $values { "elt" object } { "set" set } }
  86 { $description "Destructively adds " { $snippet "elt" } " to " { $snippet "set" } ". For sequences, this guarantees that this element is not duplicated, and that it is at the end of the sequence." $nl "Each mutable set type is expected to implement a method on this generic word." }
  87 { $examples
  88     { $example
  89         "USING: prettyprint sets kernel ;"
  90         "V{ \"beans\" \"salsa\" \"cheese\" } clone"
  91         "\"nachos\" over adjoin"
  92         "\"salsa\" over adjoin"
  93         "."
  94         "V{ \"beans\" \"cheese\" \"nachos\" \"salsa\" }"
  95     }
  96 }
  97 { $side-effects "set" } ;
  98
  99 HELP: ?adjoin
 100 { $values { "elt" object } { "set" set } { "?" boolean } }
 101 { $description "A version of " { $link adjoin } " which returns whether the element was added to the set." } ;
 102
 103 HELP: delete
 104 { $values { "elt" object } { "set" set } }
 105 { $description "Destructively removes " { $snippet "elt" } " from " { $snippet "set" } ". If the element is not present, this does nothing." $nl "Each mutable set type is expected to implement a method on this generic word." }
 106 { $side-effects "set" } ;
 107
 108 HELP: ?delete
 109 { $values { "elt" object } { "set" set } { "?" boolean } }
 110 { $description "A version of " { $link delete } " which returns whether the element was removed from the set." } ;
 111
 112 HELP: clear-set
 113 { $values { "set" set } }
 114 { $contract "Removes all entries from the set." }
 115 { $side-effects "set" } ;
 116
 117 HELP: members
 118 { $values { "set" set } { "seq" sequence } }
 119 { $description "Creates a sequence with a single copy of each member of the set." $nl "Each set type is expected to implement a method on this generic word." }
 120 { $notes "This will preserve the ordering of unique elements when called on a " { $link sequence } "." } ;
 121
 122 HELP: in?
 123 { $values { "elt" object } { "set" set } { "?" boolean } }
 124 { $description "Tests whether the element is a member of the set." $nl "Each set type is expected to implement a method on this generic word as part of the set protocol." } ;
 125
 126 HELP: adjoin-at
 127 { $values { "value" object } { "key" object } { "assoc" assoc } }
 128 { $description "Adds " { $snippet "value" } " to the set stored at " { $snippet "key" } " of " { $snippet "assoc" } "." }
 129 { $side-effects "assoc" } ;
 130
 131 HELP: duplicates
 132 { $values { "set" set } { "seq" sequence } }
 133 { $description "Outputs a sequence consisting of elements which occur more than once in " { $snippet "set" } "." }
 134 { $examples
 135     { $example "USING: sets prettyprint ;" "{ 1 2 3 1 2 1 } duplicates ." "{ 1 2 1 }" }
 136 } ;
 137
 138 HELP: all-unique?
 139 { $values { "set" set } { "?" boolean } }
 140 { $description "Tests whether a set contains any repeated elements." }
 141 { $example
 142     "USING: sets prettyprint ;"
 143     "{ 0 1 1 2 3 5 } all-unique? ."
 144     "f"
 145 } ;
 146
 147 HELP: diff
 148 { $values { "set1" set } { "set2" set } { "set" set } }
 149 { $description "Outputs a set consisting of elements present in " { $snippet "set1" } " but not " { $snippet "set2" } ", comparing elements for equality." $nl "This word has a default definition which works for all sets, but set implementations may override the default for efficiency."
 150 } { $examples
 151     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } diff ." "{ 1 }" }
 152 } ;
 153
 154 HELP: intersect
 155 { $values { "set1" set } { "set2" set } { "set" set } }
 156 { $description "Outputs a set consisting of elements present in both " { $snippet "set1" } " and " { $snippet "set2" } "."
 157 "This word has a default definition which works for all sets, but set implementations may override the default for efficiency." }
 158 { $examples
 159     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } intersect ." "{ 2 3 }" }
 160 } ;
 161
 162 HELP: union
 163 { $values { "set1" set } { "set2" set } { "set" set } }
 164 { $description "Outputs a set consisting of elements present in either " { $snippet "set1" } " or " { $snippet "set2" } " which does not contain duplicate values." $nl "This word has a default definition which works for all sets, but set implementations may override the default for efficiency." }
 165 { $examples
 166     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } union ." "{ 1 2 3 4 }" }
 167 } ;
 168
 169 { diff intersect union } related-words
 170
 171 HELP: union!
 172 { $values { "set1" set } { "set2" set } }
 173 { $description "Adds all members from " { $snippet "set2" } " to " { $snippet "set1" } "." }
 174 { $side-effects "set1" } ;
 175
 176 HELP: diff!
 177 { $values { "set1" set } { "set2" set } }
 178 { $description "Removes all members from " { $snippet "set1" } " contained in " { $snippet "set2" } "." }
 179 { $side-effects "set1" } ;
 180
 181 HELP: intersect!
 182 { $values { "set1" set } { "set2" set } }
 183 { $description "Removes all members from " { $snippet "set1" } " not contained in " { $snippet "set2" } "." }
 184 { $side-effects "set1" } ;
 185
 186 HELP: intersects?
 187 { $values { "set1" set } { "set2" set } { "?" boolean } }
 188 { $description "Tests if " { $snippet "set1" } " and " { $snippet "set2" } " have any elements in common." }
 189 { $notes "If one of the sets is empty, the result is always " { $link f } "." } ;
 190
 191 HELP: subset?
 192 { $values { "set1" set } { "set2" set } { "?" boolean } }
 193 { $description "Tests if every element of " { $snippet "set1" } " is contained in " { $snippet "set2" } "." }
 194 { $notes "If " { $snippet "set1" } " is empty, the result is always " { $link t } "." } ;
 195
 196 HELP: set=
 197 { $values { "set1" set } { "set2" set } { "?" boolean } }
 198 { $description "Tests if both sets contain the same elements, disregarding order and duplicates." } ;
 199
 200 HELP: gather
 201 { $values
 202      { "seq" sequence } { "quot" { $quotation ( ... elt -- ... elts ) } }
 203      { "newseq" sequence } }
 204 { $description "Maps a quotation over a sequence, concatenates the results of the mapping, and removes duplicates." } ;
 205
 206 HELP: set-like
 207 { $values { "set" set } { "exemplar" set } { "set'" set } }
 208 { $description "If the conversion is defined for the exemplar, converts the set into a set of the exemplar's class. This is not guaranteed to create a new set, for example if the input set and exemplar are of the same class." $nl "Set implementations may optionally implement a method on this generic word. The default implementation returns its input set." }
 209 { $examples
 210     { $example "USING: sets prettyprint ;" "{ 1 2 3 } HS{ } set-like ." "HS{ 1 2 3 }" }
 211 } ;
 212
 213 HELP: within
 214 { $values { "seq" sequence } { "set" set } { "subseq" sequence } }
 215 { $description "Returns the subsequence of the given sequence consisting of members of the set. This may contain duplicates, if the sequence has duplicates." } ;
 216
 217 HELP: without
 218 { $values { "seq" sequence } { "set" set } { "subseq" sequence } }
 219 { $description "Returns the subsequence of the given sequence consisting of things that are not members of the set. This may contain duplicates, if the sequence has duplicates." } ;
 220
 221 HELP: null?
 222 { $values { "set" set } { "?" boolean } }
 223 { $description "Tests whether the given set is empty. This outputs " { $snippet "t" } " when given a null set of any type." } ;
 224
 225 HELP: cardinality
 226 { $values { "set" set } { "n" "a non-negative integer" } }
 227 { $description "Returns the number of elements in the set. All sets support this operation." } ;
 228
 229 HELP: intersect-all
 230 { $values { "sets" sequence } { "set/f" { $maybe set } } }
 231 { $description "Outputs the intersection of all the sets of the sequence " { $snippet "sets" } ", or " { $link f } " if " { $snippet "sets" } " is empty." } ;
 232
 233 HELP: union-all
 234 { $values { "sets" { $sequence set } } { "set/f" { $maybe set } } }
 235 { $description "Outputs the union of a sequence of sets, or " { $link f } " if the sequence is empty." } ;