core/sequences/sequences-docs.factor

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