core/sequences/sequences-docs.factor

   1 USING: assocs arrays generic.single help.markup help.syntax kernel
   2 layouts math math.order quotations sequences.private vectors ;
   3 IN: sequences
   4
   5 HELP: sequence
   6 { $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:"
   7     { $code "INSTANCE: my-sequence sequence" }
   8 } ;
   9
  10 HELP: length
  11 { $values { "seq" sequence } { "n" "a non-negative integer" } }
  12 { $contract "Outputs the length of the sequence. All sequences support this operation." } ;
  13
  14 HELP: set-length
  15 { $values { "n" "a non-negative integer" } { "seq" "a resizable sequence" } }
  16 { $contract "Resizes a sequence. The initial contents of the new area is undefined." }
  17 { $errors "Throws a " { $link no-method } " error if the sequence is not resizable, and a " { $link bounds-error } " if the new length is negative." }
  18 { $side-effects "seq" } ;
  19
  20 HELP: lengthen
  21 { $values { "n" "a non-negative integer" } { "seq" "a resizable sequence" } }
  22 { $contract "Ensures the sequence has a length of at least " { $snippet "n" } " elements. This word differs from " { $link set-length } " in two respects:"
  23     { $list
  24         { "This word does not shrink the sequence if " { $snippet "n" } " is less than its length." }
  25         { "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." }
  26     }
  27 } ;
  28
  29 HELP: nth
  30 { $values { "n" "a non-negative integer" } { "seq" sequence } { "elt" "the element at the " { $snippet "n" } "th index" } }
  31 { $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." }
  32 { $errors "Throws a " { $link bounds-error } " if the index is negative, or greater than or equal to the length of the sequence." } ;
  33
  34 HELP: set-nth
  35 { $values { "elt" object } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
  36 { $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." }
  37 { $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."
  38 $nl
  39 "Throws an error if the sequence cannot hold elements of the given type." }
  40 { $side-effects "seq" } ;
  41
  42 HELP: nths
  43 { $values
  44      { "indices" sequence } { "seq" sequence }
  45      { "seq'" sequence } }
  46 { $description "Outputs a sequence of elements from the input sequence indexed by the indices." }
  47 { $examples
  48     { $example "USING: prettyprint sequences ;"
  49                "{ 0 2 } { \"a\" \"b\" \"c\" } nths ."
  50                "{ \"a\" \"c\" }"
  51     }
  52 } ;
  53
  54 HELP: immutable
  55 { $values { "seq" sequence } }
  56 { $description "Throws an " { $link immutable } " error." }
  57 { $error-description "Thrown if an attempt is made to modify an immutable sequence." } ;
  58
  59 HELP: new-sequence
  60 { $values { "len" "a non-negative integer" } { "seq" sequence } { "newseq" "a mutable sequence" } }
  61 { $contract "Outputs a mutable sequence of length " { $snippet "len" } " which can hold the elements of " { $snippet "seq" } ". The initial contents of the sequence are undefined." } ;
  62
  63 HELP: new-resizable
  64 { $values { "len" "a non-negative integer" } { "seq" sequence } { "newseq" "a resizable mutable sequence" } }
  65 { $contract "Outputs a resizable mutable sequence with an initial capacity of " { $snippet "len" } " elements and zero length, which can hold the elements of " { $snippet "seq" } "." }
  66 { $examples
  67     { $example "USING: prettyprint sequences ;" "300 V{ } new-resizable ." "V{ }" }
  68     { $example "USING: prettyprint sequences ;" "300 SBUF\" \" new-resizable ." "SBUF\" \"" }
  69 } ;
  70
  71 HELP: like
  72 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" "a new sequence" } }
  73 { $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."
  74 $nl
  75 "The default implementation does nothing." }
  76 { $notes "Unlike " { $link clone-like } ", the output sequence might share storage with the input sequence." } ;
  77
  78 HELP: empty?
  79 { $values { "seq" sequence } { "?" boolean } }
  80 { $description "Tests if the sequence has zero length." } ;
  81
  82 HELP: if-empty
  83 { $values { "seq" sequence } { "quot1" quotation } { "quot2" quotation } }
  84 { $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." }
  85 { $examples
  86     { $example
  87         "USING: kernel prettyprint sequences ;"
  88         "{ 1 2 3 } [ \"empty sequence\" ] [ sum ] if-empty ."
  89         "6"
  90     }
  91 } ;
  92
  93 HELP: when-empty
  94 { $values
  95      { "seq" sequence } { "quot" "the first quotation of an " { $link if-empty } } }
  96 { $description "Makes an implicit check if the sequence is empty. An empty sequence is dropped and the " { $snippet "quot" } " is called." }
  97 { $examples "This word is equivalent to " { $link if-empty } " with an empty second quotation:"
  98     { $example
  99     "USING: sequences prettyprint ;"
 100     "{ } [ { 4 5 6 } ] [ ] if-empty ."
 101     "{ 4 5 6 }"
 102     }
 103     { $example
 104     "USING: sequences prettyprint ;"
 105     "{ } [ { 4 5 6 } ] when-empty ."
 106     "{ 4 5 6 }"
 107     }
 108 } ;
 109
 110 HELP: unless-empty
 111 { $values
 112      { "seq" sequence } { "quot" "the second quotation of an " { $link if-empty } } }
 113 { $description "Makes an implicit check if the sequence is empty. An empty sequence is dropped. Otherwise, the " { $snippet "quot" } " is called on the sequence." }
 114 { $examples "This word is equivalent to " { $link if-empty } " with an empty first quotation:"
 115     { $example
 116     "USING: sequences prettyprint ;"
 117     "{ 4 5 6 } [ ] [ sum ] if-empty ."
 118     "15"
 119     }
 120     { $example
 121     "USING: sequences prettyprint ;"
 122     "{ 4 5 6 } [ sum ] unless-empty ."
 123     "15"
 124     }
 125 } ;
 126
 127 HELP: delete-all
 128 { $values { "seq" "a resizable sequence" } }
 129 { $description "Resizes the sequence to zero length, removing all elements. Not all sequences are resizable." }
 130 { $errors "Throws a " { $link bounds-error } " if the new length is negative, or if the sequence is not resizable." }
 131 { $side-effects "seq" } ;
 132
 133 HELP: resize
 134 { $values { "n" "a non-negative integer" } { "seq" sequence } { "newseq" "a new sequence" } }
 135 { $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." }
 136 { $notes "This generic word is only implemented for strings and arrays." } ;
 137
 138 HELP: first
 139 { $values { "seq" sequence } { "first" "the first element of the sequence" } }
 140 { $description "Outputs the first element of the sequence." }
 141 { $errors "Throws an error if the sequence is empty." } ;
 142
 143 HELP: second
 144 { $values { "seq" sequence } { "second" "the second element of the sequence" } }
 145 { $description "Outputs the second element of the sequence." }
 146 { $errors "Throws an error if the sequence contains less than two elements." } ;
 147
 148 HELP: third
 149 { $values { "seq" sequence } { "third" "the third element of the sequence" } }
 150 { $description "Outputs the third element of the sequence." }
 151 { $errors "Throws an error if the sequence contains less than three elements." } ;
 152
 153 HELP: fourth
 154 { $values { "seq" sequence } { "fourth" "the fourth element of the sequence" } }
 155 { $description "Outputs the fourth element of the sequence." }
 156 { $errors "Throws an error if the sequence contains less than four elements." } ;
 157
 158 HELP: push
 159 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 160 { $description "Adds an element at the end of the sequence. The sequence length is adjusted accordingly." }
 161 { $errors "Throws an error if " { $snippet "seq" } " is not resizable, or if the type of " { $snippet "elt" } " is not permitted in " { $snippet "seq" } "." }
 162 { $side-effects "seq" } ;
 163
 164 HELP: bounds-check?
 165 { $values { "n" integer } { "seq" sequence } { "?" boolean } }
 166 { $description "Tests if the index is within the bounds of the sequence." } ;
 167
 168 HELP: bounds-error
 169 { $values { "n" "a positive integer" } { "seq" sequence } }
 170 { $description "Throws a " { $link bounds-error } "." }
 171 { $error-description "Thrown by " { $link nth } ", " { $link set-nth } " and " { $link set-length } " if the given index lies beyond the bounds of the sequence." } ;
 172
 173 HELP: bounds-check
 174 { $values { "n" "a positive integer" } { "seq" sequence } }
 175 { $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." } ;
 176
 177 HELP: ?nth
 178 { $values { "n" integer } { "seq" sequence } { "elt/f" "an object or " { $link f } } }
 179 { $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 } "." } ;
 180
 181 HELP: ?set-nth
 182 { $values { "elt" object } { "n" integer } { "seq" sequence } }
 183 { $description "A forgiving version of " { $link set-nth } ".  If the index is out of bounds, does nothing." } ;
 184
 185 HELP: ?first
 186 { $values { "seq" sequence } { "elt/f" "an object or " { $link f } } }
 187 { $description "A forgiving version of " { $link first } ". If the sequence is empty, or if the sequence is " { $link f } ", simply outputs " { $link f } "." }
 188 { $examples
 189     "On an empty sequence:"
 190     { $example "USING: sequences prettyprint ;"
 191                "{ } ?first ."
 192                "f"
 193     }
 194     "Works like first on sequences with elements:"
 195     { $example "USING: sequences prettyprint ;"
 196                "{ 1 2 3 } ?first ."
 197                "1"
 198     }
 199 } ;
 200
 201
 202 HELP: ?second
 203 { $values { "seq" sequence } { "elt/f" "an object or " { $link f } } }
 204 { $description "A forgiving version of " { $link second } ". If the sequence has less than two elements, or if the sequence is " { $link f } ", simply outputs " { $link f } "." } ;
 205
 206 HELP: ?last
 207 { $values { "seq" sequence } { "elt/f" "an object or " { $link f } } }
 208 { $description "A forgiving version of " { $link last } ". If the sequence is empty, or if the sequence is " { $link f } ", simply outputs " { $link f } "." } ;
 209
 210 HELP: nth-unsafe
 211 { $values { "n" integer } { "seq" sequence } { "elt" object } }
 212 { $contract "Unsafe variant of " { $link nth } " that does not perform bounds checks." } ;
 213
 214 HELP: set-nth-unsafe
 215 { $values { "elt" object } { "n" integer } { "seq" sequence } }
 216 { $contract "Unsafe variant of " { $link set-nth } " that does not perform bounds checks." } ;
 217
 218 HELP: exchange-unsafe
 219 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 220 { $description "Unsafe variant of " { $link exchange } " that does not perform bounds checks." } ;
 221
 222 HELP: first-unsafe
 223 { $values { "seq" sequence } { "first" "the first element" } }
 224 { $contract "Unsafe variant of " { $link first } " that does not perform bounds checks." } ;
 225
 226 HELP: first2-unsafe
 227 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } }
 228 { $contract "Unsafe variant of " { $link first2 } " that does not perform bounds checks." } ;
 229
 230 HELP: first3-unsafe
 231 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } }
 232 { $contract "Unsafe variant of " { $link first3 } " that does not perform bounds checks." } ;
 233
 234 HELP: first4-unsafe
 235 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } { "fourth" "the fourth element" } }
 236 { $contract "Unsafe variant of " { $link first4 } " that does not perform bounds checks." } ;
 237
 238 HELP: 1sequence
 239 { $values { "obj" object } { "exemplar" sequence } { "seq" sequence } }
 240 { $description "Creates a one-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 241
 242 HELP: 2sequence
 243 { $values { "obj1" object } { "obj2" object } { "exemplar" sequence } { "seq" sequence } }
 244 { $description "Creates a two-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 245
 246 HELP: 3sequence
 247 { $values { "obj1" object } { "obj2" object } { "obj3" object } { "exemplar" sequence } { "seq" sequence } }
 248 { $description "Creates a three-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 249
 250 HELP: 4sequence
 251 { $values { "obj1" object } { "obj2" object } { "obj3" object } { "obj4" object } { "exemplar" sequence } { "seq" sequence } }
 252 { $description "Creates a four-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 253
 254 HELP: first2
 255 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } }
 256 { $description "Pushes the first two elements of a sequence." }
 257 { $errors "Throws an error if the sequence has less than two elements." } ;
 258
 259 HELP: first3
 260 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } }
 261 { $description "Pushes the first three elements of a sequence." }
 262 { $errors "Throws an error if the sequence has less than three elements." } ;
 263
 264 HELP: first4
 265 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } { "fourth" "the fourth element" } }
 266 { $description "Pushes the first four elements of a sequence." }
 267 { $errors "Throws an error if the sequence has less than four elements." } ;
 268
 269 HELP: array-capacity
 270 { $values { "array" array } { "n" "a non-negative fixnum" } }
 271 { $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 } "." }
 272 { $description "Low-level array length accessor." }
 273 { $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." } ;
 274
 275 HELP: array-nth
 276 { $values { "n" "a non-negative fixnum" } { "array" array } { "elt" object } }
 277 { $description "Low-level array element accessor." }
 278 { $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. User code must use " { $link nth } " instead." } ;
 279
 280 HELP: set-array-nth
 281 { $values { "elt" object } { "n" "a non-negative fixnum" } { "array" array } }
 282 { $description "Low-level array element mutator." }
 283 { $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. User code must use " { $link set-nth } " instead." } ;
 284
 285 HELP: collect
 286 { $values { "n" "a non-negative integer" } { "quot" { $quotation ( ... n -- ... value ) } } { "into" "a sequence of length at least " { $snippet "n" } } }
 287 { $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." }
 288 { $examples
 289   { $example
 290     "USING: kernel math.parser prettyprint sequences sequences.private ;"
 291     "10 [ number>string ] 10 f new-sequence [ collect ] keep ."
 292     "{ \"0\" \"1\" \"2\" \"3\" \"4\" \"5\" \"6\" \"7\" \"8\" \"9\" }"
 293   }
 294 } ;
 295
 296 HELP: each
 297 { $values { "seq" sequence } { "quot" { $quotation ( ... x -- ... ) } } }
 298 { $description "Applies the quotation to each element of the sequence in order." } ;
 299
 300 HELP: reduce
 301 { $values { "seq" sequence } { "identity" object } { "quot" { $quotation ( ... prev elt -- ... next ) } } { "result" "the final result" } }
 302 { $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." }
 303 { $examples
 304     { $example "USING: math prettyprint sequences ;" "{ 1 5 3 } 0 [ + ] reduce ." "9" }
 305 } ;
 306
 307 HELP: reduce-index
 308 { $values
 309      { "seq" sequence } { "identity" object } { "quot" { $quotation ( ... prev elt index -- ... next ) } } { "result" object } }
 310 { $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." }
 311 { $examples { $example "USING: sequences prettyprint math ;"
 312     "{ 10 50 90 } 0 [ + + ] reduce-index ."
 313     "153"
 314 } } ;
 315
 316 HELP: accumulate-as
 317 { $values { "seq" sequence } { "identity" object } { "quot" { $quotation ( ... prev elt -- ... next ) } } { "exemplar" sequence } { "final" "the final result" } { "newseq" "a new sequence" } }
 318 { $description "Combines successive elements of the sequence using a binary operation, and outputs a sequence of the same type as " { $snippet "exemplar" } " containing intermediate results, together with the final result."
 319 $nl
 320 "The first element of the new sequence is " { $snippet "identity" } ". Then, on the first iteration, the two inputs to the quotation are " { $snippet "identity" } ", and the first element of the old sequence. On successive iterations, the first input is the result of the previous iteration, and the second input is the corresponding element of the old sequence."
 321 $nl
 322 "When given the empty sequence, outputs an empty sequence together with the " { $snippet "identity" } "." } ;
 323
 324 HELP: accumulate
 325 { $values { "seq" sequence } { "identity" object } { "quot" { $quotation ( ... prev elt -- ... next ) } } { "final" "the final result" } { "newseq" "a new array" } }
 326 { $description "Combines successive elements of the sequence using a binary operation, and outputs a sequence of intermediate results, together with the final result."
 327 $nl
 328 "The first element of the new sequence is " { $snippet "identity" } ". Then, on the first iteration, the two inputs to the quotation are " { $snippet "identity" } ", and the first element of the old sequence. On successive iterations, the first input is the result of the previous iteration, and the second input is the corresponding element of the old sequence."
 329 $nl
 330 "When given the empty sequence, outputs an empty sequence together with the " { $snippet "identity" } "." }
 331 { $examples
 332     { $example "USING: math prettyprint sequences ;" "{ 2 2 2 2 2 } 0 [ + ] accumulate . ." "{ 0 2 4 6 8 }\n10" }
 333 } ;
 334
 335 HELP: accumulate!
 336 { $values { "seq" sequence } { "identity" object } { "quot" { $quotation ( ... prev elt -- ... next ) } } { "final" "the final result" } }
 337 { $description "Combines successive elements of the sequence using a binary operation, and outputs the original sequence of intermediate results, together with the final result."
 338 $nl
 339 "The first element of the new sequence is " { $snippet "identity" } ". Then, on the first iteration, the two inputs to the quotation are " { $snippet "identity" } ", and the first element of the old sequence. On successive iterations, the first input is the result of the previous iteration, and the second input is the corresponding element of the old sequence."
 340 $nl
 341 "When given the empty sequence, outputs an empty sequence together with the " { $snippet "identity" } "." }
 342 { $examples
 343     { $example "USING: math prettyprint sequences ;" "{ 2 2 2 2 2 } 0 [ + ] accumulate! . ." "{ 0 2 4 6 8 }\n10" }
 344 } ;
 345
 346 HELP: map
 347 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... newelt ) } } { "newseq" "a new sequence" } }
 348 { $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." } ;
 349
 350 HELP: map-as
 351 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... newelt ) } } { "exemplar" sequence } { "newseq" "a new sequence" } }
 352 { $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" } "." }
 353 { $examples
 354     "The following example converts a string into an array of one-element strings:"
 355     { $example "USING: prettyprint strings sequences ;" "\"Hello\" [ 1string ] { } map-as ." "{ \"H\" \"e\" \"l\" \"l\" \"o\" }" }
 356     "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."
 357 } ;
 358
 359 HELP: each-index
 360 { $values
 361      { "seq" sequence } { "quot" { $quotation ( ... elt index -- ... ) } } }
 362 { $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." }
 363 { $examples { $example "USING: arrays sequences prettyprint ;"
 364 "{ 10 20 30 } [ 2array . ] each-index"
 365 "{ 10 0 }\n{ 20 1 }\n{ 30 2 }"
 366 } } ;
 367
 368 HELP: change-nth
 369 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" { $quotation ( ..a elt -- ..b newelt ) } } }
 370 { $description "Applies the quotation to the " { $snippet "i" } "th element of the sequence, storing the result back into the sequence." }
 371 { $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" } "." }
 372 { $side-effects "seq" } ;
 373
 374 HELP: map!
 375 { $values { "seq" "a mutable sequence" } { "quot" { $quotation ( ... elt -- ... newelt ) } } }
 376 { $description "Applies the quotation to each element yielding a new element, storing the new elements back in the original sequence. Returns the original sequence." }
 377 { $errors "Throws an error if the sequence is immutable, or the sequence cannot hold elements of the type output by " { $snippet "quot" } "." }
 378 { $side-effects "seq" } ;
 379
 380 HELP: min-length
 381 { $values { "seq1" sequence } { "seq2" sequence } { "n" "a non-negative integer" } }
 382 { $description "Outputs the minimum of the lengths of the two sequences." } ;
 383
 384 HELP: max-length
 385 { $values { "seq1" sequence } { "seq2" sequence } { "n" "a non-negative integer" } }
 386 { $description "Outputs the maximum of the lengths of the two sequences." } ;
 387
 388 HELP: 2each
 389 { $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ) } } }
 390 { $description "Applies the quotation to pairs of elements from " { $snippet "seq1" } " and " { $snippet "seq2" } "." } ;
 391
 392 HELP: 3each
 393 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "quot" { $quotation ( ... elt1 elt2 elt3 -- ... ) } } }
 394 { $description "Applies the quotation to triples of elements from " { $snippet "seq1" } ", " { $snippet "seq2" } " and " { $snippet "seq3" } "." } ;
 395
 396 HELP: 2reduce
 397 { $values { "seq1" sequence }
 398           { "seq2" sequence }
 399           { "identity" object }
 400           { "quot" { $quotation ( ... prev elt1 elt2 -- ... next ) } }
 401           { "result" "the final result" } }
 402 { $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" } "." } ;
 403
 404 HELP: 2map
 405 { $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... newelt ) } } { "newseq" "a new sequence" } }
 406 { $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" } "." } ;
 407
 408 HELP: 3map
 409 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "quot" { $quotation ( ... elt1 elt2 elt3 -- ... newelt ) } } { "newseq" "a new sequence" } }
 410 { $description "Applies the quotation to each triple of elements in turn, yielding new elements which are collected into a new sequence having the same class as " { $snippet "seq1" } "." } ;
 411
 412 HELP: 2map-as
 413 { $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... newelt ) } } { "exemplar" sequence } { "newseq" "a new sequence" } }
 414 { $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" } "." } ;
 415
 416 HELP: 3map-as
 417 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "quot" { $quotation ( ... elt1 elt2 elt3 -- ... newelt ) } } { "exemplar" sequence } { "newseq" "a new sequence" } }
 418 { $description "Applies the quotation to each triple of elements in turn, yielding new elements which are collected into a new sequence having the same class as " { $snippet "exemplar" } "." } ;
 419
 420 HELP: 2all?
 421 { $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ? ) } } { "?" boolean } }
 422 { $description "Tests the predicate pairwise against elements of " { $snippet "seq1" } " and " { $snippet "seq2" } "." } ;
 423
 424 HELP: find
 425 { $values { "seq" sequence }
 426           { "quot" { $quotation ( ... elt -- ... ? ) } }
 427           { "i" "the index of the first match, or " { $link f } }
 428           { "elt" "the first matching element, or " { $link f } } }
 429 { $description "A simpler variant of " { $link find-from } " where the starting index is 0." } ;
 430
 431 HELP: find-from
 432 { $values { "n" "a starting index" }
 433           { "seq" sequence }
 434           { "quot" { $quotation ( ... elt -- ... ? ) } }
 435           { "i" "the index of the first match, or " { $link f } }
 436           { "elt" "the first matching element, or " { $link f } } }
 437 { $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 " { $link f } " and " { $link f } " as the element." } ;
 438
 439 HELP: find-last
 440 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "i" "the index of the first match, or f" } { "elt" "the first matching element, or " { $link f } } }
 441 { $description "A simpler variant of " { $link find-last-from } " where the starting index is one less than the length of the sequence." } ;
 442
 443 HELP: find-last-from
 444 { $values { "n" "a starting index" } { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "i" "the index of the first match, or f" } { "elt" "the first matching element, or " { $link f } } }
 445 { $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 " { $link f } " and " { $link f } " as the element." } ;
 446
 447 HELP: find-index
 448 { $values { "seq" sequence }
 449           { "quot" { $quotation ( ... elt i -- ... ? ) } }
 450           { "i" "the index of the first match, or " { $link f } }
 451           { "elt" "the first matching element, or " { $link f } } }
 452 { $description "A varient of " { $link find } " where the quotation takes both an element and its index." } ;
 453
 454 HELP: find-index-from
 455 { $values { "n" "a starting index" }
 456           { "seq" sequence }
 457           { "quot" { $quotation ( ... elt i -- ... ? ) } }
 458           { "i" "the index of the first match, or " { $link f } }
 459           { "elt" "the first matching element, or " { $link f } } }
 460 { $description "A varient of " { $link find-from } " where the quotation takes both an element and its index." } ;
 461
 462 HELP: map-find
 463 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... result/f ) } } { "result" "the first non-false result of the quotation" } { "elt" "the first matching element, or " { $link f } } }
 464 { $description "Applies the quotation to each element of the sequence, until the quotation outputs a true value. If the quotation ever yields a result which is not " { $link f } ", then the value is output, along with the element of the sequence which yielded this." } ;
 465
 466 HELP: any?
 467 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "?" boolean } }
 468 { $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 } "." } ;
 469
 470 HELP: all?
 471 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "?" boolean } }
 472 { $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 } "." } ;
 473
 474 HELP: push-if
 475 { $values { "elt" object } { "quot" { $quotation ( ..a elt -- ..b ? ) } } { "accum" "a resizable mutable sequence" } }
 476 { $description "Adds the element at the end of the sequence if the quotation yields a true value." }
 477 { $notes "This word is a factor of " { $link filter } "." } ;
 478
 479 HELP: filter
 480 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "subseq" "a new sequence" } }
 481 { $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." } ;
 482
 483 HELP: filter-as
 484 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "exemplar" sequence } { "subseq" "a new sequence" } }
 485 { $description "Applies the quotation to each element in turn, and outputs a new sequence of the same type as " { $snippet "exemplar" } " containing the elements of the original sequence for which the quotation output a true value." } ;
 486
 487 HELP: filter!
 488 { $values { "seq" "a resizable mutable sequence" } { "quot" { $quotation ( ... elt -- ... ? ) } } }
 489 { $description "Applies the quotation to each element in turn, and removes elements for which the quotation outputs a false value." }
 490 { $side-effects "seq" } ;
 491
 492 HELP: interleave
 493 { $values { "seq" sequence } { "between" quotation } { "quot" { $quotation ( ... elt -- ... ) } } }
 494 { $description "Applies " { $snippet "quot" } " to each element in turn, also invoking " { $snippet "between" } " in-between each pair of elements." }
 495 { $examples { $example "USING: io sequences ;" "{ \"a\" \"b\" \"c\" } [ \"X\" write ] [ write ] interleave" "aXbXc" } } ;
 496
 497 HELP: index
 498 { $values { "obj" object } { "seq" sequence } { "n" "an index" } }
 499 { $description "Outputs the index of the first element in the sequence equal to " { $snippet "obj" } ". If no element is found, outputs " { $link f } "." } ;
 500
 501 HELP: index-from
 502 { $values { "obj" object } { "i" "a start index" } { "seq" sequence } { "n" "an index" } }
 503 { $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 } "." } ;
 504
 505 HELP: last-index
 506 { $values { "obj" object } { "seq" sequence } { "n" "an index" } }
 507 { $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 } "." } ;
 508
 509 HELP: last-index-from
 510 { $values { "obj" object } { "i" "a start index" } { "seq" sequence } { "n" "an index" } }
 511 { $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 } "." } ;
 512
 513 HELP: member?
 514 { $values { "elt" object } { "seq" sequence } { "?" boolean } }
 515 { $description "Tests if the sequence contains an element equal to the object." }
 516 { $examples
 517     "Is a letter in a string:"
 518     { $example
 519         "USING: sequences prettyprint ;"
 520         """CHAR: a "abc" member? ."""
 521         "t"
 522     } $nl
 523     "Is a number in a sequence:"
 524     { $example
 525         "USING: sequences prettyprint ;"
 526         "4 { 1 2 3 } member? ."
 527         "f"
 528     }
 529 }
 530 { $notes "This word uses equality comparison (" { $link = } ")." } ;
 531
 532 HELP: member-eq?
 533 { $values { "elt" object } { "seq" sequence } { "?" boolean } }
 534 { $description "Tests if the sequence contains the object." }
 535 { $notes "This word uses identity comparison (" { $link eq? } ")." } ;
 536
 537 HELP: remove
 538 { $values { "elt" object } { "seq" sequence } { "newseq" "a new sequence" } }
 539 { $description "Outputs a new sequence containing all elements of the input sequence except for given element." }
 540 { $notes "This word uses equality comparison (" { $link = } ")." } ;
 541
 542 HELP: remove-eq
 543 { $values { "elt" object } { "seq" sequence } { "newseq" "a new sequence" } }
 544 { $description "Outputs a new sequence containing all elements of the input sequence except those equal to the given element." }
 545 { $notes "This word uses identity comparison (" { $link eq? } ")." } ;
 546
 547 HELP: remove-nth
 548 { $values
 549      { "n" integer } { "seq" sequence }
 550      { "seq'" sequence } }
 551 { $description "Creates a new sequence without the element at index " { $snippet "n" } "." }
 552 { $examples "Notice that the original sequence is left intact:" { $example "USING: sequences prettyprint kernel ;"
 553     "{ 1 2 3 } 1 over remove-nth . ."
 554     "{ 1 3 }\n{ 1 2 3 }"
 555 } } ;
 556
 557 HELP: move
 558 { $values { "to" "an index in " { $snippet "seq" } } { "from" "an index in " { $snippet "seq" } } { "seq" "a mutable sequence" } }
 559 { $description "Sets the element with index " { $snippet "m" } " to the element with index " { $snippet "n" } "." }
 560 { $side-effects "seq" } ;
 561
 562 HELP: remove!
 563 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 564 { $description "Removes all elements equal to " { $snippet "elt" } " from " { $snippet "seq" } " and returns " { $snippet "seq" } "." }
 565 { $notes "This word uses equality comparison (" { $link = } ")." }
 566 { $side-effects "seq" } ;
 567
 568 HELP: remove-eq!
 569 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 570 { $description "Outputs a new sequence containing all elements of the input sequence except the given element." }
 571 { $notes "This word uses identity comparison (" { $link eq? } ")." }
 572 { $side-effects "seq" } ;
 573
 574 HELP: remove-nth!
 575 { $values { "n" "a non-negative integer" } { "seq" "a resizable mutable sequence" } }
 576 { $description "Removes the " { $snippet "n" } "th element from the sequence, shifting all other elements down and reducing its length by one." }
 577 { $side-effects "seq" } ;
 578
 579 HELP: delete-slice
 580 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" "a resizable mutable sequence" } }
 581 { $description "Removes a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } "." }
 582 { $side-effects "seq" } ;
 583
 584 HELP: replace-slice
 585 { $values { "new" sequence } { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "seq'" sequence } }
 586 { $description "Replaces a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } " with a new sequence." }
 587 { $errors "Throws an error if " { $snippet "new" } " contains elements whose types are not permissible in " { $snippet "seq" } "." } ;
 588
 589 { push prefix suffix } related-words
 590
 591 HELP: suffix
 592 { $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
 593 { $description "Outputs a new sequence obtained by adding " { $snippet "elt" } " at the end of " { $snippet "seq" } "." }
 594 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 595 { $examples
 596     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } 4 suffix ." "{ 1 2 3 4 }" }
 597 } ;
 598
 599 HELP: suffix!
 600 { $values { "seq" sequence } { "elt" object } }
 601 { $description "Modifiers a sequence in-place by adding " { $snippet "elt" } " to the end of " { $snippet "seq" } ". Outputs " { $snippet "seq" } "." }
 602 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq" } "." }
 603 { $examples
 604     { $example "USING: prettyprint sequences ;" "V{ 1 2 3 } 4 suffix! ." "V{ 1 2 3 4 }" }
 605 } ;
 606
 607 HELP: append!
 608 { $values { "seq1" sequence } { "seq2" sequence } }
 609 { $description "Modifiers " { $snippet "seq1" } " in-place by adding the elements from " { $snippet "seq2" } " to the end and outputs " { $snippet "seq1" } "." }
 610 { $examples
 611     { $example "USING: prettyprint sequences ;" "V{ 1 2 3 } { 4 5 6 } append! ." "V{ 1 2 3 4 5 6 }" }
 612 } ;
 613
 614 HELP: prefix
 615 { $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
 616 { $description "Outputs a new sequence obtained by adding " { $snippet "elt" } " at the beginning of " { $snippet "seq" } "." }
 617 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 618 { $examples
 619 { $example "USING: prettyprint sequences ;" "{ 1 2 3 } 0 prefix ." "{ 0 1 2 3 }" }
 620 } ;
 621
 622 HELP: sum-lengths
 623 { $values { "seq" "a sequence of sequences" } { "n" integer } }
 624 { $description "Outputs the sum of the lengths of all sequences in " { $snippet "seq" } "." } ;
 625
 626 HELP: concat
 627 { $values { "seq" sequence } { "newseq" sequence } }
 628 { $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" } "." }
 629 { $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" } "." } ;
 630
 631 HELP: concat-as
 632 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" sequence } }
 633 { $description "Concatenates a sequence of sequences together into one sequence with the same type as " { $snippet "exemplar" } "." }
 634 { $errors "Throws an error if one of the sequences in " { $snippet "seq" } " contains elements not permitted in sequences of the same class as " { $snippet "exemplar" } "." } ;
 635
 636 HELP: join
 637 { $values { "seq" sequence } { "glue" sequence } { "newseq" sequence } }
 638 { $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" } "." }
 639 { $examples
 640     "Join a list of strings:"
 641     { $example "USING: sequences prettyprint ;"
 642         """{ "cat" "dog" "ant" } " " join ."""
 643         """"cat dog ant""""
 644     }
 645 }
 646 { $notes "If the " { $snippet "glue" } " sequence is empty, this word calls " { $link concat-as } "." }
 647 { $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" } "." } ;
 648
 649 HELP: join-as
 650 { $values { "seq" sequence } { "glue" sequence } { "exemplar" sequence } { "newseq" sequence } }
 651 { $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" } "." }
 652 { $notes "If the " { $snippet "glue" } " sequence is empty, this word calls " { $link concat-as } "." }
 653 { $examples
 654     "Join a list of strings as a string buffer:"
 655     { $example "USING: sequences prettyprint ;"
 656         """{ "a" "b" "c" } "1" SBUF" "join-as ."""
 657         """SBUF" a1b1c""""
 658     }
 659 }
 660 { $errors "Throws an error if one of the sequences in " { $snippet "seq" } " contains elements not permitted in sequences of the same class as " { $snippet "exemplar" } "." } ;
 661
 662 { join join-as concat concat-as } related-words
 663
 664 HELP: last
 665 { $values { "seq" sequence } { "elt" object } }
 666 { $description "Outputs the last element of a sequence." }
 667 { $errors "Throws an error if the sequence is empty." } ;
 668
 669 { pop pop* } related-words
 670
 671 HELP: pop*
 672 { $values { "seq" "a resizable mutable sequence" } }
 673 { $description "Removes the last element and shortens the sequence." }
 674 { $side-effects "seq" }
 675 { $errors "Throws an error if the sequence is empty." } ;
 676
 677 HELP: pop
 678 { $values { "seq" "a resizable mutable sequence" } { "elt" object } }
 679 { $description "Outputs the last element after removing it and shortening the sequence." }
 680 { $side-effects "seq" }
 681 { $errors "Throws an error if the sequence is empty." } ;
 682
 683 HELP: mismatch
 684 { $values { "seq1" sequence } { "seq2" sequence } { "i" "an index" } }
 685 { $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." } ;
 686
 687 HELP: flip
 688 { $values { "matrix" "a sequence of equal-length sequences" } { "newmatrix" "a sequence of equal-length sequences" } }
 689 { $description "Transposes the matrix; that is, rows become columns and columns become rows." }
 690 { $examples { $example "USING: prettyprint sequences ;" "{ { 1 2 3 } { 4 5 6 } } flip ." "{ { 1 4 } { 2 5 } { 3 6 } }" } } ;
 691
 692 HELP: exchange
 693 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 694 { $description "Exchanges the " { $snippet "m" } "th and " { $snippet "n" } "th elements of " { $snippet "seq" } "." } ;
 695
 696 HELP: reverse!
 697 { $values { "seq" "a mutable sequence" } }
 698 { $description "Reverses a sequence in-place and outputs that sequence." }
 699 { $side-effects "seq" } ;
 700
 701 HELP: padding
 702 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "quot" { $quotation ( ... seq1 seq2 -- ... newseq ) } } { "newseq" "a new sequence" } }
 703 { $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." } ;
 704
 705 HELP: pad-head
 706 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "padded" "a new sequence" } }
 707 { $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" } "." }
 708 { $examples { $example "USING: io sequences ;" "{ \"ab\" \"quux\" } [ 5 CHAR: - pad-head print ] each" "---ab\n-quux" } } ;
 709
 710 HELP: pad-tail
 711 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "padded" "a new sequence" } }
 712 { $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" } "." }
 713 { $examples { $example "USING: io sequences ;" "{ \"ab\" \"quux\" } [ 5 CHAR: - pad-tail print ] each" "ab---\nquux-" } } ;
 714
 715 HELP: sequence=
 716 { $values { "seq1" sequence } { "seq2" sequence } { "?" boolean } }
 717 { $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." } ;
 718
 719 HELP: reversed
 720 { $class-description "A virtual sequence which presents a reversed view of an underlying sequence. New instances can be created by calling " { $link <reversed> } "." } ;
 721
 722 HELP: reverse
 723 { $values { "seq" sequence } { "newseq" "a new sequence" } }
 724 { $description "Outputs a new sequence having the same elements as " { $snippet "seq" } " but in reverse order." } ;
 725
 726 { reverse <reversed> reverse! } related-words
 727
 728 HELP: <reversed>
 729 { $values { "seq" sequence } { "reversed" "a new sequence" } }
 730 { $description "Creates an instance of the " { $link reversed } " class." }
 731 { $see-also "virtual-sequences" } ;
 732
 733 HELP: slice-error
 734 { $values { "str" "a reason" } }
 735 { $description "Throws a " { $link slice-error } "." }
 736 { $error-description "Thrown by " { $link <slice> } " if one of the following invalid conditions holds:"
 737     { $list
 738         "The start index is negative"
 739         "The end index is greater than the length of the sequence"
 740         "The start index is greater than the end index"
 741     }
 742 } ;
 743
 744 HELP: slice
 745 { $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> } ". Convenience words are also provided for creating slices where one endpoint is the start or end of the sequence; see " { $link "sequences-slices" } " for a list."
 746 $nl
 747 "Slices are mutable if the underlying sequence is mutable, and mutating a slice changes the underlying sequence. However, slices cannot be resized after creation." } ;
 748
 749 HELP: check-slice
 750 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } }
 751 { $description "Ensures that " { $snippet "m" } " is less than or equal to " { $snippet "m" } ", and that both indices are within bounds for " { $snippet "seq" } "." }
 752 { $errors "Throws a " { $link slice-error } " if the preconditions are not met." } ;
 753
 754 HELP: collapse-slice
 755 { $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 } }
 756 { $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." }
 757 ;
 758
 759 HELP: <slice>
 760 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "slice" slice } }
 761 { $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" } "." }
 762 { $errors "Throws an error if " { $snippet "m" } " or " { $snippet "n" } " is out of bounds." }
 763 { $notes "Taking the slice of a slice outputs a slice of the underlying sequence, instead of a slice of a slice. This means that you cannot assume that the " { $snippet "from" } " and " { $snippet "to" } " slots of the resulting slice will be equal to the values you passed to " { $link <slice> } "." } ;
 764
 765 { <slice> subseq } related-words
 766
 767 HELP: repetition
 768 { $class-description "A virtual sequence consisting of " { $snippet "elt" } " repeated " { $snippet "len" } " times. Repetitions are created by calling " { $link <repetition> } "." } ;
 769
 770 HELP: <repetition>
 771 { $values { "len" "a non-negative integer" } { "elt" object } { "repetition" repetition } }
 772 { $description "Creates a new " { $link repetition } "." }
 773 { $examples
 774     { $example "USING: arrays prettyprint sequences ;" "10 \"X\" <repetition> >array ." "{ \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" }" }
 775     { $example "USING: prettyprint sequences ;" "10 \"X\" <repetition> concat ." "\"XXXXXXXXXX\"" }
 776 } ;
 777 HELP: copy
 778 { $values { "src" sequence } { "i" "an index in " { $snippet "dst" } } { "dst" "a mutable sequence" } }
 779 { $description "Copies all elements of " { $snippet "src" } " to " { $snippet "dst" } ", with destination indices starting from " { $snippet "i" } ". Grows " { $snippet "dst" } " first if necessary." }
 780 { $side-effects "dst" }
 781 { $errors "An error is thrown if " { $snippet "dst" } " is not resizable, and not large enough to hold the copied elements." } ;
 782
 783 HELP: push-all
 784 { $values { "src" sequence } { "dst" "a resizable mutable sequence" } }
 785 { $description "Appends " { $snippet "src" } " to the end of " { $snippet "dst" } "." }
 786 { $side-effects "dst" }
 787 { $errors "Throws an error if " { $snippet "src" } " contains elements not permitted in " { $snippet "dst" } "." } ;
 788
 789 HELP: append
 790 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
 791 { $description "Outputs a new sequence of the same type as " { $snippet "seq1" } " consisting of the elements of " { $snippet "seq1" } " followed by " { $snippet "seq2" } "." }
 792 { $errors "Throws an error if " { $snippet "seq2" } " contains elements not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 793 { $examples
 794     { $example "USING: prettyprint sequences ;"
 795         "{ 1 2 } B{ 3 4 } append ."
 796         "{ 1 2 3 4 }"
 797     }
 798     { $example "USING: prettyprint sequences strings ;"
 799         "\"go\" \"ing\" append ."
 800         "\"going\""
 801     }
 802 } ;
 803
 804 HELP: append-as
 805 { $values { "seq1" sequence } { "seq2" sequence } { "exemplar" sequence } { "newseq" sequence } }
 806 { $description "Outputs a new sequence of the same type as " { $snippet "exemplar" } " consisting of the elements of " { $snippet "seq1" } " followed by " { $snippet "seq2" } "." }
 807 { $errors "Throws an error if " { $snippet "seq1" } " or " { $snippet "seq2" } " contain elements not permitted in sequences of the same class as " { $snippet "exemplar" } "." }
 808 { $examples
 809     { $example "USING: prettyprint sequences ;"
 810         "{ 1 2 } B{ 3 4 } B{ } append-as ."
 811         "B{ 1 2 3 4 }"
 812     }
 813     { $example "USING: prettyprint sequences strings ;"
 814         "\"go\" \"ing\" SBUF\" \" append-as ."
 815         "SBUF\" going\""
 816     }
 817 } ;
 818
 819 { append append-as } related-words
 820
 821 HELP: prepend
 822 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
 823 { $description "Outputs a new sequence of the same type as " { $snippet "seq1" } " consisting of the elements of " { $snippet "seq2" } " followed by " { $snippet "seq1" } "." }
 824 { $errors "Throws an error if " { $snippet "seq2" } " contains elements not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 825 { $examples { $example "USING: prettyprint sequences ;"
 826         "{ 1 2 } B{ 3 4 } prepend ."
 827         "{ 3 4 1 2 }"
 828     }
 829     { $example "USING: prettyprint sequences strings ;"
 830         "\"go\" \"car\" prepend ."
 831         "\"cargo\""
 832     }
 833 } ;
 834
 835 HELP: prepend-as
 836 { $values { "seq1" sequence } { "seq2" sequence } { "exemplar" sequence } { "newseq" sequence } }
 837 { $description "Outputs a new sequence of the same type as " { $snippet "exemplar" } " consisting of the elements of " { $snippet "seq2" } " followed by " { $snippet "seq1" } "." }
 838 { $errors "Throws an error if " { $snippet "seq1" } " or " { $snippet "seq2" } " contain elements not permitted in sequences of the same class as " { $snippet "exemplar" } "." }
 839 { $examples
 840     { $example "USING: prettyprint sequences ;"
 841         "{ 3 4 } B{ 1 2 } B{ } prepend-as ."
 842         "B{ 1 2 3 4 }"
 843     }
 844     { $example "USING: prettyprint sequences strings ;"
 845         "\"ing\" \"go\" SBUF\" \" prepend-as ."
 846         "SBUF\" going\""
 847     }
 848 } ;
 849
 850 { prepend prepend-as } related-words
 851
 852 HELP: 3append
 853 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
 854 { $description "Outputs a new sequence consisting of the elements of " { $snippet "seq1" } ", " { $snippet "seq2" } " and " { $snippet "seq3" } " in turn." }
 855 { $errors "Throws an error if " { $snippet "seq2" } " or " { $snippet "seq3" } " contain elements not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 856 { $examples
 857     { $example "USING: prettyprint sequences ;"
 858         "\"a\" \"b\" \"c\" 3append ."
 859         "\"abc\""
 860     }
 861 } ;
 862
 863 HELP: 3append-as
 864 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "exemplar" sequence } { "newseq" sequence } }
 865 { $description "Outputs a new sequence consisting of the elements of " { $snippet "seq1" } ", " { $snippet "seq2" } " and " { $snippet "seq3" } " in turn of the same type as " { $snippet "exemplar" } "." }
 866 { $errors "Throws an error if " { $snippet "seq1" } ", " { $snippet "seq2" } ", or " { $snippet "seq3" } " contain elements not permitted in sequences of the same class as " { $snippet "exemplar" } "." }
 867 { $examples
 868     { $example "USING: prettyprint sequences ;"
 869         "\"a\" \"b\" \"c\" SBUF\" \" 3append-as ."
 870         "SBUF\" abc\""
 871     }
 872 } ;
 873
 874 { 3append 3append-as } related-words
 875
 876 HELP: surround
 877 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
 878 { $description "Outputs a new sequence with " { $snippet "seq1" } " inserted between " { $snippet "seq2" } " and " { $snippet "seq3" } "." }
 879 { $examples
 880     { $example "USING: sequences prettyprint ;"
 881                "\"sssssh\" \"(\" \")\" surround ."
 882                "\"(sssssh)\""
 883     }
 884 } ;
 885
 886 HELP: glue
 887 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
 888 { $description "Outputs a new sequence with " { $snippet "seq3" } " inserted between " { $snippet "seq1" } " and " { $snippet "seq2" } "." }
 889 { $examples
 890     { $example "USING: sequences prettyprint ;"
 891                "\"a\" \"b\" \",\" glue ."
 892                "\"a,b\""
 893     }
 894 } ;
 895
 896 HELP: subseq
 897 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "subseq" "a new sequence" } }
 898 { $description "Outputs a new sequence consisting of all elements starting from and including " { $snippet "from" } ", and up to but not including " { $snippet "to" } "." }
 899 { $errors "Throws an error if " { $snippet "from" } " or " { $snippet "to" } " is out of bounds." } ;
 900
 901 HELP: clone-like
 902 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" "a new sequence" } }
 903 { $description "Outputs a newly-allocated sequence with the same elements as " { $snippet "seq" } " but of the same type as " { $snippet "exemplar" } "." }
 904 { $notes "Unlike " { $link like } ", this word always creates a new sequence which never shares storage with the original." } ;
 905
 906 HELP: head-slice
 907 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 908 { $description "Outputs a virtual sequence sharing storage with the first " { $snippet "n" } " elements of the input sequence." }
 909 { $errors "Throws an error if the index is out of bounds." } ;
 910
 911 HELP: tail-slice
 912 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 913 { $description "Outputs a virtual sequence sharing storage with all elements from the " { $snippet "n" } "th index until the end of the input sequence." }
 914 { $errors "Throws an error if the index is out of bounds." } ;
 915
 916 HELP: but-last-slice
 917 { $values { "seq" sequence } { "slice" "a slice" } }
 918 { $description "Outputs a virtual sequence sharing storage with all but the last element of the input sequence." }
 919 { $errors "Throws an error on an empty sequence." } ;
 920
 921 HELP: rest-slice
 922 { $values { "seq" sequence } { "slice" "a slice" } }
 923 { $description "Outputs a virtual sequence sharing storage with all elements from the 1st index until the end of the input sequence." }
 924 { $notes "Equivalent to " { $snippet "1 tail" } }
 925 { $errors "Throws an error on an empty sequence." } ;
 926
 927 HELP: head-slice*
 928 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 929 { $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." }
 930 { $errors "Throws an error if the index is out of bounds." } ;
 931
 932 HELP: tail-slice*
 933 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 934 { $description "Outputs a virtual sequence sharing storage with the last " { $snippet "n" } " elements of the input sequence." }
 935 { $errors "Throws an error if the index is out of bounds." } ;
 936
 937 HELP: head
 938 { $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
 939 { $description "Outputs a new sequence consisting of the first " { $snippet "n" } " elements of the input sequence." }
 940 { $examples
 941     { $example "USING: sequences prettyprint ;"
 942         "{ 1 2 3 4 5 6 7 } 2 head ."
 943         "{ 1 2 }"
 944     }
 945 }
 946 { $errors "Throws an error if the index is out of bounds." } ;
 947
 948 HELP: tail
 949 { $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
 950 { $description "Outputs a new sequence consisting of the input sequence with the first " { $snippet "n" } " items removed." }
 951 { $examples
 952     { $example "USING: sequences prettyprint ;"
 953         "{ 1 2 3 4 5 6 7 } 2 tail ."
 954         "{ 3 4 5 6 7 }"
 955     }
 956 }
 957 { $errors "Throws an error if the index is out of bounds." } ;
 958
 959 HELP: but-last
 960 { $values { "seq" sequence } { "headseq" "a new sequence" } }
 961 { $description "Outputs a new sequence consisting of the input sequence with the last item removed." }
 962 { $errors "Throws an error on an empty sequence." } ;
 963
 964 HELP: rest
 965 { $values { "seq" sequence } { "tailseq" "a new sequence" } }
 966 { $description "Outputs a new sequence consisting of the input sequence with the first item removed." }
 967 { $errors "Throws an error on an empty sequence." } ;
 968
 969 HELP: head*
 970 { $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
 971 { $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." }
 972 { $examples
 973     { $example "USING: sequences prettyprint ;"
 974         "{ 1 2 3 4 5 6 7 } 2 head* ."
 975         "{ 1 2 3 4 5 }"
 976     }
 977 }
 978 { $errors "Throws an error if the index is out of bounds." } ;
 979
 980 HELP: tail*
 981 { $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
 982 { $description "Outputs a new sequence consisting of the last " { $snippet "n" } " elements of the input sequence." }
 983 { $examples
 984     { $example "USING: sequences prettyprint ;"
 985         "{ 1 2 3 4 5 6 7 } 2 tail* ."
 986         "{ 6 7 }"
 987     }
 988 }
 989 { $errors "Throws an error if the index is out of bounds." } ;
 990
 991 HELP: shorter?
 992 { $values { "seq1" sequence } { "seq2" sequence } { "?" boolean } }
 993 { $description "Tests if the length of " { $snippet "seq1" } " is smaller than the length of " { $snippet "seq2" } "." } ;
 994
 995 HELP: head?
 996 { $values { "seq" sequence } { "begin" sequence } { "?" boolean } }
 997 { $description "Tests if " { $snippet "seq" } " starts with " { $snippet "begin" } ". If " { $snippet "begin" } " is longer than " { $snippet "seq" } ", this word outputs " { $link f } "." }
 998 { $examples
 999   { $example
1000     "USING: prettyprint sequences ;"
1001     "{ \"accept\" \"adept\" \"advance\" \"advice\" \"affect\" } [ \"ad\" head? ] filter ."
1002     "{ \"adept\" \"advance\" \"advice\" }"
1003   }
1004 } ;
1005
1006 HELP: tail?
1007 { $values { "seq" sequence } { "end" sequence } { "?" boolean } }
1008 { $description "Tests if " { $snippet "seq" } " ends with " { $snippet "end" } ". If " { $snippet "end" } " is longer than " { $snippet "seq" } ", this word outputs " { $link f } "." } ;
1009
1010 { remove remove-nth remove-eq remove-eq! remove! remove-nth! } related-words
1011
1012 HELP: cut-slice
1013 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before-slice" sequence } { "after-slice" "a slice" } }
1014 { $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." }
1015 { $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." } ;
1016
1017 HELP: cut
1018 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
1019 { $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" } "." }
1020 { $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." } ;
1021
1022 HELP: cut*
1023 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
1024 { $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" } "." } ;
1025
1026 HELP: start*
1027 { $values { "subseq" sequence } { "seq" sequence } { "n" "a start index" } { "i" "a start index" } }
1028 { $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 } "." } ;
1029
1030 HELP: start
1031 { $values { "subseq" sequence } { "seq" sequence } { "i" "a start index" } }
1032 { $description "Outputs the start index of the first contiguous subsequence equal to " { $snippet "subseq" } ", or " { $link f } " if no matching subsequence is found." } ;
1033
1034 HELP: subseq?
1035 { $values { "subseq" sequence } { "seq" sequence } { "?" boolean } }
1036 { $description "Tests if " { $snippet "seq" } " contains the elements of " { $snippet "subseq" } " as a contiguous subsequence." } ;
1037
1038 HELP: drop-prefix
1039 { $values { "seq1" sequence } { "seq2" sequence } { "slice1" "a slice" } { "slice2" "a slice" } }
1040 { $description "Outputs a pair of virtual sequences with the common prefix of " { $snippet "seq1" } " and " { $snippet "seq2" } " removed." } ;
1041
1042 HELP: unclip
1043 { $values { "seq" sequence } { "rest" sequence } { "first" object } }
1044 { $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." }
1045 { $examples
1046     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } unclip suffix ." "{ 2 3 1 }" }
1047 } ;
1048
1049 HELP: unclip-slice
1050 { $values { "seq" sequence } { "rest-slice" slice } { "first" object } }
1051 { $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." }
1052 { $examples { $example "USING: math.order prettyprint sequences ;" "{ 3 -1 -10 5 7 } unclip-slice [ min ] reduce ." "-10" } } ;
1053
1054 HELP: unclip-last
1055 { $values { "seq" sequence } { "butlast" sequence } { "last" object } }
1056 { $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." }
1057 { $examples
1058     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } unclip-last prefix ." "{ 3 1 2 }" }
1059 } ;
1060
1061 HELP: unclip-last-slice
1062 { $values { "seq" sequence } { "butlast-slice" slice } { "last" object } }
1063 { $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." } ;
1064
1065 HELP: sum
1066 { $values { "seq" "a sequence of numbers" } { "n" number } }
1067 { $description "Outputs the sum of all elements of " { $snippet "seq" } ". Outputs zero given an empty sequence." } ;
1068
1069 HELP: product
1070 { $values { "seq" "a sequence of numbers" } { "n" number } }
1071 { $description "Outputs the product of all elements of " { $snippet "seq" } ". Outputs one given an empty sequence." } ;
1072
1073 HELP: infimum
1074 { $values { "seq" "a sequence of real numbers" } { "n" number } }
1075 { $description "Outputs the least element of " { $snippet "seq" } "." }
1076 { $errors "Throws an error if the sequence is empty." } ;
1077
1078 HELP: supremum
1079 { $values { "seq" "a sequence of real numbers" } { "n" number } }
1080 { $description "Outputs the greatest element of " { $snippet "seq" } "." }
1081 { $errors "Throws an error if the sequence is empty." } ;
1082
1083 { min max supremum infimum } related-words
1084
1085 HELP: produce
1086 { $values { "pred" { $quotation ( ..a -- ..b ? ) } } { "quot" { $quotation ( ..b -- ..a obj ) } } { "seq" sequence } }
1087 { $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." }
1088 { $examples
1089     "The following example divides a number by two until we reach zero, and accumulates intermediate results:"
1090     { $example "USING: kernel math prettyprint sequences ;" "1337 [ dup 0 > ] [ 2/ dup ] produce nip ." "{ 668 334 167 83 41 20 10 5 2 1 0 }" }
1091     "The following example collects random numbers as long as they are greater than 1:"
1092     { $unchecked-example "USING: kernel prettyprint random sequences ;" "[ 10 random dup 1 > ] [ ] produce nip ." "{ 8 2 2 9 }" }
1093 } ;
1094
1095 HELP: produce-as
1096 { $values { "pred" { $quotation ( ..a -- ..b ? ) } } { "quot" { $quotation ( ..b -- ..a obj ) } } { "exemplar" sequence } { "seq" sequence } }
1097 { $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 of type " { $snippet "exemplar" } " at the end." }
1098 { $examples "See " { $link produce } " for examples." } ;
1099
1100 HELP: map-sum
1101 { $values { "seq" sequence } { "quot" quotation } { "n" number } }
1102 { $description "Like " { $snippet "map sum" } ", but without creating an intermediate sequence." }
1103 { $examples
1104     { $example
1105         "USING: math math.ranges sequences prettyprint ;"
1106         "100 [1,b] [ sq ] map-sum ."
1107         "338350"
1108     }
1109 } ;
1110
1111 HELP: count
1112 { $values { "seq" sequence } { "quot" quotation } { "n" integer } }
1113 { $description "Efficiently returns the number of elements that the predicate quotation matches." }
1114 { $examples
1115     { $example
1116         "USING: math math.ranges sequences prettyprint ;"
1117         "100 [1,b] [ even? ] count ."
1118         "50"
1119     }
1120 } ;
1121
1122 HELP: selector
1123 { $values
1124      { "quot" { $quotation ( ... elt -- ... ? ) } }
1125      { "selector" { $quotation ( ... elt -- ... ) } } { "accum" vector } }
1126 { $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 collector if the test yields true. The collector is left on the stack for convenience." }
1127 { $examples
1128     { $example "! Find all the even numbers:" "USING: prettyprint sequences math kernel ;"
1129                "10 iota [ even? ] selector [ each ] dip ."
1130                "V{ 0 2 4 6 8 }"
1131     }
1132 }
1133 { $notes "Used to implement the " { $link filter } " word. Compare this word with " { $link collector } ", which is an unfiltering version." } ;
1134
1135 HELP: trim-head
1136 { $values
1137      { "seq" sequence } { "quot" quotation }
1138      { "newseq" sequence } }
1139 { $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." }
1140 { $examples
1141     { $example "USING: prettyprint math sequences ;"
1142                "{ 0 0 1 2 3 0 0 } [ zero? ] trim-head ."
1143                "{ 1 2 3 0 0 }"
1144     }
1145 } ;
1146
1147 HELP: trim-head-slice
1148 { $values
1149      { "seq" sequence } { "quot" quotation }
1150      { "slice" slice } }
1151 { $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." }
1152 { $examples
1153     { $example "USING: prettyprint math sequences ;"
1154                "{ 0 0 1 2 3 0 0 } [ zero? ] trim-head-slice ."
1155                "T{ slice { from 2 } { to 7 } { seq { 0 0 1 2 3 0 0 } } }"
1156     }
1157 } ;
1158
1159 HELP: trim-tail
1160 { $values
1161      { "seq" sequence } { "quot" quotation }
1162      { "newseq" sequence } }
1163 { $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." }
1164 { $examples
1165     { $example "USING: prettyprint math sequences ;"
1166                "{ 0 0 1 2 3 0 0 } [ zero? ] trim-tail ."
1167                "{ 0 0 1 2 3 }"
1168     }
1169 } ;
1170
1171 HELP: trim-tail-slice
1172 { $values
1173      { "seq" sequence } { "quot" quotation }
1174      { "slice" slice } }
1175 { $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." }
1176 { $examples
1177     { $example "USING: prettyprint math sequences ;"
1178                "{ 0 0 1 2 3 0 0 } [ zero? ] trim-tail-slice ."
1179                "T{ slice { from 0 } { to 5 } { seq { 0 0 1 2 3 0 0 } } }"
1180     }
1181 } ;
1182
1183 HELP: trim
1184 { $values
1185      { "seq" sequence } { "quot" quotation }
1186      { "newseq" sequence } }
1187 { $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." }
1188 { $examples
1189     { $example "USING: prettyprint math sequences ;"
1190                "{ 0 0 1 2 3 0 0 } [ zero? ] trim ."
1191                "{ 1 2 3 }"
1192     }
1193 } ;
1194
1195 HELP: trim-slice
1196 { $values
1197      { "seq" sequence } { "quot" quotation }
1198      { "slice" slice } }
1199 { $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." }
1200 { $examples
1201     { $example "USING: prettyprint math sequences ;"
1202                "{ 0 0 1 2 3 0 0 } [ zero? ] trim-slice ."
1203                "T{ slice { from 2 } { to 5 } { seq { 0 0 1 2 3 0 0 } } }"
1204     }
1205 } ;
1206
1207 { trim trim-slice trim-head trim-head-slice trim-tail trim-tail-slice } related-words
1208
1209 HELP: sift
1210 { $values
1211      { "seq" sequence }
1212      { "newseq" sequence } }
1213  { $description "Outputs a new sequence with all instance of " { $link f } " removed." }
1214  { $examples
1215     { $example "USING: prettyprint sequences ;"
1216         "{ \"a\" 3 { } f } sift ."
1217         "{ \"a\" 3 { } }"
1218     }
1219 } ;
1220
1221 HELP: harvest
1222 { $values
1223      { "seq" sequence }
1224      { "newseq" sequence } }
1225 { $description "Outputs a new sequence with all empty sequences removed." }
1226 { $examples
1227     { $example "USING: prettyprint sequences ;"
1228                "{ { } { 2 3 } { 5 } { } } harvest ."
1229                "{ { 2 3 } { 5 } }"
1230     }
1231 } ;
1232
1233 { filter filter! sift harvest } related-words
1234
1235 HELP: set-first
1236 { $values
1237      { "first" object } { "seq" sequence } }
1238 { $description "Sets the first element of a sequence." }
1239 { $examples
1240     { $example "USING: prettyprint kernel sequences ;"
1241         "{ 1 2 3 4 } 5 over set-first ."
1242         "{ 5 2 3 4 }"
1243     }
1244 } ;
1245
1246 HELP: set-second
1247 { $values
1248      { "second" object } { "seq" sequence } }
1249 { $description "Sets the second element of a sequence." }
1250 { $examples
1251     { $example "USING: prettyprint kernel sequences ;"
1252         "{ 1 2 3 4 } 5 over set-second ."
1253         "{ 1 5 3 4 }"
1254     }
1255 } ;
1256
1257 HELP: set-third
1258 { $values
1259      { "third" object } { "seq" sequence } }
1260 { $description "Sets the third element of a sequence." }
1261 { $examples
1262     { $example "USING: prettyprint kernel sequences ;"
1263         "{ 1 2 3 4 } 5 over set-third ."
1264         "{ 1 2 5 4 }"
1265     }
1266 } ;
1267
1268 HELP: set-fourth
1269 { $values
1270      { "fourth" object } { "seq" sequence } }
1271 { $description "Sets the fourth element of a sequence." }
1272 { $examples
1273     { $example "USING: prettyprint kernel sequences ;"
1274         "{ 1 2 3 4 } 5 over set-fourth ."
1275         "{ 1 2 3 5 }"
1276     }
1277 } ;
1278
1279 { set-first set-second set-third set-fourth } related-words
1280
1281 HELP: replicate
1282 { $values
1283      { "len" integer } { "quot" { $quotation ( ... -- ... newelt ) } }
1284      { "newseq" sequence } }
1285      { $description "Calls the quotation " { $snippet "len" } " times, collecting results into a new array." }
1286 { $examples
1287     { $unchecked-example "USING: kernel prettyprint random sequences ;"
1288         "5 [ 100 random ] replicate ."
1289         "{ 52 10 45 81 30 }"
1290     }
1291 } ;
1292
1293 HELP: replicate-as
1294 { $values
1295      { "len" integer } { "quot" { $quotation ( ... -- ... newelt ) } } { "exemplar" sequence }
1296      { "newseq" sequence } }
1297  { $description "Calls the quotation " { $snippet "len" } " times, collecting results into a new sequence of the same type as the exemplar sequence." }
1298 { $examples
1299     { $unchecked-example "USING: prettyprint kernel sequences ;"
1300         "5 [ 100 random ] B{ } replicate-as ."
1301         "B{ 44 8 2 33 18 }"
1302     }
1303 } ;
1304
1305 { replicate replicate-as } related-words
1306
1307 HELP: partition
1308 { $values
1309      { "seq" sequence } { "quot" quotation }
1310      { "trueseq" sequence } { "falseseq" sequence } }
1311      { $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" } "." }
1312 { $examples
1313     { $example "USING: prettyprint kernel math sequences ;"
1314         "{ 1 2 3 4 5 } [ even? ] partition [ . ] bi@"
1315         "{ 2 4 }\n{ 1 3 5 }"
1316     }
1317 } ;
1318
1319 HELP: virtual-exemplar
1320 { $values
1321      { "seq" sequence }
1322      { "seq'" sequence } }
1323 { $description "Part of the virtual sequence protocol, this word is used to return an exemplar of the underlying storage. This is used in words like " { $link new-sequence } "." } ;
1324
1325 HELP: virtual@
1326 { $values
1327      { "n" integer } { "seq" sequence }
1328      { "n'" integer } { "seq'" sequence } }
1329 { $description "Part of the sequence protocol, this word translates the input index " { $snippet "n" } " into an index and the underlying storage this index points into." } ;
1330
1331 HELP: 2map-reduce
1332 { $values
1333      { "seq1" sequence } { "seq2" sequence } { "map-quot" { $quotation ( ..a elt1 elt2 -- ..b intermediate ) } } { "reduce-quot" { $quotation ( ..b prev intermediate -- ..a next ) } }
1334      { "result" object } }
1335  { $description "Calls " { $snippet "map-quot" } " on each pair of elements from " { $snippet "seq1" } " and " { $snippet "seq2" } " and combines the results using " { $snippet "reduce-quot" } " in the same manner as " { $link reduce } ", except that there is no identity element, and the sequence must have a length of at least 1." }
1336 { $errors "Throws an error if the sequence is empty." }
1337 { $examples { $example "USING: sequences prettyprint math ;"
1338     "{ 10 30 50 } { 200 400 600 } [ + ] [ + ] 2map-reduce ."
1339     "1290"
1340 } } ;
1341
1342 HELP: 2selector
1343 { $values
1344      { "quot" quotation }
1345      { "selector" quotation } { "accum1" vector } { "accum2" vector } }
1346 { $description "Creates two new vectors to accumulate values based on a predicate. The first vector accumulates values for which the predicate yields true; the second for false." } ;
1347
1348 HELP: collector
1349 { $values
1350      { "quot" quotation }
1351      { "quot'" quotation } { "vec" vector } }
1352 { $description "Creates a new quotation that pushes its result to a vector and outputs that vector on the stack." }
1353 { $examples { $example "USING: sequences prettyprint kernel math ;"
1354     "{ 1 2 } [ 30 + ] collector [ each ] dip ."
1355     "V{ 31 32 }"
1356 } } ;
1357
1358 HELP: binary-reduce
1359 { $values
1360      { "seq" sequence } { "start" integer } { "quot" { $quotation ( elt1 elt2 -- newelt ) } }
1361      { "value" object } }
1362 { $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 } "." }
1363 { $examples "Computing factorial:"
1364     { $example "USING: prettyprint sequences math ;"
1365     "40 iota rest-slice 1 [ * ] binary-reduce ."
1366     "20397882081197443358640281739902897356800000000" }
1367 } ;
1368
1369 HELP: follow
1370 { $values
1371      { "obj" object } { "quot" { $quotation ( ... prev -- ... result/f ) } }
1372      { "seq" sequence } }
1373 { $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 recursively. Objects yielded by the quotation are added to the output sequence until the quotation yields " { $link f } ", at which point the recursion terminates." }
1374 { $examples "Get random numbers until zero is reached:"
1375     { $unchecked-example
1376     "USING: random sequences prettyprint math ;"
1377     "100 [ random [ f ] when-zero ] follow ."
1378     "{ 100 86 34 32 24 11 7 2 }"
1379 } } ;
1380
1381 HELP: halves
1382 { $values
1383      { "seq" sequence }
1384      { "first-slice" slice } { "second-slice" slice } }
1385 { $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." }
1386 { $examples { $example "USING: arrays sequences prettyprint kernel ;"
1387     "{ 1 2 3 4 5 } halves [ >array . ] bi@"
1388     "{ 1 2 }\n{ 3 4 5 }"
1389 } } ;
1390
1391 HELP: indices
1392 { $values
1393      { "obj" object } { "seq" sequence }
1394      { "indices" sequence } }
1395 { $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." }
1396 { $examples { $example "USING: sequences prettyprint ;"
1397     "2 { 2 4 2 6 2 8 2 10 } indices ."
1398     "V{ 0 2 4 6 }"
1399 } } ;
1400
1401 HELP: insert-nth
1402 { $values
1403      { "elt" object } { "n" integer } { "seq" sequence }
1404      { "seq'" sequence } }
1405 { $description "Creates a new sequence where the " { $snippet "n" } "th index is set to the input object." }
1406 { $examples { $example "USING: prettyprint sequences ;"
1407     "40 3 { 10 20 30 50 } insert-nth ."
1408     "{ 10 20 30 40 50 }"
1409 } } ;
1410
1411 HELP: map-reduce
1412 { $values
1413      { "seq" sequence } { "map-quot" { $quotation ( ..a elt -- ..b intermediate ) } } { "reduce-quot" { $quotation ( ..b prev intermediate -- ..a next ) } }
1414      { "result" object } }
1415 { $description "Calls " { $snippet "map-quot" } " on each element and combines the results using " { $snippet "reduce-quot" } " in the same manner as " { $link reduce } ", except that there is no identity element, and the sequence must have a length of at least 1." }
1416 { $errors "Throws an error if the sequence is empty." }
1417 { $examples { $example "USING: sequences prettyprint math ;"
1418     "{ 1 3 5 } [ sq ] [ + ] map-reduce ."
1419     "35"
1420 } } ;
1421
1422 HELP: new-like
1423 { $values
1424      { "len" integer } { "exemplar" "an exemplar sequence" } { "quot" quotation }
1425      { "seq" sequence } }
1426 { $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." } ;
1427
1428 HELP: push-either
1429 { $values
1430      { "elt" object } { "quot" quotation } { "accum1" vector } { "accum2" vector } }
1431 { $description "Pushes the input object onto one of the accumulators; the first if the quotation yields true, the second if false." } ;
1432
1433 HELP: sequence-hashcode
1434 { $values
1435      { "n" integer } { "seq" sequence }
1436      { "x" integer } }
1437 { $description "Iterates over a sequence, computes a hashcode with " { $link hashcode* } " for each element, and combines them using " { $link sequence-hashcode-step } "." } ;
1438
1439 HELP: sequence-hashcode-step
1440 { $values
1441      { "oldhash" integer } { "newpart" integer }
1442      { "newhash" integer } }
1443 { $description "An implementation word that computes a running hashcode of a sequence using some bit-twiddling. The resulting hashcode is always a fixnum." } ;
1444
1445 HELP: short
1446 { $values
1447      { "seq" sequence } { "n" integer } { "n'" integer } }
1448 { $description "Returns the input sequence and its length or " { $snippet "n" } ", whichever is less." }
1449 { $examples { $example "USING: sequences kernel prettyprint ;"
1450     "\"abcd\" 3 short [ . ] bi@"
1451     "\"abcd\"\n3"
1452 } } ;
1453
1454 HELP: shorten
1455 { $values
1456      { "n" integer } { "seq" sequence } }
1457 { $description "Shortens a " { $link "growable" } " sequence to be " { $snippet "n" } " elements long." }
1458 { $examples { $example "USING: sequences prettyprint kernel ;"
1459     "V{ 1 2 3 4 5 } 3 over shorten ."
1460     "V{ 1 2 3 }"
1461 } } ;
1462
1463 HELP: iota
1464 { $values { "n" integer } { "iota" iota } }
1465 { $description "Creates an immutable virtual sequence containing the integers from 0 to " { $snippet "n-1" } "." }
1466 { $examples
1467   { $example
1468     "USING: math sequences prettyprint ;"
1469     "3 iota [ sq ] map ."
1470     "{ 0 1 4 }"
1471   }
1472 } ;
1473
1474 HELP: assert-sequence=
1475 { $values
1476     { "a" sequence } { "b" sequence }
1477 }
1478 { $description "Throws an error if all the elements of two sequences, taken pairwise, are not equal." }
1479 { $notes "The sequences need not be of the same type." }
1480 { $examples
1481   { $code
1482     "USING: prettyprint sequences ;"
1483     "{ 1 2 3 } V{ 1 2 3 } assert-sequence="
1484   }
1485 } ;
1486
1487 HELP: cartesian-each
1488 { $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ) } } }
1489 { $description "Applies the quotation to every possible pairing of elements from the two sequences." } ;
1490
1491 HELP: cartesian-map
1492 { $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... newelt ) } } { "newseq" "a new sequence of sequences" } }
1493 { $description "Applies the quotation to every possible pairing of elements from the two sequences, collecting results into a new sequence of sequences." } ;
1494
1495 HELP: cartesian-product
1496 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" "a new sequence of sequences of pairs" } }
1497 { $description "Outputs a sequence of all possible pairings of elements from the two sequences." }
1498 { $examples
1499     { $example
1500         "USING: prettyprint sequences ;"
1501         "{ 1 2 } { 3 4 } cartesian-product ."
1502         "{ { { 1 3 } { 1 4 } } { { 2 3 } { 2 4 } } }"
1503     }
1504 } ;
1505
1506 ARTICLE: "sequences-unsafe" "Unsafe sequence operations"
1507 "The " { $link nth-unsafe } " and " { $link set-nth-unsafe } " sequence protocol bypasses bounds checks for increased performance."
1508 $nl
1509 "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."
1510 $nl
1511 "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."
1512 $nl
1513 "The justification for this is that the VM should not crash if a resizable sequence is resized during the execution of an iteration combinator."
1514 $nl
1515 "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 } "." ;
1516
1517 ARTICLE: "sequence-protocol" "Sequence protocol"
1518 "All sequences must be instances of a mixin class:"
1519 { $subsections sequence sequence? }
1520 "All sequences must know their length:"
1521 { $subsections length }
1522 "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:"
1523 { $subsections nth nth-unsafe }
1524 "Note that sequences are always indexed starting from zero."
1525 $nl
1526 "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:"
1527 { $subsections set-nth set-nth-unsafe }
1528 "If your sequence is immutable, then you must implement either " { $link set-nth } " or " { $link set-nth-unsafe } " to simply call " { $link immutable } " to signal an error."
1529 $nl
1530 "The following two generic words are optional, as not all sequences are resizable:"
1531 { $subsections set-length lengthen }
1532 "An optional generic word for creating sequences of the same class as a given sequence:"
1533 { $subsections like }
1534 "Optional generic words for optimization purposes:"
1535 { $subsections new-sequence new-resizable }
1536 { $see-also "sequences-unsafe" } ;
1537
1538 ARTICLE: "virtual-sequences-protocol" "Virtual sequence protocol"
1539 "Virtual sequences must know their length:"
1540 { $subsections length }
1541 "An exemplar of the underlying storage:"
1542 { $subsections virtual-exemplar }
1543 "The index and the underlying storage where the value is located:"
1544 { $subsections virtual@ } ;
1545
1546 ARTICLE: "virtual-sequences" "Virtual sequences"
1547 "A virtual sequence is an implementation of the " { $link "sequence-protocol" } " which does not store its own elements, and instead computes them, either from scratch or by retrieving them from another sequence."
1548 $nl
1549 "Implementations include the following:"
1550 { $subsections reversed slice }
1551 "Virtual sequences can be implemented with the " { $link "virtual-sequences-protocol" } ", by translating an index in the virtual sequence into an index in another sequence."
1552 { $see-also "sequences-integers" } ;
1553
1554 ARTICLE: "sequences-integers" "Counted loops"
1555 "A virtual sequence is defined for iterating over integers from zero."
1556 { $subsection iota }
1557 "For example, calling " { $link iota } " on the integer 3 produces a sequence containing the elements 0, 1, and 2. This is very useful for performing counted loops using words such as " { $link each } ":"
1558 { $example "USING: sequences prettyprint ; 3 iota [ . ] each" "0\n1\n2" }
1559 "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 } "."
1560 $nl
1561 "Combinators that produce new sequences, such as " { $link map } ", will output an array if the input is an instance of " { $link iota } "."
1562 $nl
1563 "More elaborate counted loops can be performed with " { $link "math.ranges" } "." ;
1564
1565 ARTICLE: "sequences-if" "Control flow with sequences"
1566 "To reduce the boilerplate of checking if a sequence is empty, several combinators are provided."
1567 $nl
1568 "Checking if a sequence is empty:"
1569 { $subsections if-empty when-empty unless-empty } ;
1570
1571 ARTICLE: "sequences-access" "Accessing sequence elements"
1572 "Element access by index, without raising exceptions:"
1573 { $subsections ?nth }
1574 "Concise way of extracting one of the first four elements:"
1575 { $subsections first second third fourth ?first ?second }
1576 "Extracting the last element:"
1577 { $subsections last ?last }
1578 "Unpacking sequences:"
1579 { $subsections first2 first3 first4 }
1580 { $see-also nth } ;
1581
1582 ARTICLE: "sequences-add-remove" "Adding and removing sequence elements"
1583 "Adding elements:"
1584 { $subsections prefix suffix insert-nth }
1585 "Removing elements:"
1586 { $subsections remove remove-eq remove-nth } ;
1587
1588 ARTICLE: "sequences-reshape" "Reshaping sequences"
1589 "A " { $emphasis "repetition" } " is a virtual sequence consisting of a single element repeated multiple times:"
1590 { $subsections repetition <repetition> }
1591 "Reversing a sequence:"
1592 { $subsections reverse }
1593 "A " { $emphasis "reversal" } " presents a reversed view of an underlying sequence:"
1594 { $subsections reversed <reversed> }
1595 "Transposing a matrix:"
1596 { $subsections flip } ;
1597
1598 ARTICLE: "sequences-appending" "Appending sequences"
1599 "Basic append operations:"
1600 { $subsections
1601     append
1602     append-as
1603     prepend
1604     3append
1605     3append-as
1606     surround
1607     glue
1608 }
1609 "Collapse a sequence unto itself:"
1610 { $subsections concat join }
1611 "A pair of words useful for aligning strings:"
1612 { $subsections pad-head pad-tail } ;
1613
1614 ARTICLE: "sequences-slices" "Subsequences and slices"
1615 "There are two ways to extract a subrange of elements from a sequence. The first approach creates a new sequence of the same type as the input, which does not share storage with the underlying sequence. This takes time proportional to the number of elements being extracted. The second approach creates a " { $emphasis "slice" } ", which is a virtual sequence (see " { $link "virtual-sequences" } ") sharing storage with the original sequence. Slices are constructed in constant time."
1616 $nl
1617 "Some general guidelines for choosing between the two approaches:"
1618 { $list
1619   "If you are using mutable state, the choice has to be made one way or another because of semantics; mutating a slice will change the underlying sequence."
1620   { "Using a slice can improve algorithmic complexity. For example, if each iteration of a loop decomposes a sequence using " { $link first } " and " { $link rest } ", then the loop will run in quadratic time, relative to the length of the sequence. Using " { $link rest-slice } " changes the loop to run in linear time, since " { $link rest-slice } " does not copy any elements. Taking a slice of a slice will “collapse” the slice so to avoid the double indirection, so it is safe to use slices in recursive code." }
1621   "Accessing elements from a concrete sequence (such as a string or an array) is often faster than accessing elements from a slice, because slice access entails additional indirection. However, in some cases, if the slice is immediately consumed by an iteration combinator, the compiler can eliminate the slice allocation and indirect altogether."
1622   "If the slice outlives the original sequence, the original sequence will still remain in memory, since the slice will reference it. This can increase memory consumption unnecessarily."
1623 }
1624 { $heading "Subsequence operations" }
1625 "Extracting a subsequence:"
1626 { $subsections
1627     subseq
1628     head
1629     tail
1630     head*
1631     tail*
1632 }
1633 "Removing the first or last element:"
1634 { $subsections rest but-last }
1635 "Taking a sequence apart into a head and a tail:"
1636 { $subsections
1637     unclip
1638     unclip-last
1639     cut
1640     cut*
1641 }
1642 { $heading "Slice operations" }
1643 "The slice data type:"
1644 { $subsections slice slice? }
1645 "Extracting a slice:"
1646 { $subsections
1647     <slice>
1648     head-slice
1649     tail-slice
1650     head-slice*
1651     tail-slice*
1652 }
1653 "Removing the first or last element:"
1654 { $subsections rest-slice but-last-slice }
1655 "Taking a sequence apart into a head and a tail:"
1656 { $subsections unclip-slice unclip-last-slice cut-slice }
1657 "Replacing slices with new elements:"
1658 { $subsections replace-slice } ;
1659
1660 ARTICLE: "sequences-combinators" "Sequence combinators"
1661 "Iteration:"
1662 { $subsections
1663     each
1664     each-index
1665     reduce
1666     interleave
1667     replicate
1668     replicate-as
1669 }
1670 "Mapping:"
1671 { $subsections
1672     map
1673     map-as
1674     map-index
1675     map-index-as
1676     map-reduce
1677     accumulate
1678     accumulate-as
1679     accumulate!
1680     produce
1681     produce-as
1682 }
1683 "Filtering:"
1684 { $subsections
1685     filter
1686     filter-as
1687     partition
1688 }
1689 "Testing if a sequence contains elements satisfying a predicate:"
1690 { $subsections
1691     any?
1692     all?
1693 }
1694 { $heading "Related Articles" }
1695 { $subsections
1696     "sequence-2combinators"
1697     "sequence-3combinators"
1698 } ;
1699
1700 ARTICLE: "sequence-2combinators" "Pair-wise sequence combinators"
1701 "There is a set of combinators which traverse two sequences pairwise. If one sequence is shorter than the other, then only the prefix having the length of the minimum of the two is examined."
1702 { $subsections
1703     2each
1704     2reduce
1705     2map
1706     2map-as
1707     2map-reduce
1708     2all?
1709 } ;
1710
1711 ARTICLE: "sequence-3combinators" "Triple-wise sequence combinators"
1712 "There is a set of combinators which traverse three sequences triple-wise. If one sequence is shorter than the others, then only the prefix having the length of the minimum of the three is examined."
1713 { $subsections 3each 3map 3map-as } ;
1714
1715 ARTICLE: "sequences-tests" "Testing sequences"
1716 "Testing for an empty sequence:"
1717 { $subsections empty? }
1718 "Testing indices:"
1719 { $subsections bounds-check? }
1720 "Testing if a sequence contains an object:"
1721 { $subsections member? member-eq? }
1722 "Testing if a sequence contains a subsequence:"
1723 { $subsections head? tail? subseq? } ;
1724
1725 ARTICLE: "sequences-search" "Searching sequences"
1726 "Finding the index of an element:"
1727 { $subsections
1728     index
1729     index-from
1730     last-index
1731     last-index-from
1732 }
1733 "Finding the start of a subsequence:"
1734 { $subsections start start* }
1735 "Finding the index of an element satisfying a predicate:"
1736 { $subsections
1737     find
1738     find-from
1739     find-last
1740     find-last-from
1741     map-find
1742 } ;
1743
1744 ARTICLE: "sequences-trimming" "Trimming sequences"
1745 "Trimming words:"
1746 { $subsections trim trim-head trim-tail }
1747 "Potentially more efficient trim:"
1748 { $subsections trim-slice trim-head-slice trim-tail-slice } ;
1749
1750 ARTICLE: "sequences-destructive-discussion" "When to use destructive operations"
1751 "Constructive (non-destructive) operations should be preferred where possible because code without side-effects is usually more reusable and easier to reason about. There are two main reasons to use destructive operations:"
1752 { $list
1753     "For the side-effect. Some code is simpler to express with destructive operations; constructive operations return new objects, and sometimes ``threading'' the objects through the program manually complicates stack shuffling."
1754     { "As an optimization. Some code written to use constructive operations suffers from worse performance. An example is a loop which adds an element to a sequence on each iteration. Either " { $link suffix } " or " { $link suffix! } " could be used; however, the former copies the entire sequence each time, which would cause the loop to run in quadratic time." }
1755 }
1756 "The second reason is much weaker than the first one. In particular, many combinators (see " { $link map } ", " { $link produce } " and " { $link "namespaces-make" } ") as well as more advanced data structures (such as " { $vocab-link "persistent.vectors" } ") alleviate the need for explicit use of side effects." ;
1757
1758 ARTICLE: "sequences-destructive" "Destructive sequence operations"
1759 "Many operations have destructive variants that side effect an input sequence, instead of creating a new sequence:"
1760 { $table
1761     { "Constructive" "Destructive" }
1762     { { $link suffix } { $link suffix! } }
1763     { { $link remove } { $link remove! } }
1764     { { $link remove-eq } { $link remove-eq! } }
1765     { { $link remove-nth } { $link remove-nth! } }
1766     { { $link reverse } { $link reverse! } }
1767     { { $link append } { $link append! } }
1768     { { $link map } { $link map! } }
1769     { { $link filter } { $link filter! } }
1770 }
1771 "Changing elements:"
1772 { $subsections map! change-nth }
1773 "Deleting elements:"
1774 { $subsections
1775     remove!
1776     remove-eq!
1777     remove-nth!
1778     delete-slice
1779     delete-all
1780     filter!
1781 }
1782 "Adding elements:"
1783 { $subsections
1784     suffix!
1785     append!
1786 }
1787 "Other destructive words:"
1788 { $subsections
1789     reverse!
1790     move
1791     exchange
1792     copy
1793 }
1794 { $heading "Related Articles" }
1795 { $subsections
1796     "sequences-destructive-discussion"
1797     "sequences-stacks"
1798 }
1799 { $see-also set-nth push push-all pop pop* } ;
1800
1801 ARTICLE: "sequences-stacks" "Treating sequences as stacks"
1802 "The classical stack operations, modifying a sequence in place:"
1803 { $subsections push push-all pop pop* }
1804 { $see-also empty? } ;
1805
1806 ARTICLE: "sequences-comparing" "Comparing sequences"
1807 "Element equality testing:"
1808 { $subsections
1809     sequence=
1810     mismatch
1811     drop-prefix
1812     assert-sequence=
1813 }
1814 "The " { $link <=> } " generic word performs lexicographic comparison when applied to sequences." ;
1815
1816 ARTICLE: "sequences-f" "The f object as a sequence"
1817 "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." ;
1818
1819 ARTICLE: "sequences-combinator-implementation" "Implementing sequence combinators"
1820 "Creating a new sequence unconditionally:"
1821 { $subsections
1822     collector
1823     collector-for
1824 }
1825 "Creating a new sequence conditionally:"
1826 { $subsections
1827     selector
1828     selector-for
1829     2selector
1830 } ;
1831
1832 ARTICLE: "sequences-cartesian" "Cartesian product operations"
1833 "The cartesian product of two sequences is a sequence of all pairs where the first element of each pair is from the first sequence, and the second element of each pair is from the second sequence. The number of elements in the cartesian product is the product of the lengths of the two sequences."
1834 $nl
1835 "Combinators which pair every element of the first sequence with every element of the second:"
1836 { $subsections
1837     cartesian-each
1838     cartesian-map
1839 }
1840 "Computing the cartesian product of two sequences:"
1841 { $subsections
1842     cartesian-product
1843 } ;
1844
1845 ARTICLE: "sequences" "Sequence operations"
1846 "A " { $emphasis "sequence" } " is a finite, linearly-ordered collection of elements. Words for working with sequences are in the " { $vocab-link "sequences" } " vocabulary."
1847 $nl
1848 "Sequences implement a protocol:"
1849 { $subsections
1850     "sequence-protocol"
1851     "sequences-f"
1852 }
1853 "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" } "."
1854 { $subsections
1855     "sequences-access"
1856     "sequences-combinators"
1857     "sequences-add-remove"
1858     "sequences-appending"
1859     "sequences-slices"
1860     "sequences-reshape"
1861     "sequences-tests"
1862     "sequences-search"
1863     "sequences-comparing"
1864     "sequences-split"
1865     "grouping"
1866     "sequences-destructive"
1867     "sequences-stacks"
1868     "sequences-sorting"
1869     "binary-search"
1870     "sets"
1871     "sequences-trimming"
1872     "sequences-cartesian"
1873     "sequences.deep"
1874 }
1875 "Using sequences for looping:"
1876 { $subsections
1877     "sequences-integers"
1878     "math.ranges"
1879 }
1880 "Using sequences for control flow:"
1881 { $subsections "sequences-if" }
1882 "For inner loops:"
1883 { $subsections "sequences-unsafe" }
1884 "Implementing sequence combinators:"
1885 { $subsections "sequences-combinator-implementation" } ;
1886
1887 ABOUT: "sequences"