core/sequences/sequences-docs.factor

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