core/sets/sets-docs.factor

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