core/sets/sets-docs.factor

   1 USING: kernel help.markup help.syntax sequences quotations ;
   2 IN: sets
   3
   4 ARTICLE: "sets" "Set-theoretic operations on sequences"
   5 "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."
   6 $nl
   7 "Remove duplicates:"
   8 { $subsection prune }
   9 "Test for duplicates:"
  10 { $subsection all-unique? }
  11 { $subsection duplicates }
  12 "Set operations on sequences:"
  13 { $subsection diff }
  14 { $subsection intersect }
  15 { $subsection union }
  16 "Set-theoretic predicates:"
  17 { $subsection intersects? }
  18 { $subsection subset? }
  19 { $subsection set= }
  20 "A word used to implement the above:"
  21 { $subsection unique }
  22 "Adding elements to sets:"
  23 { $subsection adjoin }
  24 { $subsection conjoin }
  25 { $see-also member? memq? contains? all? "assocs-sets" } ;
  26
  27 ABOUT: "sets"
  28
  29 HELP: adjoin
  30 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
  31 { $description "Removes all elements equal to " { $snippet "elt" } ", and adds " { $snippet "elt" } " at the end of the sequence." }
  32 { $examples
  33     { $example
  34         "USING: namespaces prettyprint sets ;"
  35         "V{ \"beans\" \"salsa\" \"cheese\" } \"v\" set"
  36         "\"nachos\" \"v\" get adjoin"
  37         "\"salsa\" \"v\" get adjoin"
  38         "\"v\" get ."
  39         "V{ \"beans\" \"cheese\" \"nachos\" \"salsa\" }"
  40     }
  41 }
  42 { $side-effects "seq" } ;
  43
  44 HELP: conjoin
  45 { $values { "elt" object } { "assoc" "an assoc" } }
  46 { $description "Stores a key/value pair, both equal to " { $snippet "elt" } ", into the assoc." }
  47 { $examples
  48     { $example
  49         "USING: kernel prettyprint sets ;"
  50         "H{ } clone 1 over conjoin ."
  51         "H{ { 1 1 } }"
  52     }
  53 }
  54 { $side-effects "assoc" } ;
  55
  56 HELP: unique
  57 { $values { "seq" "a sequence" } { "assoc" "an assoc" } }
  58 { $description "Outputs a new assoc where the keys and values are equal." }
  59 { $examples
  60     { $example "USING: sets prettyprint ;" "{ 1 1 2 2 3 3 } unique ." "H{ { 1 1 } { 2 2 } { 3 3 } }" }
  61 } ;
  62
  63 HELP: prune
  64 { $values { "seq" "a sequence" } { "newseq" "a sequence" } }
  65 { $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" } "." }
  66 { $examples
  67     { $example "USING: sets prettyprint ;" "{ 1 1 t 3 t } prune ." "V{ 1 t 3 }" }
  68 } ;
  69
  70 HELP: duplicates
  71 { $values { "seq" "a sequence" } { "newseq" "a sequence" } }
  72 { $description "Outputs a new sequence consisting of elements which occur more than once in " { $snippet "seq" } "." }
  73 { $examples
  74     { $example "USING: sets prettyprint ;" "{ 1 2 3 1 2 1 } duplicates ." "{ 1 2 1 }" }
  75 } ;
  76
  77 HELP: all-unique?
  78 { $values { "seq" sequence } { "?" "a boolean" } }
  79 { $description "Tests whether a sequence contains any repeated elements." }
  80 { $example
  81     "USING: sets prettyprint ;"
  82     "{ 0 1 1 2 3 5 } all-unique? ."
  83     "f"
  84 } ;
  85
  86 HELP: diff
  87 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
  88 { $description "Outputs a sequence consisting of elements present in " { $snippet "seq1" } " but not " { $snippet "seq2" } ", comparing elements for equality."
  89 } { $examples
  90     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } diff ." "{ 1 }" }
  91 } ;
  92
  93 HELP: intersect
  94 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
  95 { $description "Outputs a sequence consisting of elements present in both " { $snippet "seq1" } " and " { $snippet "seq2" } "." }
  96 { $examples
  97     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } intersect ." "{ 2 3 }" }
  98 } ;
  99
 100 HELP: union
 101 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
 102 { $description "Outputs a sequence consisting of elements present in " { $snippet "seq1" } " and " { $snippet "seq2" } " which does not contain duplicate values." }
 103 { $examples
 104     { $example "USING: sets prettyprint ;" "{ 1 2 3 } { 2 3 4 } union ." "V{ 1 2 3 4 }" }
 105 } ;
 106
 107 { diff intersect union } related-words
 108
 109 HELP: intersects?
 110 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 111 { $description "Tests if " { $snippet "seq1" } " and " { $snippet "seq2" } " have any elements in common." }
 112 { $notes "If one of the sequences is empty, the result is always " { $link f } "." } ;
 113
 114 HELP: subset?
 115 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 116 { $description "Tests if every element of " { $snippet "seq1" } " is contained in " { $snippet "seq2" } "." }
 117 { $notes "If " { $snippet "seq1" } " is empty, the result is always " { $link t } "." } ;
 118
 119 HELP: set=
 120 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 121 { $description "Tests if both sequences contain the same elements, disregrading order and duplicates." } ;
 122
 123 HELP: gather
 124 { $values
 125      { "seq" sequence } { "quot" quotation }
 126      { "newseq" sequence } }
 127 { $description "Maps a quotation onto a sequence, concatenates the results of the mapping, and removes duplicates." } ;