core/collections/sequence-combinators.facts

   1 IN: sequences
   2 USING: arrays help math sequences-internals ;
   3
   4 HELP: collect
   5 { $values { "n" "a non-negative integer" } { "quot" "a quotation with stack effect " { $snippet "( n -- value )" } } { "array" "an array with " { $snippet "n" } " elements" } }
   6 { $description "A primitive mapping operation that applies a quotation to all integers from 0 up to but not including " { $snippet "n" } ", and collects the results in a new array. User code should use " { $link map } " instead." } ;
   7
   8 HELP: each
   9 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- )" } } }
  10 { $description "Applies the quotation to each element of the sequence in turn." } ;
  11
  12 HELP: each-with
  13 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- )" } } }
  14 { $description "Variant of " { $link each } " which pushes a retained object on each invocation of the quotation." } ;
  15
  16 HELP: reduce
  17 { $values { "seq" "a sequence" } { "identity" "an object" } { "quot" "a quotation with stack effect " { $snippet "( prev elt -- next )" } } { "result" "the final result" } }
  18 { $description "Combines successive elements of the sequence using a binary operation, and outputs the final result. On the first iteration, the two inputs to the quotation are " { $snippet "identity" } ", and the first element of the sequence. On successive iterations, the first input is the result of the previous iteration, and the second input is the corresponding element of the sequence." }
  19 { $examples
  20     { $example "{ 1 5 3 } 0 [ + ] reduce ." "9" }
  21 } ;
  22
  23 HELP: accumulate
  24 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( prev elt -- next )" } } { "final" "the final result" } { "newseq" "a new sequence" } }
  25 { $description "Combines successive elements of the sequence using a binary operation, and outputs a sequence of intermediate results together with the final result. On the first iteration, the two inputs to the quotation are " { $snippet "identity" } ", and the first element of the sequence. On successive iterations, the first input is the result of the previous iteration, and the second input is the corresponding element of the sequence. Given the empty sequence, outputs a one-element sequence consisting of " { $snippet "identity" } "." }
  26 { $examples
  27     { $example "{ 2 2 2 2 2 } 0 [ + ] accumulate . ." "{ 0 2 4 6 8 }\n10" }
  28 } ;
  29
  30 HELP: map
  31 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } { "newseq" "a new sequence" } }
  32 { $description "Applies the quotation to each element yielding a new element. The new elements are collected into a sequence of the same class as the input sequence." } ;
  33
  34 HELP: map-with
  35 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- new )" } } { "newseq" "a new sequence" } }
  36 { $description "Variant of " { $link map } " which pushes a retained object on each invocation of the quotation." } ;
  37
  38 HELP: change-nth
  39 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- newelt )" } } }
  40 { $description "Applies the quotation to the " { $snippet "i" } "th element of the sequence, storing the result back into the sequence." }
  41 { $errors "Throws an error if the sequence is immutable, if the index is out of bounds, or the sequence cannot hold elements of the type output by " { $snippet "quot" } "." }
  42 { $side-effects "seq" } ;
  43
  44 HELP: inject
  45 { $values { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } }
  46 { $description "Applies the quotation to each element yielding a new element, storing the new elements back in the original sequence." }
  47 { $errors "Throws an error if the sequence is immutable, or the sequence cannot hold elements of the type output by " { $snippet "quot" } "." }
  48 { $side-effects "seq" } ;
  49
  50 HELP: inject-with
  51 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- new )" } } }
  52 { $description "Variant of " { $link inject } " which pushes a retained object on each invocation of the quotation." } ;
  53
  54 HELP: min-length
  55 { $values { "seq1" "a sequence" } { "seq2" "a sequence" } { "n" "a non-negative integer" } }
  56 { $description "Outputs the minimum of the lengths of the two sequences." } ;
  57
  58 HELP: max-length
  59 { $values { "seq1" "a sequence" } { "seq2" "a sequence" } { "n" "a non-negative integer" } }
  60 { $description "Outputs the maximum of the lengths of the two sequences." } ;
  61
  62 HELP: 2each
  63 { $values { "seq1" "a sequence" } { "seq2" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- )" } } }
  64 { $description "Applies the quotation to pairs of elements from " { $snippet "seq1" } " and " { $snippet "seq2" } "." }
  65 { $notes "If one sequence is shorter than the other, than only the prefix having the length of the minimum of the two is examined." } ;
  66
  67 HELP: 2reduce
  68 { $values { "seq1" "a sequence" }
  69           { "seq2" "a sequence" }
  70           { "identity" "an object" }
  71           { "quot" "a quotation with stack effect "
  72                    { $snippet "( prev elt1 elt2 -- next )" } }
  73           { "result" "the final result" } }
  74 { $description "Combines successive pairs of elements from the two sequences using a ternary operation. The first input value at each iteration except the first one is the result of the previous iteration. The first input value at the first iteration is " { $snippet "identity" } "." }
  75 { $examples "The " { $link v. } " word provides a particularly elegant implementation of the dot product." }
  76 { $notes "If one sequence is shorter than the other, then only the prefix having the length of the minimum of the two is examined." } ;
  77
  78 HELP: 2map
  79 { $values { "seq1" "a sequence" } { "seq2" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- new )" } } { "newseq" "a new sequence" } }
  80 { $description "Applies the quotation to each pair of elements in turn, yielding new elements which are collected into a new sequence having the same class as " { $snippet "seq1" } "." }
  81 { $see-also v+ v- v* v/ }
  82 { $notes "If one sequence is shorter than the other, than only the prefix having the length of the minimum of the two is examined." } ;
  83
  84 HELP: find
  85 { $values { "seq" "a sequence" }
  86           { "quot" "a quotation with stack effect "
  87                    { $snippet "( elt -- ? )" } }
  88           { "i" "the index of the first match, or -1" }
  89           { "elt" "the first matching element, or " { $link f } } }
  90 { $description "A simpler variant of " { $link find* } " where the starting index is 0." } ;
  91
  92 HELP: find-with
  93 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "i" "the index of the first match, or -1" } { "elt" "the first matching element, or " { $link f } } }
  94 { $description "Variant of " { $link find } " which pushes a retained object on each invocation of the quotation." } ;
  95
  96 HELP: find*
  97 { $values { "n" "a starting index" }
  98           { "seq" "a sequence" }
  99           { "quot" "a quotation with stack effect "
 100                    { $snippet "( elt -- ? )" } }
 101           { "i" "the index of the first match, or -1" }
 102           { "elt" "the first matching element, or " { $link f } } }
 103 { $description "Applies the quotation to each element of the sequence in turn, until it outputs a true value or the end of the sequence is reached. If the quotation yields a true value for some sequence element, the word outputs the element index and the element itself. Otherwise, the word outputs an index of -1 and " { $link f } " as the element." } ;
 104
 105 HELP: find-with*
 106 { $values { "obj" "an object" } { "n" "a starting index" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "i" "the index of the first match, or -1" } { "elt" "the first matching element, or " { $link f } } }
 107 { $description "Variant of " { $link find* } " which pushes a retained object on each invocation of the quotation." } ;
 108
 109 HELP: find-last
 110 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "i" "the index of the first match, or -1" } { "elt" "the first matching element, or " { $link f } } }
 111 { $description "A simpler variant of " { $link find-last* } " where the starting index is one less than the length of the sequence." } ;
 112
 113 HELP: find-last-with
 114 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "i" "the index of the first match, or -1" } { "elt" "the first matching element, or " { $link f } } }
 115 { $description "Variant of " { $link find } " which pushes a retained object on each invocation of the quotation." } ;
 116
 117 HELP: find-last*
 118 { $values { "n" "a starting index" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "i" "the index of the first match, or -1" } { "elt" "the first matching element, or " { $link f } } }
 119 { $description "Applies the quotation to each element of the sequence in reverse order, until it outputs a true value or the start of the sequence is reached. If the quotation yields a true value for some sequence element, the word outputs the element index and the element itself. Otherwise, the word outputs an index of -1 and " { $link f } " as the element." } ;
 120
 121 HELP: find-last-with*
 122 { $values { "obj" "an object" } { "n" "a starting index" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "i" "the index of the first match, or -1" } { "elt" "the first matching element, or " { $link f } } }
 123 { $description "Variant of " { $link find } " which pushes a retained object on each invocation of the quotation." } ;
 124
 125 HELP: contains?
 126 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "?" "a boolean" } }
 127 { $description "Tests if the sequence contains an element satisfying the predicate, by applying the predicate to each element in turn until a true value is found. If the sequence is empty or if the end of the sequence is reached, outputs " { $link f } "." } ;
 128
 129 HELP: contains-with?
 130 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "?" "a boolean" } }
 131 { $description "Variant of " { $link contains? } " which pushes a retained object on each invocation of the quotation." } ;
 132
 133 HELP: all?
 134 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "?" "a boolean" } }
 135 { $description "Tests if all elements in the sequence satisfy the predicate by checking each element in turn. Given an empty sequence, vacuously outputs " { $link t } "." }
 136 { $notes
 137     "The implementation makes use of a well-known logical identity:"
 138     $terpri
 139     { $snippet "P[x] for all x <==> not ((not P[x]) for some x)" }
 140 } ;
 141
 142 HELP: all-with?
 143 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "?" "a boolean" } }
 144 { $description "Variant of " { $link all? } " which pushes a retained object on each invocation of the quotation." } ;
 145
 146 HELP: subset*
 147 { $values { "flags" "a sequence" } { "seq" "a sequence" } { "subseq" "a new sequence" } }
 148 { $description "Outputs a new sequence containing all elements of " { $snippet "seq" } " such that the corresponding element of " { $snippet "flags" } " is not equal to " { $link f } "." }
 149 { $examples
 150     { $example "{ t f t f } { 1 2 3 4 } subset* ." "{ 1 3 }" }
 151 } ;
 152
 153 HELP: subset
 154 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "subseq" "a new sequence" } }
 155 { $description "Applies the quotation to each element in turn, and outputs a new sequence containing the elements of the original sequence for which the quotation output a true value." } ;
 156
 157 HELP: subset-with
 158 { $values { "obj" "an object" } { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( obj elt -- ? )" } } { "subseq" "a new sequence" } }
 159 { $description "Variant of " { $link subset } " which pushes a retained object on each invocation of the quotation." } ;
 160
 161 HELP: monotonic?
 162 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt elt -- ? )" } } { "?" "a boolean" } }
 163 { $description "Applies the relation to successive pairs of elements in the sequence, testing for a truth value. The relation should be a transitive relation, such as a total order or an equality relation." }
 164 { $examples
 165     "Testing if a sequence is non-decreasing:"
 166     { $example "{ 1 1 2 } [ <= ] monotonic? ." "t" }
 167     "Testing if a sequence is decreasing:"
 168     { $example "{ 9 8 6 7 } [ < ] monotonic? ." "f" }
 169 }
 170 { $see-also all-eq? all-equal? } ;
 171
 172 HELP: interleave
 173 { $values { "seq" "a sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- )" } } { "between" "a quotation" } }
 174 { $description "Applies " { $snippet "quot" } " to each element in turn, also invoking " { $snippet "between" } " in-between each pair of elements." }
 175 { $example "{ \"a\" \"b\" \"c\" } [ write ] [ \"X\" write ] interleave" "aXbXc" } ;
 176
 177 HELP: cache-nth
 178 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( i -- elt )" } } }
 179 { $description "If the sequence does not contain at least " { $snippet "i" } " elements or if the " { $snippet "i" } "th element of the sequence is " { $link f } ", calls the quotation to produce a new value, and stores it back into the sequence. Otherwise, this word outputs the " { $snippet "i" } "th element of the sequence." }
 180 { $side-effects "seq" } ;
 181
 182 HELP: copy-into
 183 { $values { "n" "an index in " { $snippet "dest" } } { "dest" "a mutable sequence" } { "src" "a sequence" } }
 184 { $description "Copies all elements of " { $snippet "src" } " to " { $snippet "dest" } ", with destination indices starting from " { $snippet "n" } ". Grows " { $snippet "to" } " first if necessary." }
 185 { $errors "An error is thrown if " { $snippet "to" } " is not resizable, and not large enough to hold the copied elements." } ;
 186
 187 HELP: >sequence
 188 { $values { "seq" "a sequence" } { "pred" "a quotation with stack effect " { $snippet "( seq -- ? )" } } { "quot" "a quotation with stack effect " { $snippet "( n -- newseq )" } } { "newseq" "a new sequence" } }
 189 { $description "If " { $snippet "pred" } " answers a true value given " { $snippet "seq" } ", clones " { $snippet "seq" } ". Otherwise, calls " { $snippet "quot" } " with the length of " { $snippet "seq" } ", creating a new sequence, and copies the contents of " { $snippet "seq" } " into the new sequence." }
 190 { $notes "This word is used to implement words which convert one type of sequence into another, for example " { $link >array } "." } ;