core/sets/sets-docs.factor

   1 USING: assocs hashtables help.markup help.syntax kernel
   2 quotations sequences vectors ;
   3 IN: sets
   4
   5 ARTICLE: "sets" "Sets"
   6 "A set is an unordered list of elements. Words for working with sets are in the " { $vocab-link "sets" } " vocabulary."
   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 { $subsection member? }
  19 "All sets can be represented as a sequence, without duplicates, of their members:"
  20 { $subsection members }
  21 "Sets can have members added or removed destructively:"
  22 { $subsections
  23     adjoin
  24     delete
  25 }
  26 "Basic mathematical operations, which any type of set may override for efficiency:"
  27 { $subsections
  28     diff
  29     intersect
  30     union
  31 }
  32 "Mathematical predicates on sets, which may be overridden for efficiency:"
  33 { $subsections
  34     intersects?
  35     subset?
  36     set=
  37 }
  38 "An optional generic word for creating sets of the same class as a given set:"
  39 { $subsection set-like }
  40 "An optional generic word for creating a set with a fast lookup operation, if the set itself has a slow lookup operation:"
  41 { $subsection fast-set }
  42 "For set types that allow duplicates, like sequence sets, some additional words test for duplication:"
  43 { $subsections
  44     all-unique?
  45     duplicates
  46 } ;
  47
  48 ARTICLE: "set-implementations" "Set implementations"
  49 "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."
  50 { $subsections
  51     "sequence-sets"
  52     "hash-sets"
  53     "bit-sets"
  54 } ;
  55
  56 ARTICLE: "sequence-sets" "Sequences as sets"
  57 "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."
  58 $nl
  59 "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."
  60 $nl
  61 "As one particlar example, " { $link POSTPONE: f } " is a representation of the empty set, as it represents the empty sequence." ;
  62
  63 HELP: set
  64 { $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." } ;
  65
  66 HELP: adjoin
  67 { $values { "elt" object } { "set" set } }
  68 { $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." }
  69 { $examples
  70     { $example
  71         "USING: namespaces prettyprint sets ;"
  72         "V{ \"beans\" \"salsa\" \"cheese\" } \"v\" set"
  73         "\"nachos\" \"v\" get adjoin"
  74         "\"salsa\" \"v\" get adjoin"
  75         "\"v\" get ."
  76         "V{ \"beans\" \"cheese\" \"nachos\" \"salsa\" }"
  77     }
  78 }
  79 { $side-effects "set" } ;
  80
  81 HELP: delete
  82 { $values { "elt" object } { "set" set } }
  83 { $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." }
  84 { $side-effects "set" } ;
  85
  86 HELP: members
  87 { $values { "set" set } { "seq" sequence } }
  88 { $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." } ;
  89
  90 HELP: in?
  91 { $values { "elt" object } { "set" set } { "?" "a boolean" } }
  92 { $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." } ;
  93
  94 HELP: adjoin-at
  95 { $values { "value" object } { "key" object } { "assoc" assoc } }
  96 { $description "Adds " { $snippet "value" } " to the set stored at " { $snippet "key" } " of " { $snippet "assoc" } "." }
  97 { $side-effects "assoc" } ;
  98
  99 HELP: duplicates
 100 { $values { "set" set } { "seq" sequence } }
 101 { $description "Outputs a sequence consisting of elements which occur more than once in " { $snippet "set" } "." }
 102 { $examples
 103     { $example "USING: sets prettyprint ;" "{ 1 2 3 1 2 1 } duplicates ." "{ 2 1 2 1 }" }
 104 } ;
 105
 106 HELP: all-unique?
 107 { $values { "set" set } { "?" "a boolean" } }
 108 { $description "Tests whether a set contains any repeated elements." }
 109 { $example
 110     "USING: sets prettyprint ;"
 111     "{ 0 1 1 2 3 5 } all-unique? ."
 112     "f"
 113 } ;
 114
 115 HELP: diff
 116 { $values { "set1" set } { "set2" set } { "set" set } }
 117 { $description "Outputs a set consisting of elements present in " { $snippet "set1" } " but not " { $snippet "set2" } ", comparing elements for equality."
 118 "This word has a default definition which works for all sets, but set implementations may override the default for efficiency."
 119 } { $examples
 120     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } diff ." "{ 1 }" }
 121 } ;
 122
 123 HELP: intersect
 124 { $values { "set1" set } { "set2" set } { "set" set } }
 125 { $description "Outputs a set consisting of elements present in both " { $snippet "set1" } " and " { $snippet "set2" } "."
 126 "This word has a default definition which works for all sets, but set implementations may override the default for efficiency." }
 127 { $examples
 128     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } intersect ." "{ 2 3 }" }
 129 } ;
 130
 131 HELP: union
 132 { $values { "set1" set } { "set2" set } { "set" set } }
 133 { $description "Outputs a set consisting of elements present in either " { $snippet "set1" } " or " { $snippet "set2" } " which does not contain duplicate values."
 134 "This word has a default definition which works for all sets, but set implementations may override the default for efficiency." }
 135 { $examples
 136     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } union ." "{ 1 2 3 4 }" }
 137 } ;
 138
 139 { diff intersect union } related-words
 140
 141 HELP: intersects?
 142 { $values { "set1" set } { "set2" set } { "?" "a boolean" } }
 143 { $description "Tests if " { $snippet "set1" } " and " { $snippet "set2" } " have any elements in common." }
 144 { $notes "If one of the sets is empty, the result is always " { $link f } "." } ;
 145
 146 HELP: subset?
 147 { $values { "set1" set } { "set2" set } { "?" "a boolean" } }
 148 { $description "Tests if every element of " { $snippet "set1" } " is contained in " { $snippet "set2" } "." }
 149 { $notes "If " { $snippet "set1" } " is empty, the result is always " { $link t } "." } ;
 150
 151 HELP: set=
 152 { $values { "set1" set } { "set2" set } { "?" "a boolean" } }
 153 { $description "Tests if both sets contain the same elements, disregrading order and duplicates." } ;
 154
 155 HELP: gather
 156 { $values
 157      { "seq" sequence } { "quot" quotation }
 158      { "newseq" sequence } }
 159 { $description "Maps a quotation onto a sequence, concatenates the results of the mapping, and removes duplicates." } ;
 160
 161 HELP: set-like
 162 { $values { "set" set } { "exemplar" set } { "set'" set } }
 163 { $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
 164 "Set implementations may optionally implement a method on this generic word. The default implementation returns its input set." }
 165 { $examples
 166     { $example "USING: sets prettyprint ;" "{ 1 2 3 } HS{ } set-like ." "HS{ 1 2 3 }" }
 167 } ;