core/sequences/sequences-docs.factor

   1 USING: arrays help.markup help.syntax math
   2 sequences.private vectors strings kernel math.order layouts
   3 quotations ;
   4 IN: sequences
   5
   6 HELP: sequence
   7 { $class-description "A mixin class whose instances are sequences. Custom implementations of the sequence protocol should be declared as instances of this mixin for all sequence functionality to work correctly:"
   8     { $code "INSTANCE: my-sequence sequence" }
   9 } ;
  10
  11 HELP: length
  12 { $values { "seq" sequence } { "n" "a non-negative integer" } }
  13 { $contract "Outputs the length of the sequence. All sequences support this operation." } ;
  14
  15 HELP: set-length
  16 { $values { "n" "a non-negative integer" } { "seq" "a resizable sequence" } }
  17 { $contract "Resizes the sequence. Not all sequences are resizable." }
  18 { $errors "Throws a " { $link bounds-error } " if the new length is negative." }
  19 { $side-effects "seq" } ;
  20
  21 HELP: lengthen
  22 { $values { "n" "a non-negative integer" } { "seq" "a resizable sequence" } }
  23 { $contract "Ensures the sequence has a length of at least " { $snippet "n" } " elements. This word differs from " { $link set-length } " in two respects:"
  24     { $list
  25         { "This word does not shrink the sequence if " { $snippet "n" } " is less than its length." }
  26         { "The word doubles the underlying storage of " { $snippet "seq" } ", whereas " { $link set-length } " is permitted to set it to equal " { $snippet "n" } ". This ensures that repeated calls to this word with constant increments of " { $snippet "n" } " do not result in a quadratic amount of copying, so that for example " { $link push-all } " can run efficiently when used in a loop." }
  27     }
  28 } ;
  29
  30 HELP: nth
  31 { $values { "n" "a non-negative integer" } { "seq" sequence } { "elt" "the element at the " { $snippet "n" } "th index" } }
  32 { $contract "Outputs the " { $snippet "n" } "th element of the sequence. Elements are numbered from zero, so the last element has an index one less than the length of the sequence. All sequences support this operation." }
  33 { $errors "Throws a " { $link bounds-error } " if the index is negative, or greater than or equal to the length of the sequence." } ;
  34
  35 HELP: set-nth
  36 { $values { "elt" object } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
  37 { $contract "Sets the " { $snippet "n" } "th element of the sequence. Storing beyond the end of a resizable sequence such as a vector or string buffer grows the sequence." }
  38 { $errors "Throws an error if the index is negative, or if the sequence is not resizable and the index is greater than or equal to the length of the sequence."
  39 $nl
  40 "Throws an error if the sequence cannot hold elements of the given type." }
  41 { $side-effects "seq" } ;
  42
  43 HELP: nths
  44 { $values
  45      { "indices" sequence } { "seq" sequence }
  46      { "seq'" sequence } }
  47 { $description "Ouptuts a sequence of elements from the input sequence indexed by the indices." }
  48 { $examples
  49     { $example "USING: prettyprint sequences ;"
  50                "{ 0 2 } { \"a\" \"b\" \"c\" } nths ."
  51                "{ \"a\" \"c\" }"
  52     }
  53 } ;
  54
  55 HELP: immutable
  56 { $values { "seq" sequence } }
  57 { $description "Throws an " { $link immutable } " error." }
  58 { $error-description "Thrown if an attempt is made to modify an immutable sequence." } ;
  59
  60 HELP: new-sequence
  61 { $values { "len" "a non-negative integer" } { "seq" sequence } { "newseq" "a mutable sequence" } }
  62 { $contract "Outputs a mutable sequence of length " { $snippet "n" } " which can hold the elements of " { $snippet "seq" } "." } ;
  63
  64 HELP: new-resizable
  65 { $values { "len" "a non-negative integer" } { "seq" sequence } { "newseq" "a resizable mutable sequence" } }
  66 { $contract "Outputs a resizable mutable sequence with an initial capacity of " { $snippet "n" } " elements and zero length, which can hold the elements of " { $snippet "seq" } "." }
  67 { $examples
  68     { $example "USING: prettyprint sequences ;" "300 V{ } new-resizable ." "V{ }" }
  69     { $example "USING: prettyprint sequences ;" "300 SBUF\" \" new-resizable ." "SBUF\" \"" }
  70 } ;
  71
  72 HELP: like
  73 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" "a new sequence" } }
  74 { $contract "Outputs a sequence with the same elements as " { $snippet "seq" } ", but " { $emphasis "like" } " the template sequence, in the sense that it either has the same class as the template sequence, or if the template sequence is a virtual sequence, the same class as the template sequence's underlying sequence."
  75 $nl
  76 "The default implementation does nothing." }
  77 { $notes "Unlike " { $link clone-like } ", the output sequence might share storage with the input sequence." } ;
  78
  79 HELP: empty?
  80 { $values { "seq" sequence } { "?" "a boolean" } }
  81 { $description "Tests if the sequence has zero length." } ;
  82
  83 HELP: if-empty
  84 { $values { "seq" sequence } { "quot1" quotation } { "quot2" quotation } }
  85 { $description "Makes an implicit check if the sequence is empty. An empty sequence is dropped and " { $snippet "quot1" } " is called. Otherwise, if the sequence has any elements, " { $snippet "quot2" } " is called on it." }
  86 { $example
  87     "USING: kernel prettyprint sequences ;"
  88     "{ 1 2 3 } [ \"empty sequence\" ] [ sum ] if-empty ."
  89     "6"
  90 } ;
  91
  92 HELP: when-empty
  93 { $values
  94      { "seq" sequence } { "quot" "the first quotation of an " { $link if-empty } } }
  95 { $description "Makes an implicit check if the sequence is empty. An empty sequence is dropped and the " { $snippet "quot" } " is called." }
  96 { $examples "This word is equivalent to " { $link if-empty } " with an empty second quotation:"
  97     { $example
  98     "USING: sequences prettyprint ;"
  99     "{ } [ { 4 5 6 } ] [ ] if-empty ."
 100     "{ 4 5 6 }"
 101     }
 102     { $example
 103     "USING: sequences prettyprint ;"
 104     "{ } [ { 4 5 6 } ] when-empty ."
 105     "{ 4 5 6 }"
 106     }
 107 } ;
 108
 109 HELP: unless-empty
 110 { $values
 111      { "seq" sequence } { "quot" "the second quotation of an " { $link if-empty } } }
 112 { $description "Makes an implicit check if the sequence is empty. An empty sequence is dropped. Otherwise, the " { $snippet "quot" } " is called on the sequence." }
 113 { $examples "This word is equivalent to " { $link if-empty } " with an empty first quotation:"
 114     { $example
 115     "USING: sequences prettyprint ;"
 116     "{ 4 5 6 } [ ] [ sum ] if-empty ."
 117     "15"
 118     }
 119     { $example
 120     "USING: sequences prettyprint ;"
 121     "{ 4 5 6 } [ sum ] unless-empty ."
 122     "15"
 123     }
 124 } ;
 125
 126 { if-empty when-empty unless-empty } related-words
 127
 128 HELP: delete-all
 129 { $values { "seq" "a resizable sequence" } }
 130 { $description "Resizes the sequence to zero length, removing all elements. Not all sequences are resizable." }
 131 { $errors "Throws a " { $link bounds-error } " if the new length is negative, or if the sequence is not resizable." }
 132 { $side-effects "seq" } ;
 133
 134 HELP: resize
 135 { $values { "n" "a non-negative integer" } { "seq" sequence } { "newseq" "a new sequence" } }
 136 { $description "Creates a new sequence of the same type as " { $snippet "seq" } " with " { $snippet "n" } " elements, and copies the contents of " { $snippet "seq" } " into the new sequence. If " { $snippet "n" } " exceeds the length of " { $snippet "seq" } ", the remaining elements are filled with a default value; " { $link f } " for arrays and 0 for strings." }
 137 { $notes "This generic word is only implemented for strings and arrays." } ;
 138
 139 HELP: first
 140 { $values { "seq" sequence } { "first" "the first element of the sequence" } }
 141 { $description "Outputs the first element of the sequence." }
 142 { $errors "Throws an error if the sequence is empty." } ;
 143
 144 HELP: second
 145 { $values { "seq" sequence } { "second" "the second element of the sequence" } }
 146 { $description "Outputs the second element of the sequence." }
 147 { $errors "Throws an error if the sequence contains less than two elements." } ;
 148
 149 HELP: third
 150 { $values { "seq" sequence } { "third" "the third element of the sequence" } }
 151 { $description "Outputs the third element of the sequence." }
 152 { $errors "Throws an error if the sequence contains less than three elements." } ;
 153
 154 HELP: fourth
 155 { $values { "seq" sequence } { "fourth" "the fourth element of the sequence" } }
 156 { $description "Outputs the fourth element of the sequence." }
 157 { $errors "Throws an error if the sequence contains less than four elements." } ;
 158
 159 HELP: push
 160 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 161 { $description "Adds an element at the end of the sequence. The sequence length is adjusted accordingly." }
 162 { $errors "Throws an error if " { $snippet "seq" } " is not resizable, or if the type of " { $snippet "elt" } " is not permitted in " { $snippet "seq" } "." }
 163 { $side-effects "seq" } ;
 164
 165 HELP: bounds-check?
 166 { $values { "n" "an integer" } { "seq" sequence } { "?" "a boolean" } }
 167 { $description "Tests if the index is within the bounds of the sequence." } ;
 168
 169 HELP: bounds-error
 170 { $values { "n" "a positive integer" } { "seq" sequence } }
 171 { $description "Throws a " { $link bounds-error } "." }
 172 { $error-description "Thrown by " { $link nth } ", " { $link set-nth } " and " { $link set-length } " if the given index lies beyond the bounds of the sequence." } ;
 173
 174 HELP: bounds-check
 175 { $values { "n" "a positive integer" } { "seq" sequence } }
 176 { $description "Throws an error if " { $snippet "n" } " is negative or if it is greater than or equal to the length of " { $snippet "seq" } ". Otherwise the two inputs remain on the stack." } ;
 177
 178 HELP: ?nth
 179 { $values { "n" "an integer" } { "seq" sequence } { "elt/f" "an object or " { $link f } } }
 180 { $description "A forgiving version of " { $link nth } ". If the index is out of bounds, or if the sequence is " { $link f } ", simply outputs " { $link f } "." } ;
 181
 182 HELP: nth-unsafe
 183 { $values { "n" "an integer" } { "seq" sequence } { "elt" object } }
 184 { $contract "Unsafe variant of " { $link nth } " that does not perform bounds checks." } ;
 185
 186 HELP: set-nth-unsafe
 187 { $values { "elt" object } { "n" "an integer" } { "seq" sequence } }
 188 { $contract "Unsafe variant of " { $link set-nth } " that does not perform bounds checks." } ;
 189
 190 HELP: exchange-unsafe
 191 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 192 { $description "Unsafe variant of " { $link exchange } " that does not perform bounds checks." } ;
 193
 194 HELP: first2-unsafe
 195 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } }
 196 { $contract "Unsafe variant of " { $link first2 } " that does not perform bounds checks." } ;
 197
 198 HELP: first3-unsafe
 199 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } }
 200 { $contract "Unsafe variant of " { $link first3 } " that does not perform bounds checks." } ;
 201
 202 HELP: first4-unsafe
 203 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } { "fourth" "the fourth element" } }
 204 { $contract "Unsafe variant of " { $link first4 } " that does not perform bounds checks." } ;
 205
 206 HELP: 2sequence
 207 { $values { "obj1" object } { "obj2" object } { "exemplar" sequence } { "seq" sequence } }
 208 { $description "Creates a two-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 209
 210 HELP: 3sequence
 211 { $values { "obj1" object } { "obj2" object } { "obj3" object } { "exemplar" sequence } { "seq" sequence } }
 212 { $description "Creates a three-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 213
 214 HELP: 4sequence
 215 { $values { "obj1" object } { "obj2" object } { "exemplar" sequence } { "obj3" object } { "obj4" object } { "seq" sequence } }
 216 { $description "Creates a four-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 217
 218 HELP: first2
 219 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } }
 220 { $description "Pushes the first two elements of a sequence." }
 221 { $errors "Throws an error if the sequence has less than two elements." } ;
 222
 223 HELP: first3
 224 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } }
 225 { $description "Pushes the first three elements of a sequence." }
 226 { $errors "Throws an error if the sequence has less than three elements." } ;
 227
 228 HELP: first4
 229 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } { "fourth" "the fourth element" } }
 230 { $description "Pushes the first four elements of a sequence." }
 231 { $errors "Throws an error if the sequence has less than four elements." } ;
 232
 233 HELP: array-capacity
 234 { $values { "array" "an array" } { "n" "a non-negative fixnum" } }
 235 { $class-description "A predicate class whose instances are valid array sizes for the current architecture. The minimum value is zero and the maximum value is " { $link max-array-capacity } "." }
 236 { $description "Low-level array length accessor." }
 237 { $warning "This word is in the " { $vocab-link "sequences.private" } " vocabulary because it is unsafe. It does not check types, so improper use can corrupt memory." } ;
 238
 239 HELP: array-nth
 240 { $values { "n" "a non-negative fixnum" } { "array" "an array" }  { "elt" object } }
 241 { $description "Low-level array element accessor." }
 242 { $warning "This word is in the " { $vocab-link "sequences.private" } " vocabulary because it is unsafe. It does not check types or array bounds, and improper use can corrupt memory." } ;
 243
 244 HELP: set-array-nth
 245 { $values { "elt" object } { "n" "a non-negative fixnum" } { "array" "an array" }  }
 246 { $description "Low-level array element mutator." }
 247 { $warning "This word is in the " { $vocab-link "sequences.private" } " vocabulary because it is unsafe. It does not check types or array bounds, and improper use can corrupt memory." } ;
 248
 249 HELP: collect
 250 { $values { "n" "a non-negative integer" } { "quot" "a quotation with stack effect " { $snippet "( n -- value )" } } { "into" "a sequence of length at least " { $snippet "n" } } }
 251 { $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." } ;
 252
 253 HELP: each
 254 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- )" } } }
 255 { $description "Applies the quotation to each element of the sequence in order." } ;
 256
 257 HELP: reduce
 258 { $values { "seq" sequence } { "identity" object } { "quot" "a quotation with stack effect " { $snippet "( prev elt -- next )" } } { "result" "the final result" } }
 259 { $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." }
 260 { $examples
 261     { $example "USING: math prettyprint sequences ;" "{ 1 5 3 } 0 [ + ] reduce ." "9" }
 262 } ;
 263
 264 HELP: reduce-index
 265 { $values
 266      { "seq" sequence } { "identity" object } { "quot" quotation } }
 267 { $description "Combines successive elements of the sequence and their indices binary operations, and outputs the final result. On the first iteration, the three inputs to the quotation are " { $snippet "identity" } ", the first element of the sequence, and its index, 0. On successive iterations, the first input is the result of the previous iteration, the second input is the corresponding element of the sequence, and the third is its index." }
 268 { $examples { $example "USING: sequences prettyprint math ;"
 269     "{ 10 50 90 } 0 [ + + ] reduce-index ."
 270     "153"
 271 } } ;
 272
 273 HELP: accumulate
 274 { $values { "identity" object } { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( prev elt -- next )" } } { "final" "the final result" } { "newseq" "a new sequence" } }
 275 { $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."
 276 $nl
 277 "When given the empty sequence, outputs an empty sequence together with the " { $snippet "identity" } "." }
 278 { $examples
 279     { $example "USING: math prettyprint sequences ;" "{ 2 2 2 2 2 } 0 [ + ] accumulate . ." "{ 0 2 4 6 8 }\n10" }
 280 } ;
 281
 282 HELP: map
 283 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } { "newseq" "a new sequence" } }
 284 { $description "Applies the quotation to each element of the sequence in order. The new elements are collected into a sequence of the same class as the input sequence." } ;
 285
 286 HELP: map-as
 287 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } { "newseq" "a new sequence" } { "exemplar" sequence } }
 288 { $description "Applies the quotation to each element of the sequence in order. The new elements are collected into a sequence of the same class as " { $snippet "exemplar" } "." }
 289 { $examples
 290     "The following example converts a string into an array of one-element strings:"
 291     { $example "USING: prettyprint strings sequences ;" "\"Hello\" [ 1string ] { } map-as ." "{ \"H\" \"e\" \"l\" \"l\" \"o\" }" }
 292     "Note that " { $link map } " could not be used here, because it would create another string to hold results, and one-element strings cannot themselves be elements of strings."
 293 } ;
 294
 295 HELP: each-index
 296 { $values
 297      { "seq" sequence } { "quot" quotation } }
 298 { $description "Calls the quotation with the element of the sequence and its index on the stack, with the index on the top of the stack." }
 299 { $examples { $example "USING: sequences prettyprint math ;"
 300 "{ 10 20 30 } [ + . ] each-index"
 301 "10\n21\n32"
 302 } } ;
 303
 304 HELP: map-index
 305 { $values
 306      { "seq" sequence } { "quot" quotation } }
 307 { $description "Calls the quotation with the element of the sequence and its index on the stack, with the index on the top of the stack. Collects the outputs of the quotation and outputs them in a sequence of the same type as the input sequence." }
 308 { $examples { $example "USING: sequences prettyprint math ;"
 309 "{ 10 20 30 } [ + ] map-index ."
 310 "{ 10 21 32 }"
 311 } } ;
 312
 313 HELP: change-nth
 314 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- newelt )" } } }
 315 { $description "Applies the quotation to the " { $snippet "i" } "th element of the sequence, storing the result back into the sequence." }
 316 { $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" } "." }
 317 { $side-effects "seq" } ;
 318
 319 HELP: change-each
 320 { $values { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } }
 321 { $description "Applies the quotation to each element yielding a new element, storing the new elements back in the original sequence." }
 322 { $errors "Throws an error if the sequence is immutable, or the sequence cannot hold elements of the type output by " { $snippet "quot" } "." }
 323 { $side-effects "seq" } ;
 324
 325 HELP: min-length
 326 { $values { "seq1" sequence } { "seq2" sequence } { "n" "a non-negative integer" } }
 327 { $description "Outputs the minimum of the lengths of the two sequences." } ;
 328
 329 HELP: max-length
 330 { $values { "seq1" sequence } { "seq2" sequence } { "n" "a non-negative integer" } }
 331 { $description "Outputs the maximum of the lengths of the two sequences." } ;
 332
 333 HELP: 2each
 334 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- )" } } }
 335 { $description "Applies the quotation to pairs of elements from " { $snippet "seq1" } " and " { $snippet "seq2" } "." } ;
 336
 337 HELP: 2reduce
 338 { $values { "seq1" sequence }
 339           { "seq2" sequence }
 340           { "identity" object }
 341           { "quot" "a quotation with stack effect "
 342                    { $snippet "( prev elt1 elt2 -- next )" } }
 343           { "result" "the final result" } }
 344 { $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" } "." } ;
 345
 346 HELP: 2map
 347 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- new )" } } { "newseq" "a new sequence" } }
 348 { $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" } "." } ;
 349
 350 HELP: 2map-as
 351 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- new )" } } { "exemplar" sequence } { "newseq" "a new sequence" } }
 352 { $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 "exemplar" } "." } ;
 353
 354 HELP: 2all?
 355 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- ? )" } } { "?" "a boolean" } }
 356 { $description "Tests the predicate pairwise against elements of " { $snippet "seq1" } " and " { $snippet "seq2" } "." } ;
 357
 358 HELP: find
 359 { $values { "seq" sequence }
 360           { "quot" "a quotation with stack effect "
 361                    { $snippet "( elt -- ? )" } }
 362           { "i" "the index of the first match, or f" }
 363           { "elt" "the first matching element, or " { $link f } } }
 364 { $description "A simpler variant of " { $link find-from } " where the starting index is 0." } ;
 365
 366 HELP: find-from
 367 { $values { "n" "a starting index" }
 368           { "seq" sequence }
 369           { "quot" "a quotation with stack effect "
 370                    { $snippet "( elt -- ? )" } }
 371           { "i" "the index of the first match, or f" }
 372           { "elt" "the first matching element, or " { $link f } } }
 373 { $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 f and " { $link f } " as the element." } ;
 374
 375 HELP: find-last
 376 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "i" "the index of the first match, or f" } { "elt" "the first matching element, or " { $link f } } }
 377 { $description "A simpler variant of " { $link find-last-from } " where the starting index is one less than the length of the sequence." } ;
 378
 379 HELP: find-last-from
 380 { $values { "n" "a starting index" } { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "i" "the index of the first match, or f" } { "elt" "the first matching element, or " { $link f } } }
 381 { $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 f and " { $link f } " as the element." } ;
 382
 383 HELP: contains?
 384 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "?" "a boolean" } }
 385 { $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 } "." } ;
 386
 387 HELP: all?
 388 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "?" "a boolean" } }
 389 { $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 } "." } ;
 390
 391 HELP: push-if
 392 { $values { "elt" object } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "accum" "a resizable mutable sequence" } }
 393 { $description "Adds the element at the end of the sequence if the quotation yields a true value." }
 394 { $notes "This word is a factor of " { $link filter } "." } ;
 395
 396 HELP: filter
 397 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "subseq" "a new sequence" } }
 398 { $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." } ;
 399
 400 HELP: monotonic?
 401 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt elt -- ? )" } } { "?" "a boolean" } }
 402 { $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." }
 403 { $examples
 404     "Testing if a sequence is non-decreasing:"
 405     { $example "USING: math prettyprint sequences ;" "{ 1 1 2 } [ <= ] monotonic? ." "t" }
 406     "Testing if a sequence is decreasing:"
 407     { $example "USING: math prettyprint sequences ;" "{ 9 8 6 7 } [ < ] monotonic? ." "f" }
 408 } ;
 409
 410 { monotonic? all-eq? all-equal? } related-words
 411
 412 HELP: interleave
 413 { $values { "seq" sequence } { "between" "a quotation" } { "quot" "a quotation with stack effect " { $snippet "( elt -- )" } } }
 414 { $description "Applies " { $snippet "quot" } " to each element in turn, also invoking " { $snippet "between" } " in-between each pair of elements." }
 415 { $example "USING: io sequences ;" "{ \"a\" \"b\" \"c\" } [ \"X\" write ] [ write ] interleave" "aXbXc" } ;
 416
 417 HELP: cache-nth
 418 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( i -- elt )" } } { "elt" object } }
 419 { $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." }
 420 { $side-effects "seq" } ;
 421
 422 HELP: index
 423 { $values { "obj" object } { "seq" sequence } { "n" "an index" } }
 424 { $description "Outputs the index of the first element in the sequence equal to " { $snippet "obj" } ". If no element is found, outputs " { $link f } "." } ;
 425
 426 HELP: index-from
 427 { $values { "obj" object } { "i" "a start index" } { "seq" sequence } { "n" "an index" } }
 428 { $description "Outputs the index of the first element in the sequence equal to " { $snippet "obj" } ", starting the search from the " { $snippet "i" } "th element. If no element is found, outputs " { $link f } "." } ;
 429
 430 HELP: last-index
 431 { $values { "obj" object } { "seq" sequence } { "n" "an index" } }
 432 { $description "Outputs the index of the last element in the sequence equal to " { $snippet "obj" } "; the sequence is traversed back to front. If no element is found, outputs " { $link f } "." } ;
 433
 434 HELP: last-index-from
 435 { $values { "obj" object } { "i" "a start index" } { "seq" sequence } { "n" "an index" } }
 436 { $description "Outputs the index of the last element in the sequence equal to " { $snippet "obj" } ", traversing the sequence backwards starting from the " { $snippet "i" } "th element and finishing at the first. If no element is found, outputs " { $link f } "." } ;
 437
 438 HELP: member?
 439 { $values { "obj" object } { "seq" sequence } { "?" "a boolean" } }
 440 { $description "Tests if the sequence contains an element equal to the object." } ;
 441
 442 HELP: memq?
 443 { $values { "obj" object } { "seq" sequence } { "?" "a boolean" } }
 444 { $description "Tests if the sequence contains the object." }
 445 { $examples
 446     "This word uses identity comparison, so the following will most likely print " { $link f } ":"
 447     { $example "USING: prettyprint sequences ;" "\"hello\" { \"hello\" } memq? ." "f" }
 448 } ;
 449
 450 HELP: remove
 451 { $values { "obj" object } { "seq" sequence } { "newseq" "a new sequence" } }
 452 { $description "Outputs a new sequence containing all elements of the input sequence except those equal to the given element." } ;
 453
 454 HELP: remove-nth
 455 { $values
 456      { "n" integer } { "seq" sequence }
 457      { "seq'" sequence } }
 458 { $description "Creates a new sequence without the element at index " { $snippet "n" } "." }
 459 { $examples "Notice that the original sequence is left intact:" { $example "USING: sequences prettyprint kernel ;"
 460     "{ 1 2 3 } 1 over remove-nth . ."
 461     "{ 1 3 }\n{ 1 2 3 }"
 462 } } ;
 463
 464 HELP: move
 465 { $values { "from" "an index in " { $snippet "seq" } } { "to" "an index in " { $snippet "seq" } } { "seq" "a mutable sequence" } }
 466 { $description "Sets the element with index " { $snippet "m" } " to the element with index " { $snippet "n" } "." }
 467 { $side-effects "seq" } ;
 468
 469 HELP: delete
 470 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 471 { $description "Removes all elements equal to " { $snippet "elt" } " from " { $snippet "seq" } "." }
 472 { $side-effects "seq" } ;
 473
 474 HELP: delete-nth
 475 { $values { "n" "a non-negative integer" } { "seq" "a resizable mutable sequence" } }
 476 { $description "Removes the " { $snippet "n" } "th element from the sequence, shifting all other elements down and reducing its length by one." }
 477 { $side-effects "seq" } ;
 478
 479 HELP: delete-slice
 480 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" "a resizable mutable sequence" } }
 481 { $description "Removes a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } "." }
 482 { $side-effects "seq" } ;
 483
 484 HELP: replace-slice
 485 { $values { "new" sequence } { "seq" "a mutable sequence" } { "from" "a non-negative integer" } { "to" "a non-negative integer" } }
 486 { $description "Replaces a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } " with a new sequence." }
 487 { $notes "If the " { $snippet "to - from" } " is equal to the length of " { $snippet "new" } ", the sequence remains the same size, and does not have to support resizing. However, if " { $snippet "to - from" } " is not equal to the length of " { $snippet "new" } ", the " { $link set-length } " word is called on " { $snippet "seq" } ", so fixed-size sequences should not be passed in this case." }
 488 { $errors "Throws an error if " { $snippet "new" } " contains elements whose types are not permissible in " { $snippet "seq" } "." }
 489 { $side-effects "seq" } ;
 490
 491 { push prefix suffix } related-words
 492
 493 HELP: suffix
 494 { $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
 495 { $description "Outputs a new sequence obtained by adding " { $snippet "elt" } " at the end of " { $snippet "seq" } "." }
 496 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 497 { $examples
 498     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } 4 suffix ." "{ 1 2 3 4 }" }
 499 } ;
 500
 501 HELP: prefix
 502 { $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
 503 { $description "Outputs a new sequence obtained by adding " { $snippet "elt" } " at the beginning of " { $snippet "seq" } "." }
 504 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 505 { $examples
 506 { $example "USING: prettyprint sequences ;" "{ 1 2 3 } 0 prefix ." "{ 0 1 2 3 }" }
 507 } ;
 508
 509 HELP: sum-lengths
 510 { $values { "seq" "a sequence of sequences" } { "n" integer } }
 511 { $description "Outputs the sum of the lengths of all sequences in " { $snippet "seq" } "." } ;
 512
 513 HELP: concat
 514 { $values { "seq" sequence } { "newseq" sequence } }
 515 { $description "Concatenates a sequence of sequences together into one sequence. If " { $snippet "seq" } " is empty, outputs " { $snippet "{ }" } ", otherwise the resulting sequence is of the same class as the first element of " { $snippet "seq" } "." }
 516 { $errors "Throws an error if one of the sequences in " { $snippet "seq" } " contains elements not permitted in sequences of the same class as the first element of " { $snippet "seq" } "." } ;
 517
 518 HELP: join
 519 { $values { "seq" sequence } { "glue" sequence } { "newseq" sequence } }
 520 { $description "Concatenates a sequence of sequences together into one sequence, placing a copy of " { $snippet "glue" } " between each pair of sequences. The resulting sequence is of the same class as " { $snippet "glue" } "." }
 521 { $errors "Throws an error if one of the sequences in " { $snippet "seq" } " contains elements not permitted in sequences of the same class as " { $snippet "glue" } "." } ;
 522
 523 { join concat } related-words
 524
 525 HELP: peek
 526 { $values { "seq" sequence } { "elt" object } }
 527 { $description "Outputs the last element of a sequence." }
 528 { $errors "Throws an error if the sequence is empty." } ;
 529
 530 { peek pop pop* } related-words
 531
 532 HELP: pop*
 533 { $values { "seq" "a resizable mutable sequence" } }
 534 { $description "Removes the last element and shortens the sequence." }
 535 { $side-effects "seq" }
 536 { $errors "Throws an error if the sequence is empty." } ;
 537
 538 HELP: pop
 539 { $values { "seq" "a resizable mutable sequence" } { "elt" object } }
 540 { $description "Outputs the last element after removing it and shortening the sequence." }
 541 { $side-effects "seq" }
 542 { $errors "Throws an error if the sequence is empty." } ;
 543
 544 HELP: all-equal?
 545 { $values { "seq" sequence } { "?" "a boolean" } }
 546 { $description "Tests if all elements in the sequence are equal. Yields true with an empty sequence." } ;
 547
 548 HELP: all-eq?
 549 { $values { "seq" sequence } { "?" "a boolean" } }
 550 { $description "Tests if all elements in the sequence are the same identical object. Yields true with an empty sequence." } ;
 551
 552 HELP: mismatch
 553 { $values { "seq1" sequence } { "seq2" sequence } { "i" "an index" } }
 554 { $description "Compares pairs of elements up to the minimum of the sequences' lengths, outputting the first index where the two sequences have non-equal elements, or " { $link f } " if all tested elements were equal." } ;
 555
 556 HELP: flip
 557 { $values { "matrix" "a sequence of equal-length sequences" } { "newmatrix" "a sequence of equal-length sequences" } }
 558 { $description "Transposes the matrix; that is, rows become columns and columns become rows." }
 559 { $examples { $example "USING: prettyprint sequences ;" "{ { 1 2 3 } { 4 5 6 } } flip ." "{ { 1 4 } { 2 5 } { 3 6 } }" } } ;
 560
 561 HELP: exchange
 562 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 563 { $description "Exchanges the " { $snippet "m" } "th and " { $snippet "n" } "th elements of " { $snippet "seq" } "." } ;
 564
 565 HELP: reverse-here
 566 { $values { "seq" "a mutable sequence" } }
 567 { $description "Reverses a sequence in-place." }
 568 { $side-effects "seq" } ;
 569
 570 HELP: padding
 571 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "quot" "a quotation with stack effect " { $snippet "( seq1 seq2 -- newseq )" } } { "newseq" "a new sequence" } }
 572 { $description "Outputs a new string sequence of " { $snippet "elt" } " repeated, that when appended to " { $snippet "seq" } ", yields a sequence of length " { $snippet "n" } ". If the length of " { $snippet "seq" } " is greater than " { $snippet "n" } ", this word outputs an empty sequence." } ;
 573
 574 HELP: pad-left
 575 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "padded" "a new sequence" } }
 576 { $description "Outputs a new sequence consisting of " { $snippet "seq" } " padded on the left with enough repetitions of " { $snippet "elt" } " to have the result be of length " { $snippet "n" } "." }
 577 { $examples { $example "USING: io sequences ;" "{ \"ab\" \"quux\" } [ 5 CHAR: - pad-left print ] each" "---ab\n-quux" } } ;
 578
 579 HELP: pad-right
 580 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "padded" "a new sequence" } }
 581 { $description "Outputs a new sequence consisting of " { $snippet "seq" } " padded on the right with enough repetitions of " { $snippet "elt" } " to have the result be of length " { $snippet "n" } "." }
 582 { $examples { $example "USING: io sequences ;" "{ \"ab\" \"quux\" } [ 5 CHAR: - pad-right print ] each" "ab---\nquux-" } } ;
 583
 584 HELP: sequence=
 585 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 586 { $description "Tests if the two sequences have the same length and elements. This is weaker than " { $link = } ", since it does not ensure that the sequences are instances of the same class." } ;
 587
 588 HELP: reversed
 589 { $class-description "A virtual sequence which presents a reversed view of an underlying sequence. New instances can be created by calling " { $link <reversed> } "." } ;
 590
 591 HELP: reverse
 592 { $values { "seq" sequence } { "newseq" "a new sequence" } }
 593 { $description "Outputs a new sequence having the same elements as " { $snippet "seq" } " but in reverse order." } ;
 594
 595 { reverse <reversed> } related-words
 596
 597 HELP: <reversed> ( seq -- reversed )
 598 { $values { "seq" sequence } { "reversed" "a new sequence" } }
 599 { $description "Creates an instance of the " { $link reversed } " class." }
 600 { $see-also "virtual-sequences" } ;
 601
 602 HELP: slice-error
 603 { $values { "str" "a reason" } }
 604 { $description "Throws a " { $link slice-error } "." }
 605 { $error-description "Thrown by " { $link <slice> } " if one of the following invalid conditions holds:"
 606     { $list
 607         "The start index is negative"
 608         "The end index is greater than the length of the sequence"
 609         "The start index is greater than the end index"
 610     }
 611 } ;
 612
 613 HELP: slice
 614 { $class-description "A virtual sequence which presents a subrange of the elements of an underlying sequence. New instances can be created by calling " { $link <slice> } "."
 615 $nl
 616 "Slices are mutable if the underlying sequence is mutable, and mutating a slice changes the underlying sequence. However, slices cannot be resized after creation." } ;
 617
 618 HELP: check-slice
 619 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } }
 620 { $description "Ensures that " { $snippet "m" } " is less than or equal to " { $snippet "m" } ", and that both indices are within bounds for " { $snippet "seq" } "." }
 621 { $errors "Throws a " { $link slice-error } " if the preconditions are not met." } ;
 622
 623 HELP: collapse-slice
 624 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "slice" slice } { "m'" "a non-negative integer" } { "n'" "a non-negative integer" } { "seq" sequence } }
 625 { $description "Prepares to take the slice of a slice by adjusting the start and end indices accordingly, and replacing the slice with its underlying sequence." }
 626 ;
 627
 628 HELP: <flat-slice>
 629 { $values { "seq" sequence } { "slice" slice } }
 630 { $description "Outputs a slice with the same elements as " { $snippet "seq" } ", and " { $snippet "from" } " equal to 0 and " { $snippet "to" } " equal to the length of " { $snippet "seq" } "." }
 631 { $notes "Some words create slices then proceed to read the " { $snippet "to" } " and " { $snippet "from" } " slots of the slice. To behave predictably when they are themselves given a slice as input, they apply this word first to get a canonical slice." } ;
 632
 633 HELP: <slice>
 634 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "slice" slice } }
 635 { $description "Outputs a new virtual sequence sharing storage with the subrange of elements in " { $snippet "seq" } " with indices starting from and including " { $snippet "m" } ", and up to but not including " { $snippet "n" } "." }
 636 { $errors "Throws an error if " { $snippet "m" } " or " { $snippet "n" } " is out of bounds." }
 637 { $notes "Taking the slice of a slice outputs a slice of the underlying sequence of the original slice. Keep this in mind when writing code which depends on the values of " { $snippet "from" } " and " { $snippet "to" } " being equal to the inputs to this word. The " { $link <flat-slice> } " word might be helpful in such situations." } ;
 638
 639 { <slice> subseq } related-words
 640
 641 HELP: repetition
 642 { $class-description "A virtual sequence consisting of " { $snippet "elt" } " repeated " { $snippet "len" } " times. Repetitions are created by calling " { $link <repetition> } "." } ;
 643
 644 HELP: <repetition> ( len elt -- repetition )
 645 { $values { "len" "a non-negative integer" } { "elt" object } { "repetition" repetition } }
 646 { $description "Creates a new " { $link repetition } "." }
 647 { $examples
 648     { $example "USING: arrays prettyprint sequences ;" "10 \"X\" <repetition> >array ." "{ \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" }" }
 649     { $example "USING: prettyprint sequences ;" "10 \"X\" <repetition> concat ." "\"XXXXXXXXXX\"" }
 650 } ;
 651 HELP: copy
 652 { $values { "src" sequence } { "i" "an index in " { $snippet "dest" } } { "dst" "a mutable sequence" } }
 653 { $description "Copies all elements of " { $snippet "src" } " to " { $snippet "dest" } ", with destination indices starting from " { $snippet "i" } ". Grows " { $snippet "to" } " first if necessary." }
 654 { $side-effects "dest" }
 655 { $errors "An error is thrown if " { $snippet "to" } " is not resizable, and not large enough to hold the copied elements." } ;
 656
 657 HELP: push-all
 658 { $values { "src" sequence } { "dest" "a resizable mutable sequence" } }
 659 { $description "Appends " { $snippet "src" } " to the end of " { $snippet "dest" } "." }
 660 { $side-effects "dest" }
 661 { $errors "Throws an error if " { $snippet "src" } " contains elements not permitted in " { $snippet "dest" } "." } ;
 662
 663 HELP: append
 664 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
 665 { $description "Outputs a new sequence of the same type as " { $snippet "seq1" } " consisting of the elements of " { $snippet "seq1" } " followed by " { $snippet "seq2" } "." }
 666 { $errors "Throws an error if " { $snippet "seq2" } " contains elements not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 667 { $examples
 668     { $example "USING: prettyprint sequences ;"
 669         "{ 1 2 } B{ 3 4 } append ."
 670         "{ 1 2 3 4 }"
 671     }
 672     { $example "USING: prettyprint sequences strings ;"
 673         "\"go\" \"ing\" append ."
 674         "\"going\""
 675     }
 676 } ;
 677
 678 HELP: prepend
 679 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
 680 { $description "Outputs a new sequence of the same type as " { $snippet "seq2" } " consisting of the elements of " { $snippet "seq2" } " followed by " { $snippet "seq1" } "." }
 681 { $errors "Throws an error if " { $snippet "seq1" } " contains elements not permitted in sequences of the same class as " { $snippet "seq2" } "." }
 682 { $examples
 683     { $example "USING: prettyprint sequences ;"
 684         "{ 1 2 } B{ 3 4 } prepend ."
 685         "B{ 3 4 1 2 }"
 686     }
 687     { $example "USING: prettyprint sequences strings ;"
 688         "\"go\" \"car\" prepend ."
 689         "\"cargo\""
 690     }
 691 } ;
 692
 693 HELP: 3append
 694 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
 695 { $description "Outputs a new sequence consisting of the elements of " { $snippet "seq1" } ", " { $snippet "seq2" } " and " { $snippet "seq3" } " in turn." }
 696 { $errors "Throws an error if " { $snippet "seq2" } " or " { $snippet "seq3" } " contain elements not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 697 { $examples
 698     { $example "USING: prettyprint sequences ;"
 699         "\"a\" \"b\" \"c\" 3append ."
 700         "\"abc\""
 701     }
 702 } ;
 703
 704 HELP: subseq
 705 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "subseq" "a new sequence" } }
 706 { $description "Outputs a new sequence consisting of all elements starting from and including " { $snippet "from" } ", and up to but not including " { $snippet "to" } "." }
 707 { $errors "Throws an error if " { $snippet "from" } " or " { $snippet "to" } " is out of bounds." } ;
 708
 709 HELP: clone-like
 710 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" "a new sequence" } }
 711 { $description "Outputs a newly-allocated sequence with the same elements as " { $snippet "seq" } " but of the same type as " { $snippet "exemplar" } "." }
 712 { $notes "Unlike " { $link like } ", this word always creates a new sequence which never shares storage with the original." } ;
 713
 714 HELP: head-slice
 715 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 716 { $description "Outputs a virtual sequence sharing storage with the first " { $snippet "n" } " elements of the input sequence." }
 717 { $errors "Throws an error if the index is out of bounds." } ;
 718
 719 HELP: tail-slice
 720 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 721 { $description "Outputs a virtual sequence sharing storage with all elements from the " { $snippet "n" } "th index until the end of the input sequence." }
 722 { $errors "Throws an error if the index is out of bounds." } ;
 723
 724 HELP: but-last-slice
 725 { $values { "seq" sequence } { "slice" "a slice" } }
 726 { $description "Outputs a virtual sequence sharing storage with all but the last element of the input sequence." }
 727 { $errors "Throws an error on an empty sequence." } ;
 728
 729 HELP: rest-slice
 730 { $values { "seq" sequence } { "slice" "a slice" } }
 731 { $description "Outputs a virtual sequence sharing storage with all elements from the 1st index until the end of the input sequence." }
 732 { $notes "Equivalent to " { $snippet "1 tail" } }
 733 { $errors "Throws an error on an empty sequence." } ;
 734
 735 HELP: head-slice*
 736 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 737 { $description "Outputs a virtual sequence sharing storage with all elements of " { $snippet "seq" } " until the " { $snippet "n" } "th element from the end. In other words, it outputs a sequence of the first " { $snippet "l-n" } " elements of the input sequence, where " { $snippet "l" } " is its length." }
 738 { $errors "Throws an error if the index is out of bounds." } ;
 739
 740 HELP: tail-slice*
 741 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 742 { $description "Outputs a virtual sequence sharing storage with the last " { $snippet "n" } " elements of the input sequence." }
 743 { $errors "Throws an error if the index is out of bounds." } ;
 744
 745 HELP: head
 746 { $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
 747 { $description "Outputs a new sequence consisting of the first " { $snippet "n" } " elements of the input sequence." }
 748 { $errors "Throws an error if the index is out of bounds." } ;
 749
 750 HELP: tail
 751 { $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
 752 { $description "Outputs a new sequence consisting of the input sequence with the first n items removed." }
 753 { $errors "Throws an error if the index is out of bounds." } ;
 754
 755 HELP: but-last
 756 { $values { "seq" sequence } { "headseq" "a new sequence" } }
 757 { $description "Outputs a new sequence consisting of the input sequence with the last item removed." }
 758 { $errors "Throws an error on an empty sequence." } ;
 759
 760 HELP: rest
 761 { $values { "seq" sequence } { "tailseq" "a new sequence" } }
 762 { $description "Outputs a new sequence consisting of the input sequence with the first item removed." }
 763 { $errors "Throws an error on an empty sequence." } ;
 764
 765 HELP: head*
 766 { $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
 767 { $description "Outputs a new sequence consisting of all elements of " { $snippet "seq" } " until the " { $snippet "n" } "th element from the end. In other words, it outputs a sequence of the first " { $snippet "l-n" } " elements of the input sequence, where " { $snippet "l" } " is its length." }
 768 { $errors "Throws an error if the index is out of bounds." } ;
 769
 770 HELP: tail*
 771 { $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
 772 { $description "Outputs a new sequence consisting of the last " { $snippet "n" } " elements of the input sequence." }
 773 { $errors "Throws an error if the index is out of bounds." } ;
 774
 775 HELP: shorter?
 776 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 777 { $description "Tets if the length of " { $snippet "seq1" } " is smaller than the length of " { $snippet "seq2" } "." } ;
 778
 779 HELP: head?
 780 { $values { "seq" sequence } { "begin" sequence } { "?" "a boolean" } }
 781 { $description "Tests if " { $snippet "seq" } " starts with " { $snippet "begin" } ". If " { $snippet "begin" } " is longer than " { $snippet "seq" } ", this word outputs " { $link f } "." } ;
 782
 783 HELP: tail?
 784 { $values { "seq" sequence } { "end" sequence } { "?" "a boolean" } }
 785 { $description "Tests if " { $snippet "seq" } " ends with " { $snippet "end" } ". If " { $snippet "end" } " is longer than " { $snippet "seq" } ", this word outputs " { $link f } "." } ;
 786
 787 { delete-nth remove delete } related-words
 788
 789 HELP: cut-slice
 790 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before-slice" sequence } { "after-slice" "a slice" } }
 791 { $description "Outputs a pair of sequences, where " { $snippet "before" } " consists of the first " { $snippet "n" } " elements of " { $snippet "seq" } " and has the same type, while " { $snippet "after" } " is a slice of the remaining elements." }
 792 { $notes "Unlike " { $link cut } ", the run time of this word is proportional to the length of " { $snippet "before" } ", not " { $snippet "after" } ", so it is suitable for use in an iterative algorithm which cuts successive pieces off a sequence." } ;
 793
 794 HELP: cut
 795 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
 796 { $description "Outputs a pair of sequences, where " { $snippet "before" } " consists of the first " { $snippet "n" } " elements of " { $snippet "seq" } ", while " { $snippet "after" } " holds the remaining elements. Both output sequences have the same type as " { $snippet "seq" } "." }
 797 { $notes "Since this word copies the entire tail of the sequence, it should not be used in a loop. If this is important, consider using " { $link cut-slice } " instead, since it returns a slice for the tail instead of copying." } ;
 798
 799 HELP: cut*
 800 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
 801 { $description "Outputs a pair of sequences, where " { $snippet "after" } " consists of the last " { $snippet "n" } " elements of " { $snippet "seq" } ", while " { $snippet "before" } " holds the remaining elements. Both output sequences have the same type as " { $snippet "seq" } "." } ;
 802
 803 HELP: start*
 804 { $values { "subseq" sequence } { "seq" sequence } { "n" "a start index" } { "i" "a start index" } }
 805 { $description "Outputs the start index of the first contiguous subsequence equal to " { $snippet "subseq" } ", starting the search from the " { $snippet "n" } "th element. If no matching subsequence is found, outputs " { $link f } "." } ;
 806
 807 HELP: start
 808 { $values { "subseq" sequence } { "seq" sequence } { "i" "a start index" } }
 809 { $description "Outputs the start index of the first contiguous subsequence equal to " { $snippet "subseq" } ", or " { $link f } " if no matching subsequence is found." } ;
 810
 811 HELP: subseq?
 812 { $values { "subseq" sequence } { "seq" sequence } { "?" "a boolean" } }
 813 { $description "Tests if " { $snippet "seq" } " contains the elements of " { $snippet "subseq" } " as a contiguous subsequence." } ;
 814
 815 HELP: drop-prefix
 816 { $values { "seq1" sequence } { "seq2" sequence } { "slice1" "a slice" } { "slice2" "a slice" } }
 817 { $description "Outputs a pair of virtual sequences with the common prefix of " { $snippet "seq1" } " and " { $snippet "seq2" } " removed." } ;
 818
 819 HELP: unclip
 820 { $values { "seq" sequence } { "rest" sequence } { "first" object } }
 821 { $description "Outputs a tail sequence and the first element of " { $snippet "seq" } "; the tail sequence consists of all elements of " { $snippet "seq" } " but the first." }
 822 { $examples
 823     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } unclip suffix ." "{ 2 3 1 }" }
 824 } ;
 825
 826 HELP: unclip-slice
 827 { $values { "seq" sequence } { "rest-slice" slice } { "first" object } }
 828 { $description "Outputs a tail sequence and the first element of " { $snippet "seq" } "; the tail sequence consists of all elements of " { $snippet "seq" } " but the first. Unlike " { $link unclip } ", this word does not make a copy of the input sequence, and runs in constant time." } ;
 829
 830 HELP: unclip-last
 831 { $values { "seq" sequence } { "butlast" sequence } { "last" object } }
 832 { $description "Outputs a head sequence and the last element of " { $snippet "seq" } "; the head sequence consists of all elements of " { $snippet "seq" } " but the last." }
 833 { $examples
 834     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } unclip-last prefix ." "{ 3 1 2 }" }
 835 } ;
 836
 837 HELP: unclip-last-slice
 838 { $values { "seq" sequence } { "butlast-slice" slice } { "last" object } }
 839 { $description "Outputs a head sequence and the last element of " { $snippet "seq" } "; the head sequence consists of all elements of " { $snippet "seq" } " but the last Unlike " { $link unclip-last } ", this word does not make a copy of the input sequence, and runs in constant time." } ;
 840
 841 HELP: sum
 842 { $values { "seq" "a sequence of numbers" } { "n" "a number" } }
 843 { $description "Outputs the sum of all elements of " { $snippet "seq" } ". Outputs zero given an empty sequence." } ;
 844
 845 HELP: product
 846 { $values { "seq" "a sequence of numbers" } { "n" "a number" } }
 847 { $description "Outputs the product of all elements of " { $snippet "seq" } ". Outputs one given an empty sequence." } ;
 848
 849 HELP: infimum
 850 { $values { "seq" "a sequence of real numbers" } { "n" "a number" } }
 851 { $description "Outputs the least element of " { $snippet "seq" } "." }
 852 { $errors "Throws an error if the sequence is empty." } ;
 853
 854 HELP: supremum
 855 { $values { "seq" "a sequence of real numbers" } { "n" "a number" } }
 856 { $description "Outputs the greatest element of " { $snippet "seq" } "." }
 857 { $errors "Throws an error if the sequence is empty." } ;
 858
 859 HELP: produce
 860 { $values { "pred" "a quotation with stack effect " { $snippet "( -- ? )" } } { "quot" "a quotation with stack effect " { $snippet "( -- obj )" } } { "tail" "a quotation" } { "seq" "a sequence" } }
 861 { $description "Calls " { $snippet "pred" } " repeatedly. If the predicate yields " { $link f } ", stops, otherwise, calls " { $snippet "quot" } " to yield a value. Values are accumulated and returned in a sequence at the end." }
 862 { $examples
 863     "The following example divides a number by two until we reach zero, and accumulates intermediate results:"
 864     { $example "USING: kernel math prettyprint sequences ;" "1337 [ dup 0 > ] [ 2/ dup ] [ ] produce nip ." "{ 668 334 167 83 41 20 10 5 2 1 0 }" }
 865     "The " { $snippet "tail" } " quotation is used when the predicate produces more than one output value. In this case, we have to drop this value even if the predicate fails in order for stack inference to calculate a stack effect for the " { $link produce } " call:"
 866     { $unchecked-example "USING: kernel prettyprint random sequences ;" "[ 10 random dup 1 > ] [ ] [ drop ] produce ." "{ 8 2 2 9 }" }
 867 } ;
 868
 869 HELP: sigma
 870 { $values { "seq" sequence } { "quot" quotation } { "n" number } }
 871 { $description "Like map sum, but without creating an intermediate sequence." }
 872 { $example
 873     "! Find the sum of the squares [0,99]"
 874     "USING: math math.ranges sequences prettyprint ;"
 875     "100 [1,b] [ sq ] sigma ."
 876     "338350"
 877 } ;
 878
 879 HELP: count
 880 { $values { "seq" sequence } { "quot" quotation } { "n" integer } }
 881 { $description "Efficiently returns the number of elements that the predicate quotation matches." }
 882 { $example
 883     "USING: math math.ranges sequences prettyprint ;"
 884     "100 [1,b] [ even? ] count ."
 885     "50"
 886 } ;
 887
 888 HELP: pusher
 889 { $values
 890      { "quot" "a predicate quotation" }
 891      { "quot" quotation } { "accum" vector } }
 892 { $description "Creates a new vector to accumulate the values which return true for a predicate.  Returns a new quotation which accepts an object to be tested and stored in the accumulator if the test yields true. The accumulator is left on the stack for convenience." }
 893 { $example "! Find all the even numbers:" "USING: prettyprint sequences math kernel ;"
 894            "10 [ even? ] pusher [ each ] dip ."
 895            "V{ 0 2 4 6 8 }"
 896 }
 897 { $notes "Used to implement the " { $link filter } " word." } ;
 898
 899 HELP: trim-left
 900 { $values
 901      { "seq" sequence } { "quot" quotation }
 902      { "newseq" sequence } }
 903 { $description "Removes elements starting from the left side of a sequence if they match a predicate. Once an element does not match, the test stops and the rest of the sequence is left on the stack as a new sequence." }
 904 { $example "" "USING: prettyprint math sequences ;"
 905            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-left ."
 906            "{ 1 2 3 0 0 }"
 907 } ;
 908
 909 HELP: trim-left-slice
 910 { $values
 911      { "seq" sequence } { "quot" quotation }
 912      { "slice" slice } }
 913 { $description "Removes elements starting from the left side of a sequence if they match a predicate. Once an element does not match, the test stops and the rest of the sequence is left on the stack as a slice" }
 914 { $example "" "USING: prettyprint math sequences ;"
 915            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-left-slice ."
 916            "T{ slice { from 2 } { to 7 } { seq { 0 0 1 2 3 0 0 } } }"
 917 } ;
 918
 919 HELP: trim-right
 920 { $values
 921      { "seq" sequence } { "quot" quotation }
 922      { "newseq" sequence } }
 923 { $description "Removes elements starting from the right side of a sequence if they match a predicate. Once an element does not match, the test stops and the rest of the sequence is left on the stack as a new sequence." }
 924 { $example "" "USING: prettyprint math sequences ;"
 925            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-right ."
 926            "{ 0 0 1 2 3 }"
 927 } ;
 928
 929 HELP: trim-right-slice
 930 { $values
 931      { "seq" sequence } { "quot" quotation }
 932      { "slice" slice } }
 933 { $description "Removes elements starting from the right side of a sequence if they match a predicate. Once an element does not match, the test stops and the rest of the sequence is left on the stack as a slice." }
 934 { $example "" "USING: prettyprint math sequences ;"
 935            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-right-slice ."
 936            "T{ slice { from 0 } { to 5 } { seq { 0 0 1 2 3 0 0 } } }"
 937 } ;
 938
 939 HELP: trim
 940 { $values
 941      { "seq" sequence } { "quot" quotation }
 942      { "newseq" sequence } }
 943 { $description "Removes elements starting from the left and right sides of a sequence if they match a predicate. Once an element does not match, the test stops and the rest of the sequence is left on the stack as a new sequence." }
 944 { $example "" "USING: prettyprint math sequences ;"
 945            "{ 0 0 1 2 3 0 0 } [ zero? ] trim ."
 946            "{ 1 2 3 }"
 947 } ;
 948
 949 HELP: trim-slice
 950 { $values
 951      { "seq" sequence } { "quot" quotation }
 952      { "slice" slice } }
 953 { $description "Removes elements starting from the left and right sides of a sequence if they match a predicate. Once an element does not match, the test stops and the rest of the sequence is left on the stack as a slice." }
 954 { $example "" "USING: prettyprint math sequences ;"
 955            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-slice ."
 956            "T{ slice { from 2 } { to 5 } { seq { 0 0 1 2 3 0 0 } } }"
 957 } ;
 958
 959 { trim trim-slice trim-left trim-left-slice trim-right trim-right-slice } related-words
 960
 961 HELP: sift
 962 { $values
 963      { "seq" sequence }
 964      { "newseq" sequence } }
 965  { $description "Outputs a new sequence with all instance of " { $link f  } " removed." }
 966  { $examples
 967     { $example "USING: prettyprint sequences ;"
 968         "{ \"a\" 3 { } f } sift ."
 969         "{ \"a\" 3 { } }"
 970     }
 971 } ;
 972
 973 HELP: harvest
 974 { $values
 975      { "seq" sequence }
 976      { "newseq" sequence } }
 977 { $description "Outputs a new sequence with all empty sequences removed." }
 978 { $examples
 979     { $example "USING: prettyprint sequences ;"
 980                "{ { } { 2 3 } { 5 } { } } harvest ."
 981                "{ { 2 3 } { 5 } }"
 982     }
 983 } ;
 984
 985 { filter sift harvest } related-words
 986
 987 HELP: set-first
 988 { $values
 989      { "first" object } { "seq" sequence } }
 990 { $description "Sets the first element of a sequence." }
 991 { $examples
 992     { $example "USING: prettyprint kernel sequences ;"
 993         "{ 1 2 3 4  } 5 over set-first ."
 994         "{ 5 2 3 4 }"
 995     }
 996 } ;
 997
 998 HELP: set-second
 999 { $values
1000      { "second" object } { "seq" sequence } }
1001 { $description "Sets the second element of a sequence." }
1002 { $examples
1003     { $example "USING: prettyprint kernel sequences ;"
1004         "{ 1 2 3 4  } 5 over set-second ."
1005         "{ 1 5 3 4 }"
1006     }
1007 } ;
1008
1009 HELP: set-third
1010 { $values
1011      { "third" object } { "seq" sequence } }
1012 { $description "Sets the third element of a sequence." }
1013 { $examples
1014     { $example "USING: prettyprint kernel sequences ;"
1015         "{ 1 2 3 4  } 5 over set-third ."
1016         "{ 1 2 5 4 }"
1017     }
1018 } ;
1019
1020 HELP: set-fourth
1021 { $values
1022      { "fourth" object } { "seq" sequence } }
1023 { $description "Sets the fourth element of a sequence." }
1024 { $examples
1025     { $example "USING: prettyprint kernel sequences ;"
1026         "{ 1 2 3 4  } 5 over set-fourth ."
1027         "{ 1 2 3 5 }"
1028     }
1029 } ;
1030
1031 { set-first set-second set-third set-fourth } related-words
1032
1033 HELP: replicate
1034 { $values
1035      { "seq" sequence } { "quot" quotation }
1036      { "newseq" sequence } }
1037 { $description "Calls the quotation for every element of the sequence in order. However, the element is not passed to the quotation -- it is dropped, and the quotation produces an element of its own that is collected into a sequence of the same class as the input sequence." }
1038 { $examples
1039     { $unchecked-example "USING: prettyprint kernel sequences ;"
1040         "5 [ 100 random ] replicate ."
1041         "{ 52 10 45 81 30 }"
1042     }
1043 } ;
1044
1045 HELP: replicate-as
1046 { $values
1047      { "seq" sequence } { "quot" quotation } { "exemplar" sequence }
1048      { "newseq" sequence } }
1049 { $description "Calls the quotation for every element of the sequence in order. However, the element is not passed to the quotation -- it is dropped, and the quotation produces an element of its own that is collected into a sequence of the same class as the exemplar sequence." }
1050 { $examples
1051     { $unchecked-example "USING: prettyprint kernel sequences ;"
1052         "5 [ 100 random ] B{ } replicate-as ."
1053         "B{ 44 8 2 33 18 }"
1054     }
1055 } ;
1056 { replicate replicate-as } related-words
1057
1058 HELP: partition
1059 { $values
1060      { "seq" sequence } { "quot" quotation }
1061      { "trueseq" sequence } { "falseseq" sequence } }
1062      { $description "Calls a predicate quotation on each element of the input sequence.  If the test yields true, the element is added to " { $snippet "trueseq" } "; if false, it's added to " { $snippet "falseseq" } "." }
1063 { $examples
1064     { $example "USING: prettyprint kernel math sequences ;"
1065         "{ 1 2 3 4 5 } [ even? ] partition [ . ] bi@"
1066         "{ 2 4 }\n{ 1 3 5 }"
1067     }
1068 } ;
1069
1070 HELP: virtual-seq
1071 { $values
1072      { "seq" sequence }
1073      { "seq'" sequence } }
1074 { $description "Part of the virtual sequence protocol, this word is used to return an underlying array from which to look up a value at an index given by " { $link virtual@ } "." } ;
1075
1076 HELP: virtual@
1077 { $values
1078      { "n" integer } { "seq" sequence }
1079      { "n'" integer } { "seq'" sequence } }
1080 { $description "Part of the sequence protocol, this word translates the input index " { $snippet "n" } " into an index into the underlying storage returned by " { $link virtual-seq } "." } ;
1081
1082 HELP: 2change-each
1083 { $values
1084      { "seq1" sequence } { "seq2" sequence } { "quot" quotation } }
1085 { $description "Calls the quotation on subsequent pairs of objects from the two input sequences. The resulting computation replaces the element in the first sequence." }
1086 { $examples { $example "USING: kernel math sequences prettyprint ;"
1087     "{ 10 20 30 } dup { 60 70 80 } [ + ] 2change-each ."
1088     "{ 70 90 110 }"
1089 } } ;
1090
1091 HELP: 2map-reduce
1092 { $values
1093      { "seq1" sequence } { "seq2" sequence } { "map-quot" quotation } { "reduce-quot" quotation }
1094      { "result" object } }
1095 { $description "Unclips the first element of each sequence and calls " { $snippet "map-quot" } " on both objects. The result of this calculation is passed, along with the rest of both sequences, to " { $link 2reduce } ", with the computed object as the identity." }
1096 { $examples { $example "USING: sequences prettyprint math ;"
1097     "{ 10 30 50 } { 200 400 600 } [ + ] [ + ] 2map-reduce ."
1098     "1290"
1099 } } ;
1100
1101 HELP: 2pusher
1102 { $values
1103      { "quot" quotation }
1104      { "quot" quotation } { "accum1" vector } { "accum2" vector } }
1105 { $description "Creates two new vectors to accumultate values based on a predicate. The first vector accumulates values for which the predicate yields true; the second for false." } ;
1106
1107 HELP: 2reverse-each
1108 { $values
1109      { "seq1" sequence } { "seq2" sequence } { "quot" quotation } }
1110 { $description "Reverse the sequences using the " { $link <reversed> } " word and calls " { $link 2each } " on the reversed sequences." }
1111 { $examples { $example "USING: sequences math prettyprint ;"
1112     "{ 10 20 30 } { 1 2 3 } [ + . ] 2reverse-each"
1113     "33\n22\n11"
1114 } } ;
1115
1116 HELP: 2unclip-slice
1117 { $values
1118      { "seq1" sequence } { "seq2" sequence }
1119      { "rest-slice1" sequence } { "rest-slice2" sequence } { "first1" object } { "first2" object } }
1120 { $description "Unclips the first element of each sequence and leaves two slice elements and the two unclipped objects on the stack." }
1121 { $examples { $example "USING: sequences prettyprint kernel arrays ;"
1122     "{ 1 2 } { 3 4 } 2unclip-slice 4array [ . ] each"
1123     "T{ slice { from 1 } { to 2 } { seq { 1 2 } } }\nT{ slice { from 1 } { to 2 } { seq { 3 4 } } }\n1\n3"
1124 } } ;
1125
1126 HELP: accumulator
1127 { $values
1128      { "quot" quotation }
1129      { "quot'" quotation } { "vec" vector } }
1130 { $description "Creates a new quotation that pushes its result to a vector and outputs that vector on the stack." }
1131 { $examples { $example "USING: sequences prettyprint kernel math ;"
1132     "{ 1 2 } [ 30 + ] accumulator [ each ] dip ."
1133     "V{ 31 32 }"
1134 } } ;
1135
1136 HELP: binary-reduce
1137 { $values
1138      { "seq" sequence } { "start" integer } { "quot" quotation }
1139      { "value" object } }
1140 { $description "Like " { $link reduce } ", but splits the sequence in half recursively until each sequence is small enough, and calls the quotation on these smaller sequences. If the quotation computes values that depend on the size of their input, such as bignum arithmetic, then this algorithm can be more efficient than using " { $link reduce } "." }
1141 { $examples "Computing factorial:"
1142     { $example "USING: prettyprint sequences math ;"
1143     "40 rest-slice 1 [ * ] binary-reduce ."
1144     "20397882081197443358640281739902897356800000000" }
1145 } ;
1146
1147 HELP: follow
1148 { $values
1149      { "obj" object } { "quot" quotation }
1150      { "seq" sequence } }
1151 { $description "Outputs a sequence containing the input object and all of the objects generated by successively feeding the result of the quotation called on the input object to the quotation recursuively. Objects yielded by the quotation are added to the output sequence until the quotation yields " { $link f } ", at which point the recursion terminates." }
1152 { $examples "Get random numbers until zero is reached:"
1153     { $unchecked-example
1154     "USING: random sequences prettyprint math ;"
1155     "100 [ random dup zero? [ drop f ] when ] follow ."
1156     "{ 100 86 34 32 24 11 7 2 }"
1157 } } ;
1158
1159 HELP: halves
1160 { $values
1161      { "seq" sequence }
1162      { "first-slice" slice } { "second-slice" slice } }
1163 { $description "Splits a sequence into two slices at the midpoint. If the sequence has an odd number of elements, the extra element is returned in the second slice." }
1164 { $examples { $example "USING: arrays sequences prettyprint kernel ;"
1165     "{ 1 2 3 4 5 } halves [ >array . ] bi@"
1166     "{ 1 2 }\n{ 3 4 5 }"
1167 } } ;
1168
1169 HELP: indices
1170 { $values
1171      { "obj" object } { "seq" sequence }
1172      { "indices" sequence } }
1173 { $description "Compares the input object to every element in the sequence and returns a vector containing the index of every position where the element was found." }
1174 { $examples { $example "USING: sequences prettyprint ;"
1175     "2 { 2 4 2 6 2 8 2 10 } indices ."
1176     "V{ 0 2 4 6 }"
1177 } } ;
1178
1179 HELP: insert-nth
1180 { $values
1181      { "elt" object } { "n" integer } { "seq" sequence }
1182      { "seq'" sequence } }
1183 { $description "Creates a new sequence where the " { $snippet "n" } "th index is set to the input object." }
1184 { $examples { $example "USING: prettyprint sequences ;"
1185     "40 3 { 10 20 30 50 } insert-nth ."
1186     "{ 10 20 30 40 50 }"
1187 } } ;
1188
1189 HELP: map-reduce
1190 { $values
1191      { "seq" sequence } { "map-quot" quotation } { "reduce-quot" quotation }
1192      { "result" object } }
1193 { $description "Unclips the first element of the sequence, calls " { $snippet "map-quot" } " on that element, and proceeds like a " { $link reduce } ", where the calculated element is the identity element and the rest of the sequence is the sequence to reduce." }
1194 { $examples { $example "USING: sequences prettyprint math ;"
1195     "{ 1 3 5 } [ sq ] [ + ] map-reduce ."
1196     "35"
1197 } } ;
1198
1199 HELP: new-like
1200 { $values
1201      { "len" integer } { "exemplar" "an exemplar sequence" } { "quot" quotation }
1202      { "seq" sequence } }
1203 { $description "Creates a new sequence of length " { $snippet "len" } " and calls the quotation with this sequence on the stack. The output of the quotation and the original exemplar are then passed to " { $link like } " so that the output sequence is the exemplar's type." } ;
1204
1205 HELP: push-either
1206 { $values
1207      { "elt" object } { "quot" quotation } { "accum1" vector } { "accum2" vector } }
1208 { $description "Pushes the input object onto one of the accumualators; the first if the quotation yields true, the second if false." } ;
1209
1210 HELP: sequence-hashcode
1211 { $values
1212      { "n" integer } { "seq" sequence }
1213      { "x" integer } }
1214 { $description "Iterates over a sequence, computes a hashcode with " { $link hashcode* } " for each element, and combines them using " { $link sequence-hashcode-step } "." } ;
1215
1216 HELP: sequence-hashcode-step
1217 { $values
1218      { "oldhash" integer } { "newpart" integer }
1219      { "newhash" integer } }
1220 { $description "An implementation word that computes a running hashcode of a sequence using some bit-twiddling. The resulting hashcode is always a fixnum." } ;
1221
1222 HELP: short
1223 { $values
1224      { "seq" sequence } { "n" integer }
1225      { "seq" sequence } { "n'" integer } }
1226 { $description "Returns the input sequence and its length or " { $snippet "n" } ", whichever is less." }
1227 { $examples { $example "USING: sequences kernel prettyprint ;"
1228     "\"abcd\" 3 short [ . ] bi@"
1229     "\"abcd\"\n3"
1230 } } ;
1231
1232 HELP: shorten
1233 { $values
1234      { "n" integer } { "seq" sequence } }
1235 { $description "Shortens a " { $link "growable" } " sequence to by " { $snippet "n" } " elements long." }
1236 { $examples { $example "USING: sequences prettyprint kernel ;"
1237     "V{ 1 2 3 4 5 } 3 over shorten ."
1238     "V{ 1 2 3 }"
1239 } } ;
1240
1241 ARTICLE: "sequences-unsafe" "Unsafe sequence operations"
1242 "The " { $link nth-unsafe } " and " { $link set-nth-unsafe } " sequence protocol bypasses bounds checks for increased performance."
1243 $nl
1244 "These words assume the sequence index given is within bounds; if it is not, memory corruption can occur. Great care must be exercised when using these words. First, make sure the code in question is actually a bottleneck; next, try improving the algorithm first. If all else fails, then the unsafe sequence words can be used."
1245 $nl
1246 "There is a very important invariant these word must preserve: if at some point in time, the length of a sequence was " { $snippet "n" } ", then any future lookups of elements with indices below " { $snippet "n" } " must not crash the VM, even if the sequence length is now less than " { $snippet "n" } ". For example, vectors preserve this invariant by never shrinking the underlying storage, only growing it as necessary."
1247 $nl
1248 "The justification for this is that the VM should not crash if a resizable sequence is resized during the execution of an iteration combinator."
1249 $nl
1250 "Indeed, iteration combinators are the primary use-case for these words; if the iteration index is already guarded by a loop test which ensures it is within bounds, then additional bounds checks are redundant. For example, see the implementation of " { $link each } "." ;
1251
1252 ARTICLE: "sequence-protocol" "Sequence protocol"
1253 "All sequences must be instances of a mixin class:"
1254 { $subsection sequence }
1255 { $subsection sequence? }
1256 "All sequences must know their length:"
1257 { $subsection length }
1258 "At least one of the following two generic words must have a method for accessing elements; the " { $link sequence } " mixin has default definitions which are mutually recursive:"
1259 { $subsection nth }
1260 { $subsection nth-unsafe }
1261 "Note that sequences are always indexed starting from zero."
1262 $nl
1263 "At least one of the following two generic words must have a method for storing elements; the " { $link sequence } " mixin has default definitions which are mutually recursive:"
1264 { $subsection set-nth }
1265 { $subsection set-nth-unsafe }
1266 "Note that even if the sequence is immutable, at least one of the generic words must be specialized, otherwise calling them will result in an infinite recursion. There is a standard word which throws an error indicating a sequence is immutable:"
1267 { $subsection immutable }
1268 "The following two generic words are optional, as not all sequences are resizable:"
1269 { $subsection set-length }
1270 { $subsection lengthen }
1271 "An optional generic word for creating sequences of the same class as a given sequence:"
1272 { $subsection like }
1273 "Optional generic words for optimization purposes:"
1274 { $subsection new-sequence }
1275 { $subsection new-resizable }
1276 { $see-also "sequences-unsafe" } ;
1277
1278 ARTICLE: "virtual-sequences-protocol" "Virtual sequence protocol"
1279 "Virtual sequences must know their length:"
1280 { $subsection length }
1281 "The underlying sequence to look up a value in:"
1282 { $subsection virtual-seq }
1283 "The index of the value in the underlying sequence:"
1284 { $subsection virtual@ } ;
1285
1286 ARTICLE: "virtual-sequences" "Virtual sequences"
1287 "Virtual sequences allow different ways of accessing a sequence without having to create a new sequence or a new data structure altogether. To do this, they translate the virtual index into a normal index into an underlying sequence using the " { $link "virtual-sequences-protocol" } "."
1288 { $subsection "virtual-sequences-protocol" } ;
1289
1290 ARTICLE: "sequences-integers" "Integer sequences and counted loops"
1291 "Integers support the sequence protocol in a trivial fashion; a non-negative integer presents its non-negative predecessors as elements. For example, the integer 3, when viewed as a sequence, contains the elements 0, 1, and 2. This is very useful for performing counted loops."
1292 $nl
1293 "For example, the " { $link each } " combinator, given an integer, simply calls a quotation that number of times, pushing a counter on each iteration that ranges from 0 up to that integer:"
1294 { $example "3 [ . ] each" "0\n1\n2" }
1295 "A common idiom is to iterate over a sequence, while also maintaining a loop counter. This can be done using " { $link each-index } ", " { $link map-index } " and " { $link reduce-index } "."
1296 $nl
1297 "Combinators that produce new sequences, such as " { $link map } ", will output an array if the input is an integer." ;
1298
1299 ARTICLE: "sequences-access" "Accessing sequence elements"
1300 { $subsection ?nth }
1301 "Concise way of extracting one of the first four elements:"
1302 { $subsection first }
1303 { $subsection second }
1304 { $subsection third }
1305 { $subsection fourth }
1306 "Unpacking sequences:"
1307 { $subsection first2 }
1308 { $subsection first3 }
1309 { $subsection first4 }
1310 { $see-also nth peek } ;
1311
1312 ARTICLE: "sequences-add-remove" "Adding and removing sequence elements"
1313 "Adding elements:"
1314 { $subsection prefix }
1315 { $subsection suffix }
1316 "Removing elements:"
1317 { $subsection remove }
1318 { $subsection remove-nth } ;
1319
1320 ARTICLE: "sequences-reshape" "Reshaping sequences"
1321 "A " { $emphasis "repetition" } " is a virtual sequence consisting of a single element repeated multiple times:"
1322 { $subsection repetition }
1323 { $subsection <repetition> }
1324 "Reversing a sequence:"
1325 { $subsection reverse }
1326 "A " { $emphasis "reversal" } " presents a reversed view of an underlying sequence:"
1327 { $subsection reversed }
1328 { $subsection <reversed> }
1329 "Transposing a matrix:"
1330 { $subsection flip } ;
1331
1332 ARTICLE: "sequences-appending" "Appending sequences"
1333 { $subsection append }
1334 { $subsection prepend }
1335 { $subsection 3append }
1336 { $subsection concat }
1337 { $subsection join }
1338 "A pair of words useful for aligning strings:"
1339 { $subsection pad-left }
1340 { $subsection pad-right } ;
1341
1342 ARTICLE: "sequences-slices" "Subsequences and slices"
1343 "Extracting a subsequence:"
1344 { $subsection subseq }
1345 { $subsection head }
1346 { $subsection tail }
1347 { $subsection head* }
1348 { $subsection tail* }
1349 "Removing the first or last element:"
1350 { $subsection rest }
1351 { $subsection but-last }
1352 "Taking a sequence apart into a head and a tail:"
1353 { $subsection unclip }
1354 { $subsection unclip-last }
1355 { $subsection cut }
1356 { $subsection cut* }
1357 "A " { $emphasis "slice" } " is a virtual sequence which presents as view of a subsequence of an underlying sequence:"
1358 { $subsection slice }
1359 { $subsection slice? }
1360 "Extracting a slice:"
1361 { $subsection <slice> }
1362 { $subsection head-slice }
1363 { $subsection tail-slice }
1364 { $subsection head-slice* }
1365 { $subsection tail-slice* }
1366 "Removing the first or last element:"
1367 { $subsection rest-slice }
1368 { $subsection but-last-slice }
1369 "Taking a sequence apart into a head and a tail:"
1370 { $subsection unclip-slice }
1371 { $subsection unclip-last-slice }
1372 { $subsection cut-slice }
1373 "A utility for words which use slices as iterators:"
1374 { $subsection <flat-slice> } ;
1375
1376 ARTICLE: "sequences-combinators" "Sequence combinators"
1377 "Iteration:"
1378 { $subsection each }
1379 { $subsection each-index }
1380 { $subsection reduce }
1381 { $subsection interleave }
1382 { $subsection replicate }
1383 { $subsection replicate-as }
1384 "Mapping:"
1385 { $subsection map }
1386 { $subsection map-as }
1387 { $subsection map-index }
1388 { $subsection accumulate }
1389 { $subsection produce }
1390 "Filtering:"
1391 { $subsection push-if }
1392 { $subsection filter }
1393 "Testing if a sequence contains elements satisfying a predicate:"
1394 { $subsection contains? }
1395 { $subsection all? }
1396 "Testing how elements are related:"
1397 { $subsection monotonic? }
1398 { $subsection "sequence-2combinators" } ;
1399
1400 ARTICLE: "sequence-2combinators" "Pair-wise sequence combinators"
1401 "There is a set of combinators which traverse two sequences pairwise. If one sequence is shorter than the other, than only the prefix having the length of the minimum of the two is examined."
1402 { $subsection 2each }
1403 { $subsection 2reduce }
1404 { $subsection 2map }
1405 { $subsection 2map-as }
1406 { $subsection 2all? } ;
1407
1408 ARTICLE: "sequences-tests" "Testing sequences"
1409 "Testing for an empty sequence:"
1410 { $subsection empty? }
1411 "Testing indices:"
1412 { $subsection bounds-check? }
1413 "Testing if a sequence contains an object:"
1414 { $subsection member? }
1415 { $subsection memq? }
1416 "Testing if a sequence contains a subsequence:"
1417 { $subsection head? }
1418 { $subsection tail? }
1419 { $subsection subseq? }
1420 "Testing how elements are related:"
1421 { $subsection all-eq? }
1422 { $subsection all-equal? } ;
1423
1424 ARTICLE: "sequences-search" "Searching sequences"
1425 "Finding the index of an element:"
1426 { $subsection index }
1427 { $subsection index-from }
1428 { $subsection last-index }
1429 { $subsection last-index-from }
1430 "Finding the start of a subsequence:"
1431 { $subsection start }
1432 { $subsection start* }
1433 "Finding the index of an element satisfying a predicate:"
1434 { $subsection find }
1435 { $subsection find-from }
1436 { $subsection find-last }
1437 { $subsection find-last-from } ;
1438
1439 ARTICLE: "sequences-trimming" "Trimming sequences"
1440 "Trimming words:"
1441 { $subsection trim }
1442 { $subsection trim-left }
1443 { $subsection trim-right }
1444 "Potentially more efficient trim:"
1445 { $subsection trim-slice }
1446 { $subsection trim-left-slice }
1447 { $subsection trim-right-slice } ;
1448
1449 ARTICLE: "sequences-destructive" "Destructive operations"
1450 "These words modify their input, instead of creating a new sequence."
1451 $nl
1452 "In-place variant of " { $link reverse } ":"
1453 { $subsection reverse-here }
1454 "In-place variant of " { $link append } ":"
1455 { $subsection push-all }
1456 "In-place variant of " { $link remove } ":"
1457 { $subsection delete }
1458 "In-place variant of " { $link map } ":"
1459 { $subsection change-each }
1460 "Changing elements:"
1461 { $subsection change-nth }
1462 { $subsection cache-nth }
1463 "Deleting elements:"
1464 { $subsection delete-nth }
1465 { $subsection delete-slice }
1466 { $subsection delete-all }
1467 "Other destructive words:"
1468 { $subsection move }
1469 { $subsection exchange }
1470 { $subsection copy }
1471 { $subsection replace-slice }
1472 { $see-also set-nth push pop "sequences-stacks" } ;
1473
1474 ARTICLE: "sequences-stacks" "Treating sequences as stacks"
1475 "The classical stack operations, modifying a sequence in place:"
1476 { $subsection peek }
1477 { $subsection push }
1478 { $subsection pop }
1479 { $subsection pop* }
1480 { $see-also empty? } ;
1481
1482 ARTICLE: "sequences-comparing" "Comparing sequences"
1483 "Element equality testing:"
1484 { $subsection sequence= }
1485 { $subsection mismatch }
1486 { $subsection drop-prefix }
1487 "The " { $link <=> } " generic word performs lexicographic comparison when applied to sequences." ;
1488
1489 ARTICLE: "sequences-f" "The f object as a sequence"
1490 "The " { $link f } " object supports the sequence protocol in a trivial way. It responds with a length of zero and throws an out of bounds error when an attempt is made to access elements." ;
1491
1492 ARTICLE: "sequences" "Sequence operations"
1493 "A " { $emphasis "sequence" } " is a finite, linearly-ordered collection of elements. Words for working with sequences are in the " { $vocab-link "sequences" } " vocabulary."
1494 $nl
1495 "Sequences implement a protocol:"
1496 { $subsection "sequence-protocol" }
1497 { $subsection "sequences-f" }
1498 { $subsection "sequences-integers" }
1499 "Sequence utility words can operate on any object whose class implements the sequence protocol. Most implementations are backed by storage. Some implementations obtain their elements from an underlying sequence, or compute them on the fly. These are known as " { $link "virtual-sequences" } "."
1500 { $subsection "sequences-access" }
1501 { $subsection "sequences-combinators" }
1502 { $subsection "sequences-add-remove" }
1503 { $subsection "sequences-appending" }
1504 { $subsection "sequences-slices" }
1505 { $subsection "sequences-reshape" }
1506 { $subsection "sequences-tests" }
1507 { $subsection "sequences-search" }
1508 { $subsection "sequences-comparing" }
1509 { $subsection "sequences-split" }
1510 { $subsection "grouping" }
1511 { $subsection "sequences-destructive" }
1512 { $subsection "sequences-stacks" }
1513 { $subsection "sequences-sorting" }
1514 { $subsection "binary-search" }
1515 { $subsection "sets" }
1516 { $subsection "sequences-trimming" }
1517 "For inner loops:"
1518 { $subsection "sequences-unsafe" } ;
1519
1520 ABOUT: "sequences"