core/sequences/sequences-docs.factor

   1 USING: arrays help.markup help.syntax math
   2 sequences.private vectors strings kernel math.order layouts
   3 quotations ;
   4 IN: sequences
   5
   6 ARTICLE: "sequences-unsafe" "Unsafe sequence operations"
   7 "The " { $link nth-unsafe } " and " { $link set-nth-unsafe } " sequence protocol bypasses bounds checks for increased performance."
   8 $nl
   9 "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."
  10 $nl
  11 "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."
  12 $nl
  13 "The justification for this is that the VM should not crash if a resizable sequence is resized during the execution of an iteration combinator."
  14 $nl
  15 "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 } "." ;
  16
  17 ARTICLE: "sequence-protocol" "Sequence protocol"
  18 "All sequences must be instances of a mixin class:"
  19 { $subsection sequence }
  20 { $subsection sequence? }
  21 "All sequences must know their length:"
  22 { $subsection length }
  23 "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:"
  24 { $subsection nth }
  25 { $subsection nth-unsafe }
  26 "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:"
  27 { $subsection set-nth }
  28 { $subsection set-nth-unsafe }
  29 "Note that even if the sequence is immutable, at least one of the generic words must be specialized, otherwise calling them will result in an infinite recursion. There is a standard word which throws an error indicating a sequence is immutable:"
  30 { $subsection immutable }
  31 "The following two generic words are optional, as not all sequences are resizable:"
  32 { $subsection set-length }
  33 { $subsection lengthen }
  34 "An optional generic word for creating sequences of the same class as a given sequence:"
  35 { $subsection like }
  36 "Optional generic words for optimization purposes:"
  37 { $subsection new-sequence }
  38 { $subsection new-resizable }
  39 { $see-also "sequences-unsafe" } ;
  40
  41 ARTICLE: "sequences-integers" "Integer sequences and counted loops"
  42 "Integers support the sequence protocol in a trivial fashion; a non-negative integer presents its non-negative predecessors as elements. For example, the integer 3, when viewed as a sequence, contains the elements 0, 1, and 2. This is very useful for performing counted loops."
  43 $nl
  44 "For example, the " { $link each } " combinator, given an integer, simply calls a quotation that number of times, pushing a counter on each iteration that ranges from 0 up to that integer:"
  45 { $example "3 [ . ] each" "0\n1\n2" }
  46 "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 } "."
  47 $nl
  48 "Combinators that produce new sequences, such as " { $link map } ", will output an array if the input is an integer." ;
  49
  50 ARTICLE: "sequences-access" "Accessing sequence elements"
  51 { $subsection ?nth }
  52 "Concise way of extracting one of the first four elements:"
  53 { $subsection first }
  54 { $subsection second }
  55 { $subsection third }
  56 { $subsection fourth }
  57 "Unpacking sequences:"
  58 { $subsection first2 }
  59 { $subsection first3 }
  60 { $subsection first4 }
  61 { $see-also nth peek } ;
  62
  63 ARTICLE: "sequences-add-remove" "Adding and removing sequence elements"
  64 "Adding elements:"
  65 { $subsection prefix }
  66 { $subsection suffix }
  67 "Removing elements:"
  68 { $subsection remove } ;
  69
  70 ARTICLE: "sequences-reshape" "Reshaping sequences"
  71 "A " { $emphasis "repetition" } " is a virtual sequence consisting of a single element repeated multiple times:"
  72 { $subsection repetition }
  73 { $subsection <repetition> }
  74 "Reversing a sequence:"
  75 { $subsection reverse }
  76 "A " { $emphasis "reversal" } " presents a reversed view of an underlying sequence:"
  77 { $subsection reversed }
  78 { $subsection <reversed> }
  79 "Transposing a matrix:"
  80 { $subsection flip } ;
  81
  82 ARTICLE: "sequences-appending" "Appending sequences"
  83 { $subsection append }
  84 { $subsection 3append }
  85 { $subsection concat }
  86 { $subsection join }
  87 "A pair of words useful for aligning strings:"
  88 { $subsection pad-left }
  89 { $subsection pad-right } ;
  90
  91 ARTICLE: "sequences-slices" "Subsequences and slices"
  92 "Extracting a subsequence:"
  93 { $subsection subseq }
  94 { $subsection head }
  95 { $subsection tail }
  96 { $subsection head* }
  97 { $subsection tail* }
  98 "Removing the first or last element:"
  99 { $subsection rest }
 100 { $subsection but-last }
 101 "Taking a sequence apart into a head and a tail:"
 102 { $subsection unclip }
 103 { $subsection cut }
 104 { $subsection cut* }
 105 "A " { $emphasis "slice" } " is a virtual sequence which presents as view of a subsequence of an underlying sequence:"
 106 { $subsection slice }
 107 { $subsection slice? }
 108 "Creating slices:"
 109 { $subsection <slice> }
 110 { $subsection head-slice }
 111 { $subsection tail-slice }
 112 { $subsection but-last-slice }
 113 { $subsection rest-slice }
 114 { $subsection head-slice* }
 115 { $subsection tail-slice* }
 116 "Taking a sequence apart into a head and a tail:"
 117 { $subsection unclip-slice }
 118 { $subsection cut-slice }
 119 "A utility for words which use slices as iterators:"
 120 { $subsection <flat-slice> } ;
 121
 122 ARTICLE: "sequences-combinators" "Sequence combinators"
 123 "Iteration:"
 124 { $subsection each }
 125 { $subsection reduce }
 126 { $subsection interleave }
 127 "Mapping:"
 128 { $subsection map }
 129 { $subsection map-as }
 130 { $subsection accumulate }
 131 { $subsection produce }
 132 "Filtering:"
 133 { $subsection push-if }
 134 { $subsection filter }
 135 "Testing if a sequence contains elements satisfying a predicate:"
 136 { $subsection contains? }
 137 { $subsection all? }
 138 "Testing how elements are related:"
 139 { $subsection monotonic? }
 140 { $subsection "sequence-2combinators" } ;
 141
 142 ARTICLE: "sequence-2combinators" "Pair-wise sequence combinators"
 143 "There is a set of combinators which traverse two sequences pairwise. If one sequence is shorter than the other, than only the prefix having the length of the minimum of the two is examined."
 144 { $subsection 2each }
 145 { $subsection 2reduce }
 146 { $subsection 2map }
 147 { $subsection 2map-as }
 148 { $subsection 2all? } ;
 149
 150 ARTICLE: "sequences-tests" "Testing sequences"
 151 "Testing for an empty sequence:"
 152 { $subsection empty? }
 153 "Testing indices:"
 154 { $subsection bounds-check? }
 155 "Testing if a sequence contains an object:"
 156 { $subsection member? }
 157 { $subsection memq? }
 158 "Testing if a sequence contains a subsequence:"
 159 { $subsection head? }
 160 { $subsection tail? }
 161 { $subsection subseq? }
 162 "Testing how elements are related:"
 163 { $subsection all-eq? }
 164 { $subsection all-equal? } ;
 165
 166 ARTICLE: "sequences-search" "Searching sequences"
 167 "Finding the index of an element:"
 168 { $subsection index }
 169 { $subsection index-from }
 170 { $subsection last-index }
 171 { $subsection last-index-from }
 172 "Finding the start of a subsequence:"
 173 { $subsection start }
 174 { $subsection start* }
 175 "Finding the index of an element satisfying a predicate:"
 176 { $subsection find }
 177 { $subsection find-from }
 178 { $subsection find-last }
 179 { $subsection find-last-from } ;
 180
 181 ARTICLE: "sequences-trimming" "Trimming sequences"
 182 "Trimming words:"
 183 { $subsection trim }
 184 { $subsection trim-left }
 185 { $subsection trim-right }
 186 "Potentially more efficient trim:"
 187 { $subsection trim-slice }
 188 { $subsection trim-left-slice }
 189 { $subsection trim-right-slice } ;
 190
 191 ARTICLE: "sequences-destructive" "Destructive operations"
 192 "These words modify their input, instead of creating a new sequence."
 193 $nl
 194 "In-place variant of " { $link reverse } ":"
 195 { $subsection reverse-here }
 196 "In-place variant of " { $link append } ":"
 197 { $subsection push-all }
 198 "In-place variant of " { $link remove } ":"
 199 { $subsection delete }
 200 "In-place variant of " { $link map } ":"
 201 { $subsection change-each }
 202 "Changing elements:"
 203 { $subsection change-nth }
 204 { $subsection cache-nth }
 205 "Deleting elements:"
 206 { $subsection delete-nth }
 207 { $subsection delete-slice }
 208 { $subsection delete-all }
 209 "Other destructive words:"
 210 { $subsection move }
 211 { $subsection exchange }
 212 { $subsection copy }
 213 { $subsection replace-slice }
 214 { $see-also set-nth push pop "sequences-stacks" } ;
 215
 216 ARTICLE: "sequences-stacks" "Treating sequences as stacks"
 217 "The classical stack operations, modifying a sequence in place:"
 218 { $subsection peek }
 219 { $subsection push }
 220 { $subsection pop }
 221 { $subsection pop* }
 222 { $see-also empty? } ;
 223
 224 ARTICLE: "sequences-comparing" "Comparing sequences"
 225 "Element equality testing:"
 226 { $subsection sequence= }
 227 { $subsection mismatch }
 228 { $subsection drop-prefix }
 229 "The " { $link <=> } " generic word performs lexicographic comparison when applied to sequences." ;
 230
 231 ARTICLE: "sequences-f" "The f object as a sequence"
 232 "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." ;
 233
 234 ARTICLE: "sequences" "Sequence operations"
 235 "A " { $emphasis "sequence" } " is a finite, linearly-ordered collection of elements. Words for working with sequences are in the " { $vocab-link "sequences" } " vocabulary."
 236 $nl
 237 "Sequences implement a protocol:"
 238 { $subsection "sequence-protocol" }
 239 { $subsection "sequences-f" }
 240 { $subsection "sequences-integers" }
 241 "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 " { $emphasis "virtual sequences" } "."
 242 { $subsection "sequences-access" }
 243 { $subsection "sequences-combinators" }
 244 { $subsection "sequences-add-remove" }
 245 { $subsection "sequences-appending" }
 246 { $subsection "sequences-slices" }
 247 { $subsection "sequences-reshape" }
 248 { $subsection "sequences-tests" }
 249 { $subsection "sequences-search" }
 250 { $subsection "sequences-comparing" }
 251 { $subsection "sequences-split" }
 252 { $subsection "grouping" }
 253 { $subsection "sequences-destructive" }
 254 { $subsection "sequences-stacks" }
 255 { $subsection "sequences-sorting" }
 256 { $subsection "binary-search" }
 257 { $subsection "sets" }
 258 { $subsection "sequences-trimming" }
 259 "For inner loops:"
 260 { $subsection "sequences-unsafe" } ;
 261
 262 ABOUT: "sequences"
 263
 264 HELP: sequence
 265 { $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:"
 266     { $code "INSTANCE: my-sequence sequence" }
 267 } ;
 268
 269 HELP: length
 270 { $values { "seq" sequence } { "n" "a non-negative integer" } }
 271 { $contract "Outputs the length of the sequence. All sequences support this operation." } ;
 272
 273 HELP: set-length
 274 { $values { "n" "a non-negative integer" } { "seq" "a resizable sequence" } }
 275 { $contract "Resizes the sequence. Not all sequences are resizable." }
 276 { $errors "Throws a " { $link bounds-error } " if the new length is negative." }
 277 { $side-effects "seq" } ;
 278
 279 HELP: lengthen
 280 { $values { "n" "a non-negative integer" } { "seq" "a resizable sequence" } }
 281 { $contract "Ensures the sequence has a length of at least " { $snippet "n" } " elements. This word differs from " { $link set-length } " in two respects:"
 282     { $list
 283         { "This word does not shrink the sequence if " { $snippet "n" } " is less than its length." }
 284         { "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." }
 285     }
 286 } ;
 287
 288 HELP: nth
 289 { $values { "n" "a non-negative integer" } { "seq" sequence } { "elt" "the element at the " { $snippet "n" } "th index" } }
 290 { $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." }
 291 { $errors "Throws a " { $link bounds-error } " if the index is negative, or greater than or equal to the length of the sequence." } ;
 292
 293 HELP: set-nth
 294 { $values { "elt" object } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 295 { $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." }
 296 { $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."
 297 $nl
 298 "Throws an error if the sequence cannot hold elements of the given type." }
 299 { $side-effects "seq" } ;
 300
 301 HELP: immutable
 302 { $values { "seq" sequence } }
 303 { $description "Throws an " { $link immutable } " error." }
 304 { $error-description "Thrown if an attempt is made to modify an immutable sequence." } ;
 305
 306 HELP: new-sequence
 307 { $values { "len" "a non-negative integer" } { "seq" sequence } { "newseq" "a mutable sequence" } }
 308 { $contract "Outputs a mutable sequence of length " { $snippet "n" } " which can hold the elements of " { $snippet "seq" } "." } ;
 309
 310 HELP: new-resizable
 311 { $values { "len" "a non-negative integer" } { "seq" sequence } { "newseq" "a resizable mutable sequence" } }
 312 { $contract "Outputs a resizable mutable sequence with an initial capacity of " { $snippet "n" } " elements and zero length, which can hold the elements of " { $snippet "seq" } "." }
 313 { $examples
 314     { $example "USING: prettyprint sequences ;" "300 V{ } new-resizable ." "V{ }" }
 315     { $example "USING: prettyprint sequences ;" "300 SBUF\" \" new-resizable ." "SBUF\" \"" }
 316 } ;
 317
 318 HELP: like
 319 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" "a new sequence" } }
 320 { $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."
 321 $nl
 322 "The default implementation does nothing." }
 323 { $notes "Unlike " { $link clone-like } ", the output sequence might share storage with the input sequence." } ;
 324
 325 HELP: empty?
 326 { $values { "seq" sequence } { "?" "a boolean" } }
 327 { $description "Tests if the sequence has zero length." } ;
 328
 329 HELP: if-empty
 330 { $values { "seq" sequence } { "quot1" quotation } { "quot2" quotation } }
 331 { $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." }
 332 { $example
 333     "USING: kernel prettyprint sequences sequences.lib ;"
 334     "{ 1 2 3 } [ \"empty sequence\" ] [ sum ] if-empty ."
 335     "6"
 336 } ;
 337
 338 HELP: delete-all
 339 { $values { "seq" "a resizable sequence" } }
 340 { $description "Resizes the sequence to zero length, removing all elements. Not all sequences are resizable." }
 341 { $errors "Throws a " { $link bounds-error } " if the new length is negative, or if the sequence is not resizable." }
 342 { $side-effects "seq" } ;
 343
 344 HELP: resize
 345 { $values { "n" "a non-negative integer" } { "seq" sequence } { "newseq" "a new sequence" } }
 346 { $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." }
 347 { $notes "This generic word is only implemented for strings and arrays." } ;
 348
 349 HELP: first
 350 { $values { "seq" sequence } { "first" "the first element of the sequence" } }
 351 { $description "Outputs the first element of the sequence." }
 352 { $errors "Throws an error if the sequence is empty." } ;
 353
 354 HELP: second
 355 { $values { "seq" sequence } { "second" "the second element of the sequence" } }
 356 { $description "Outputs the second element of the sequence." }
 357 { $errors "Throws an error if the sequence contains less than two elements." } ;
 358
 359 HELP: third
 360 { $values { "seq" sequence } { "third" "the third element of the sequence" } }
 361 { $description "Outputs the third element of the sequence." }
 362 { $errors "Throws an error if the sequence contains less than three elements." } ;
 363
 364 HELP: fourth
 365 { $values { "seq" sequence } { "fourth" "the fourth element of the sequence" } }
 366 { $description "Outputs the fourth element of the sequence." }
 367 { $errors "Throws an error if the sequence contains less than four elements." } ;
 368
 369 HELP: push
 370 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 371 { $description "Adds an element at the end of the sequence. The sequence length is adjusted accordingly." }
 372 { $errors "Throws an error if " { $snippet "seq" } " is not resizable, or if the type of " { $snippet "elt" } " is not permitted in " { $snippet "seq" } "." }
 373 { $side-effects "seq" } ;
 374
 375 HELP: bounds-check?
 376 { $values { "n" "an integer" } { "seq" sequence } { "?" "a boolean" } }
 377 { $description "Tests if the index is within the bounds of the sequence." } ;
 378
 379 HELP: bounds-error
 380 { $values { "n" "a positive integer" } { "seq" sequence } }
 381 { $description "Throws a " { $link bounds-error } "." }
 382 { $error-description "Thrown by " { $link nth } ", " { $link set-nth } " and " { $link set-length } " if the given index lies beyond the bounds of the sequence." } ;
 383
 384 HELP: bounds-check
 385 { $values { "n" "a positive integer" } { "seq" sequence } }
 386 { $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." } ;
 387
 388 HELP: ?nth
 389 { $values { "n" "an integer" } { "seq" sequence } { "elt/f" "an object or " { $link f } } }
 390 { $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 } "." } ;
 391
 392 HELP: nth-unsafe
 393 { $values { "n" "an integer" } { "seq" sequence } { "elt" object } }
 394 { $contract "Unsafe variant of " { $link nth } " that does not perform bounds checks." } ;
 395
 396 HELP: set-nth-unsafe
 397 { $values { "elt" object } { "n" "an integer" } { "seq" sequence } }
 398 { $contract "Unsafe variant of " { $link set-nth } " that does not perform bounds checks." } ;
 399
 400 HELP: exchange-unsafe
 401 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 402 { $description "Unsafe variant of " { $link exchange } " that does not perform bounds checks." } ;
 403
 404 HELP: first2-unsafe
 405 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } }
 406 { $contract "Unsafe variant of " { $link first2 } " that does not perform bounds checks." } ;
 407
 408 HELP: first3-unsafe
 409 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } }
 410 { $contract "Unsafe variant of " { $link first3 } " that does not perform bounds checks." } ;
 411
 412 HELP: first4-unsafe
 413 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } { "fourth" "the fourth element" } }
 414 { $contract "Unsafe variant of " { $link first4 } " that does not perform bounds checks." } ;
 415
 416 HELP: 2sequence
 417 { $values { "obj1" object } { "obj2" object } { "exemplar" sequence } { "seq" sequence } }
 418 { $description "Creates a two-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 419
 420 HELP: 3sequence
 421 { $values { "obj1" object } { "obj2" object } { "obj3" object } { "exemplar" sequence } { "seq" sequence } }
 422 { $description "Creates a three-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 423
 424 HELP: 4sequence
 425 { $values { "obj1" object } { "obj2" object } { "exemplar" sequence } { "obj3" object } { "obj4" object } { "seq" sequence } }
 426 { $description "Creates a four-element sequence of the same type as " { $snippet "exemplar" } "." } ;
 427
 428 HELP: first2
 429 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } }
 430 { $description "Pushes the first two elements of a sequence." }
 431 { $errors "Throws an error if the sequence has less than two elements." } ;
 432
 433 HELP: first3
 434 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } }
 435 { $description "Pushes the first three elements of a sequence." }
 436 { $errors "Throws an error if the sequence has less than three elements." } ;
 437
 438 HELP: first4
 439 { $values { "seq" sequence } { "first" "the first element" } { "second" "the second element" } { "third" "the third element" } { "fourth" "the fourth element" } }
 440 { $description "Pushes the first four elements of a sequence." }
 441 { $errors "Throws an error if the sequence has less than four elements." } ;
 442
 443 HELP: array-capacity
 444 { $values { "array" "an array" } { "n" "a non-negative fixnum" } }
 445 { $class-description "A predicate class whose instances are valid array sizes for the current architecture. The minimum value is zero and the maximum value is " { $link max-array-capacity } "." }
 446 { $description "Low-level array length accessor." }
 447 { $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." } ;
 448
 449 HELP: array-nth
 450 { $values { "n" "a non-negative fixnum" } { "array" "an array" }  { "elt" object } }
 451 { $description "Low-level array element accessor." }
 452 { $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." } ;
 453
 454 HELP: set-array-nth
 455 { $values { "elt" object } { "n" "a non-negative fixnum" } { "array" "an array" }  }
 456 { $description "Low-level array element mutator." }
 457 { $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." } ;
 458
 459 HELP: collect
 460 { $values { "n" "a non-negative integer" } { "quot" "a quotation with stack effect " { $snippet "( n -- value )" } } { "into" "a sequence of length at least " { $snippet "n" } } }
 461 { $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." } ;
 462
 463 HELP: each
 464 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- )" } } }
 465 { $description "Applies the quotation to each element of the sequence in order." } ;
 466
 467 HELP: reduce
 468 { $values { "seq" sequence } { "identity" object } { "quot" "a quotation with stack effect " { $snippet "( prev elt -- next )" } } { "result" "the final result" } }
 469 { $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." }
 470 { $examples
 471     { $example "USING: math prettyprint sequences ;" "{ 1 5 3 } 0 [ + ] reduce ." "9" }
 472 } ;
 473
 474 HELP: accumulate
 475 { $values { "identity" object } { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( prev elt -- next )" } } { "final" "the final result" } { "newseq" "a new sequence" } }
 476 { $description "Combines successive elements of the sequence using a binary operation, and outputs a sequence of intermediate results together with the final result. On the first iteration, the two inputs to the quotation are " { $snippet "identity" } ", and the first element of the sequence. On successive iterations, the first input is the result of the previous iteration, and the second input is the corresponding element of the sequence."
 477 $nl
 478 "When given the empty sequence, outputs an empty sequence together with the " { $snippet "identity" } "." }
 479 { $examples
 480     { $example "USING: math prettyprint sequences ;" "{ 2 2 2 2 2 } 0 [ + ] accumulate . ." "{ 0 2 4 6 8 }\n10" }
 481 } ;
 482
 483 HELP: map
 484 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } { "newseq" "a new sequence" } }
 485 { $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." } ;
 486
 487 HELP: map-as
 488 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } { "newseq" "a new sequence" } { "exemplar" sequence } }
 489 { $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" } "." }
 490 { $examples
 491     "The following example converts a string into an array of one-element strings:"
 492     { $example "USING: prettyprint strings sequences ;" "\"Hello\" [ 1string ] { } map-as ." "{ \"H\" \"e\" \"l\" \"l\" \"o\" }" }
 493     "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."
 494 } ;
 495
 496 HELP: change-nth
 497 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( elt -- newelt )" } } }
 498 { $description "Applies the quotation to the " { $snippet "i" } "th element of the sequence, storing the result back into the sequence." }
 499 { $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" } "." }
 500 { $side-effects "seq" } ;
 501
 502 HELP: change-each
 503 { $values { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( old -- new )" } } }
 504 { $description "Applies the quotation to each element yielding a new element, storing the new elements back in the original sequence." }
 505 { $errors "Throws an error if the sequence is immutable, or the sequence cannot hold elements of the type output by " { $snippet "quot" } "." }
 506 { $side-effects "seq" } ;
 507
 508 HELP: min-length
 509 { $values { "seq1" sequence } { "seq2" sequence } { "n" "a non-negative integer" } }
 510 { $description "Outputs the minimum of the lengths of the two sequences." } ;
 511
 512 HELP: max-length
 513 { $values { "seq1" sequence } { "seq2" sequence } { "n" "a non-negative integer" } }
 514 { $description "Outputs the maximum of the lengths of the two sequences." } ;
 515
 516 HELP: 2each
 517 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- )" } } }
 518 { $description "Applies the quotation to pairs of elements from " { $snippet "seq1" } " and " { $snippet "seq2" } "." } ;
 519
 520 HELP: 2reduce
 521 { $values { "seq1" sequence }
 522           { "seq2" sequence }
 523           { "identity" object }
 524           { "quot" "a quotation with stack effect "
 525                    { $snippet "( prev elt1 elt2 -- next )" } }
 526           { "result" "the final result" } }
 527 { $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" } "." } ;
 528
 529 HELP: 2map
 530 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- new )" } } { "newseq" "a new sequence" } }
 531 { $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" } "." } ;
 532
 533 HELP: 2map-as
 534 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- new )" } } { "exemplar" sequence } { "newseq" "a new sequence" } }
 535 { $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" } "." } ;
 536
 537 HELP: 2all?
 538 { $values { "seq1" sequence } { "seq2" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt1 elt2 -- ? )" } } { "?" "a boolean" } }
 539 { $description "Tests the predicate pairwise against elements of " { $snippet "seq1" } " and " { $snippet "seq2" } "." } ;
 540
 541 HELP: find
 542 { $values { "seq" sequence }
 543           { "quot" "a quotation with stack effect "
 544                    { $snippet "( elt -- ? )" } }
 545           { "i" "the index of the first match, or f" }
 546           { "elt" "the first matching element, or " { $link f } } }
 547 { $description "A simpler variant of " { $link find-from } " where the starting index is 0." } ;
 548
 549 HELP: find-from
 550 { $values { "n" "a starting index" }
 551           { "seq" sequence }
 552           { "quot" "a quotation with stack effect "
 553                    { $snippet "( elt -- ? )" } }
 554           { "i" "the index of the first match, or f" }
 555           { "elt" "the first matching element, or " { $link f } } }
 556 { $description "Applies the quotation to each element of the sequence in turn, until it outputs a true value or the end of the sequence is reached. If the quotation yields a true value for some sequence element, the word outputs the element index and the element itself. Otherwise, the word outputs an index of f and " { $link f } " as the element." } ;
 557
 558 HELP: find-last
 559 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "i" "the index of the first match, or f" } { "elt" "the first matching element, or " { $link f } } }
 560 { $description "A simpler variant of " { $link find-last-from } " where the starting index is one less than the length of the sequence." } ;
 561
 562 HELP: find-last-from
 563 { $values { "n" "a starting index" } { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "i" "the index of the first match, or f" } { "elt" "the first matching element, or " { $link f } } }
 564 { $description "Applies the quotation to each element of the sequence in reverse order, until it outputs a true value or the start of the sequence is reached. If the quotation yields a true value for some sequence element, the word outputs the element index and the element itself. Otherwise, the word outputs an index of f and " { $link f } " as the element." } ;
 565
 566 HELP: contains?
 567 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "?" "a boolean" } }
 568 { $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 } "." } ;
 569
 570 HELP: all?
 571 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "?" "a boolean" } }
 572 { $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 } "." } ;
 573
 574 HELP: push-if
 575 { $values { "elt" object } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "accum" "a resizable mutable sequence" } }
 576 { $description "Adds the element at the end of the sequence if the quotation yields a true value." }
 577 { $notes "This word is a factor of " { $link filter } "." } ;
 578
 579 HELP: filter
 580 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt -- ? )" } } { "subseq" "a new sequence" } }
 581 { $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." } ;
 582
 583 HELP: monotonic?
 584 { $values { "seq" sequence } { "quot" "a quotation with stack effect " { $snippet "( elt elt -- ? )" } } { "?" "a boolean" } }
 585 { $description "Applies the relation to successive pairs of elements in the sequence, testing for a truth value. The relation should be a transitive relation, such as a total order or an equality relation." }
 586 { $examples
 587     "Testing if a sequence is non-decreasing:"
 588     { $example "USING: math prettyprint sequences ;" "{ 1 1 2 } [ <= ] monotonic? ." "t" }
 589     "Testing if a sequence is decreasing:"
 590     { $example "USING: math prettyprint sequences ;" "{ 9 8 6 7 } [ < ] monotonic? ." "f" }
 591 } ;
 592
 593 { monotonic? all-eq? all-equal? } related-words
 594
 595 HELP: interleave
 596 { $values { "seq" sequence } { "between" "a quotation" } { "quot" "a quotation with stack effect " { $snippet "( elt -- )" } } }
 597 { $description "Applies " { $snippet "quot" } " to each element in turn, also invoking " { $snippet "between" } " in-between each pair of elements." }
 598 { $example "USING: io sequences ;" "{ \"a\" \"b\" \"c\" } [ \"X\" write ] [ write ] interleave" "aXbXc" } ;
 599
 600 HELP: cache-nth
 601 { $values { "i" "a non-negative integer" } { "seq" "a mutable sequence" } { "quot" "a quotation with stack effect " { $snippet "( i -- elt )" } } { "elt" object } }
 602 { $description "If the sequence does not contain at least " { $snippet "i" } " elements or if the " { $snippet "i" } "th element of the sequence is " { $link f } ", calls the quotation to produce a new value, and stores it back into the sequence. Otherwise, this word outputs the " { $snippet "i" } "th element of the sequence." }
 603 { $side-effects "seq" } ;
 604
 605 HELP: index
 606 { $values { "obj" object } { "seq" sequence } { "n" "an index" } }
 607 { $description "Outputs the index of the first element in the sequence equal to " { $snippet "obj" } ". If no element is found, outputs " { $link f } "." } ;
 608
 609 HELP: index-from
 610 { $values { "obj" object } { "i" "a start index" } { "seq" sequence } { "n" "an index" } }
 611 { $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 } "." } ;
 612
 613 HELP: last-index
 614 { $values { "obj" object } { "seq" sequence } { "n" "an index" } }
 615 { $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 } "." } ;
 616
 617 HELP: last-index-from
 618 { $values { "obj" object } { "i" "a start index" } { "seq" sequence } { "n" "an index" } }
 619 { $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 } "." } ;
 620
 621 HELP: member?
 622 { $values { "obj" object } { "seq" sequence } { "?" "a boolean" } }
 623 { $description "Tests if the sequence contains an element equal to the object." } ;
 624
 625 HELP: memq?
 626 { $values { "obj" object } { "seq" sequence } { "?" "a boolean" } }
 627 { $description "Tests if the sequence contains the object." }
 628 { $examples
 629     "This word uses identity comparison, so the following will most likely print " { $link f } ":"
 630     { $example "USING: prettyprint sequences ;" "\"hello\" { \"hello\" } memq? ." "f" }
 631 } ;
 632
 633 HELP: remove
 634 { $values { "obj" object } { "seq" sequence } { "newseq" "a new sequence" } }
 635 { $description "Outputs a new sequence containing all elements of the input sequence except those equal to the given element." } ;
 636
 637 HELP: move
 638 { $values { "from" "an index in " { $snippet "seq" } } { "to" "an index in " { $snippet "seq" } } { "seq" "a mutable sequence" } }
 639 { $description "Sets the element with index " { $snippet "m" } " to the element with index " { $snippet "n" } "." }
 640 { $side-effects "seq" } ;
 641
 642 HELP: delete
 643 { $values { "elt" object } { "seq" "a resizable mutable sequence" } }
 644 { $description "Removes all elements equal to " { $snippet "elt" } " from " { $snippet "seq" } "." }
 645 { $side-effects "seq" } ;
 646
 647 HELP: delete-nth
 648 { $values { "n" "a non-negative integer" } { "seq" "a resizable mutable sequence" } }
 649 { $description "Removes the " { $snippet "n" } "th element from the sequence, shifting all other elements down and reducing its length by one." }
 650 { $side-effects "seq" } ;
 651
 652 HELP: delete-slice
 653 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" "a resizable mutable sequence" } }
 654 { $description "Removes a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } "." }
 655 { $side-effects "seq" } ;
 656
 657 HELP: replace-slice
 658 { $values { "new" sequence } { "seq" "a mutable sequence" } { "from" "a non-negative integer" } { "to" "a non-negative integer" } }
 659 { $description "Replaces a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } " with a new sequence." }
 660 { $notes "If the " { $snippet "to - from" } " is equal to the length of " { $snippet "new" } ", the sequence remains the same size, and does not have to support resizing. However, if " { $snippet "to - from" } " is not equal to the length of " { $snippet "new" } ", the " { $link set-length } " word is called on " { $snippet "seq" } ", so fixed-size sequences should not be passed in this case." }
 661 { $errors "Throws an error if " { $snippet "new" } " contains elements whose types are not permissible in " { $snippet "seq" } "." }
 662 { $side-effects "seq" } ;
 663
 664 { push prefix suffix } related-words
 665
 666 HELP: suffix
 667 { $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
 668 { $description "Outputs a new sequence obtained by adding " { $snippet "elt" } " at the end of " { $snippet "seq" } "." }
 669 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 670 { $examples
 671     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } 4 suffix ." "{ 1 2 3 4 }" }
 672 } ;
 673
 674 HELP: prefix
 675 { $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
 676 { $description "Outputs a new sequence obtained by adding " { $snippet "elt" } " at the beginning of " { $snippet "seq" } "." }
 677 { $errors "Throws an error if the type of " { $snippet "elt" } " is not permitted in sequences of the same class as " { $snippet "seq1" } "." }
 678 { $examples
 679 { $example "USING: prettyprint sequences ;" "{ 1 2 3 } 0 prefix ." "{ 0 1 2 3 }" }
 680 } ;
 681
 682 HELP: sum-lengths
 683 { $values { "seq" "a sequence of sequences" } { "n" integer } }
 684 { $description "Outputs the sum of the lengths of all sequences in " { $snippet "seq" } "." } ;
 685
 686 HELP: concat
 687 { $values { "seq" sequence } { "newseq" sequence } }
 688 { $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" } "." }
 689 { $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" } "." } ;
 690
 691 HELP: join
 692 { $values { "seq" sequence } { "glue" sequence } { "newseq" sequence } }
 693 { $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" } "." }
 694 { $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" } "." } ;
 695
 696 { join concat } related-words
 697
 698 HELP: peek
 699 { $values { "seq" sequence } { "elt" object } }
 700 { $description "Outputs the last element of a sequence." }
 701 { $errors "Throws an error if the sequence is empty." } ;
 702
 703 { peek pop pop* } related-words
 704
 705 HELP: pop*
 706 { $values { "seq" "a resizable mutable sequence" } }
 707 { $description "Removes the last element and shortens the sequence." }
 708 { $side-effects "seq" }
 709 { $errors "Throws an error if the sequence is empty." } ;
 710
 711 HELP: pop
 712 { $values { "seq" "a resizable mutable sequence" } { "elt" object } }
 713 { $description "Outputs the last element after removing it and shortening the sequence." }
 714 { $side-effects "seq" }
 715 { $errors "Throws an error if the sequence is empty." } ;
 716
 717 HELP: all-equal?
 718 { $values { "seq" sequence } { "?" "a boolean" } }
 719 { $description "Tests if all elements in the sequence are equal. Yields true with an empty sequence." } ;
 720
 721 HELP: all-eq?
 722 { $values { "seq" sequence } { "?" "a boolean" } }
 723 { $description "Tests if all elements in the sequence are the same identical object. Yields true with an empty sequence." } ;
 724
 725 HELP: mismatch
 726 { $values { "seq1" sequence } { "seq2" sequence } { "i" "an index" } }
 727 { $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." } ;
 728
 729 HELP: flip
 730 { $values { "matrix" "a sequence of equal-length sequences" } { "newmatrix" "a sequence of equal-length sequences" } }
 731 { $description "Transposes the matrix; that is, rows become columns and columns become rows." }
 732 { $examples { $example "USING: prettyprint sequences ;" "{ { 1 2 3 } { 4 5 6 } } flip ." "{ { 1 4 } { 2 5 } { 3 6 } }" } } ;
 733
 734 HELP: exchange
 735 { $values { "m" "a non-negative integer" } { "n" "a non-negative integer" } { "seq" "a mutable sequence" } }
 736 { $description "Exchanges the " { $snippet "m" } "th and " { $snippet "n" } "th elements of " { $snippet "seq" } "." } ;
 737
 738 HELP: reverse-here
 739 { $values { "seq" "a mutable sequence" } }
 740 { $description "Reverses a sequence in-place." }
 741 { $side-effects "seq" } ;
 742
 743 HELP: padding
 744 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "quot" "a quotation with stack effect " { $snippet "( seq1 seq2 -- newseq )" } } { "newseq" "a new sequence" } }
 745 { $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." } ;
 746
 747 HELP: pad-left
 748 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "padded" "a new sequence" } }
 749 { $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" } "." }
 750 { $examples { $example "USING: io sequences ;" "{ \"ab\" \"quux\" } [ 5 CHAR: - pad-left print ] each" "---ab\n-quux" } } ;
 751
 752 HELP: pad-right
 753 { $values { "seq" sequence } { "n" "a non-negative integer" } { "elt" object } { "padded" "a new sequence" } }
 754 { $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" } "." }
 755 { $examples { $example "USING: io sequences ;" "{ \"ab\" \"quux\" } [ 5 CHAR: - pad-right print ] each" "ab---\nquux-" } } ;
 756
 757 HELP: sequence=
 758 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 759 { $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." } ;
 760
 761 HELP: reversed
 762 { $class-description "A virtual sequence which presents a reversed view of an underlying sequence. New instances can be created by calling " { $link <reversed> } "." } ;
 763
 764 HELP: reverse
 765 { $values { "seq" sequence } { "newseq" "a new sequence" } }
 766 { $description "Outputs a new sequence having the same elements as " { $snippet "seq" } " but in reverse order." } ;
 767
 768 { reverse <reversed> } related-words
 769
 770 HELP: <reversed> ( seq -- reversed )
 771 { $values { "seq" sequence } { "reversed" "a new sequence" } }
 772 { $description "Creates an instance of the " { $link reversed } " virtual sequence." } ;
 773
 774 HELP: slice-error
 775 { $values { "str" "a reason" } }
 776 { $description "Throws a " { $link slice-error } "." }
 777 { $error-description "Thrown by " { $link <slice> } " if one of the following invalid conditions holds:"
 778     { $list
 779         "The start index is negative"
 780         "The end index is greater than the length of the sequence"
 781         "The start index is greater than the end index"
 782     }
 783 } ;
 784
 785 HELP: slice
 786 { $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> } "."
 787 $nl
 788 "Slices are mutable if the underlying sequence is mutable, and mutating a slice changes the underlying sequence. However, slices cannot be resized after creation." } ;
 789
 790 HELP: check-slice
 791 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } }
 792 { $description "Ensures that " { $snippet "m" } " is less than or equal to " { $snippet "m" } ", and that both indices are within bounds for " { $snippet "seq" } "." }
 793 { $errors "Throws a " { $link slice-error } " if the preconditions are not met." } ;
 794
 795 HELP: collapse-slice
 796 { $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 } }
 797 { $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." }
 798 ;
 799
 800 HELP: <flat-slice>
 801 { $values { "seq" sequence } { "slice" slice } }
 802 { $description "Outputs a slice with the same elements as " { $snippet "seq" } ", and " { $snippet "from" } " equal to 0 and " { $snippet "to" } " equal to the length of " { $snippet "seq" } "." }
 803 { $notes "Some words create slices then proceed to read the " { $snippet "to" } " and " { $snippet "from" } " slots of the slice. To behave predictably when they are themselves given a slice as input, they apply this word first to get a canonical slice." } ;
 804
 805 HELP: <slice>
 806 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "slice" slice } }
 807 { $description "Outputs a new virtual sequence sharing storage with the subrange of elements in " { $snippet "seq" } " with indices starting from and including " { $snippet "m" } ", and up to but not including " { $snippet "n" } "." }
 808 { $errors "Throws an error if " { $snippet "m" } " or " { $snippet "n" } " is out of bounds." }
 809 { $notes "Taking the slice of a slice outputs a slice of the underlying sequence of the original slice. Keep this in mind when writing code which depends on the values of " { $snippet "from" } " and " { $snippet "to" } " being equal to the inputs to this word. The " { $link <flat-slice> } " word might be helpful in such situations." } ;
 810
 811 { <slice> subseq } related-words
 812
 813 HELP: repetition
 814 { $class-description "A virtual sequence consisting of " { $snippet "elt" } " repeated " { $snippet "len" } " times. Repetitions are created by calling " { $link <repetition> } "." } ;
 815
 816 HELP: <repetition> ( len elt -- repetition )
 817 { $values { "len" "a non-negative integer" } { "elt" object } { "repetition" repetition } }
 818 { $description "Creates a new " { $link repetition } "." }
 819 { $examples
 820     { $example "USING: arrays prettyprint sequences ;" "10 \"X\" <repetition> >array ." "{ \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" \"X\" }" }
 821     { $example "USING: prettyprint sequences ;" "10 \"X\" <repetition> concat ." "\"XXXXXXXXXX\"" }
 822 } ;
 823 HELP: copy
 824 { $values { "src" sequence } { "i" "an index in " { $snippet "dest" } } { "dst" "a mutable sequence" } }
 825 { $description "Copies all elements of " { $snippet "src" } " to " { $snippet "dest" } ", with destination indices starting from " { $snippet "i" } ". Grows " { $snippet "to" } " first if necessary." }
 826 { $side-effects "dest" }
 827 { $errors "An error is thrown if " { $snippet "to" } " is not resizable, and not large enough to hold the copied elements." } ;
 828
 829 HELP: push-all
 830 { $values { "src" sequence } { "dest" "a resizable mutable sequence" } }
 831 { $description "Appends " { $snippet "src" } " to the end of " { $snippet "dest" } "." }
 832 { $side-effects "dest" }
 833 { $errors "Throws an error if " { $snippet "src" } " contains elements not permitted in " { $snippet "dest" } "." } ;
 834
 835 HELP: append
 836 { $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
 837 { $description "Outputs a new sequence of the same type as " { $snippet "seq1" } " consisting of the elements of " { $snippet "seq1" } " followed by " { $snippet "seq2" } "." }
 838 { $errors "Throws an error if " { $snippet "seq2" } " contains elements not permitted in sequences of the same class as " { $snippet "seq1" } "." } ;
 839
 840 HELP: 3append
 841 { $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
 842 { $description "Outputs a new sequence consisting of the elements of " { $snippet "seq1" } ", " { $snippet "seq2" } " and " { $snippet "seq3" } " in turn." }
 843 { $errors "Throws an error if " { $snippet "seq2" } " or " { $snippet "seq3" } " contain elements not permitted in sequences of the same class as " { $snippet "seq1" } "." } ;
 844
 845 HELP: subseq
 846 { $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "subseq" "a new sequence" } }
 847 { $description "Outputs a new sequence consisting of all elements starting from and including " { $snippet "from" } ", and up to but not including " { $snippet "to" } "." }
 848 { $errors "Throws an error if " { $snippet "from" } " or " { $snippet "to" } " is out of bounds." } ;
 849
 850 HELP: clone-like
 851 { $values { "seq" sequence } { "exemplar" sequence } { "newseq" "a new sequence" } }
 852 { $description "Outputs a newly-allocated sequence with the same elements as " { $snippet "seq" } " but of the same type as " { $snippet "exemplar" } "." }
 853 { $notes "Unlike " { $link like } ", this word always creates a new sequence which never shares storage with the original." } ;
 854
 855 HELP: head-slice
 856 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 857 { $description "Outputs a virtual sequence sharing storage with the first " { $snippet "n" } " elements of the input sequence." }
 858 { $errors "Throws an error if the index is out of bounds." } ;
 859
 860 HELP: tail-slice
 861 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 862 { $description "Outputs a virtual sequence sharing storage with all elements from the " { $snippet "n" } "th index until the end of the input sequence." }
 863 { $errors "Throws an error if the index is out of bounds." } ;
 864
 865 HELP: but-last-slice
 866 { $values { "seq" sequence } { "slice" "a slice" } }
 867 { $description "Outputs a virtual sequence sharing storage with all but the last element of the input sequence." }
 868 { $errors "Throws an error on an empty sequence." } ;
 869
 870 HELP: rest-slice
 871 { $values { "seq" sequence } { "slice" "a slice" } }
 872 { $description "Outputs a virtual sequence sharing storage with all elements from the 1st index until the end of the input sequence." }
 873 { $notes "Equivalent to " { $snippet "1 tail" } }
 874 { $errors "Throws an error on an empty sequence." } ;
 875
 876 HELP: head-slice*
 877 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 878 { $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." }
 879 { $errors "Throws an error if the index is out of bounds." } ;
 880
 881 HELP: tail-slice*
 882 { $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
 883 { $description "Outputs a virtual sequence sharing storage with the last " { $snippet "n" } " elements of the input sequence." }
 884 { $errors "Throws an error if the index is out of bounds." } ;
 885
 886 HELP: head
 887 { $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
 888 { $description "Outputs a new sequence consisting of the first " { $snippet "n" } " elements of the input sequence." }
 889 { $errors "Throws an error if the index is out of bounds." } ;
 890
 891 HELP: tail
 892 { $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
 893 { $description "Outputs a new sequence consisting of the input sequence with the first n items removed." }
 894 { $errors "Throws an error if the index is out of bounds." } ;
 895
 896 HELP: but-last
 897 { $values { "seq" sequence } { "headseq" "a new sequence" } }
 898 { $description "Outputs a new sequence consisting of the input sequence with the last item removed." }
 899 { $errors "Throws an error on an empty sequence." } ;
 900
 901 HELP: rest
 902 { $values { "seq" sequence } { "tailseq" "a new sequence" } }
 903 { $description "Outputs a new sequence consisting of the input sequence with the first item removed." }
 904 { $errors "Throws an error on an empty sequence." } ;
 905
 906 HELP: head*
 907 { $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
 908 { $description "Outputs a new sequence consisting of all elements of " { $snippet "seq" } " until the " { $snippet "n" } "th element from the end. In other words, it outputs a sequence of the first " { $snippet "l-n" } " elements of the input sequence, where " { $snippet "l" } " is its length." }
 909 { $errors "Throws an error if the index is out of bounds." } ;
 910
 911 HELP: tail*
 912 { $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
 913 { $description "Outputs a new sequence consisting of the last " { $snippet "n" } " elements of the input sequence." }
 914 { $errors "Throws an error if the index is out of bounds." } ;
 915
 916 HELP: shorter?
 917 { $values { "seq1" sequence } { "seq2" sequence } { "?" "a boolean" } }
 918 { $description "Tets if the length of " { $snippet "seq1" } " is smaller than the length of " { $snippet "seq2" } "." } ;
 919
 920 HELP: head?
 921 { $values { "seq" sequence } { "begin" sequence } { "?" "a boolean" } }
 922 { $description "Tests if " { $snippet "seq" } " starts with " { $snippet "begin" } ". If " { $snippet "begin" } " is longer than " { $snippet "seq" } ", this word outputs " { $link f } "." } ;
 923
 924 HELP: tail?
 925 { $values { "seq" sequence } { "end" sequence } { "?" "a boolean" } }
 926 { $description "Tests if " { $snippet "seq" } " ends with " { $snippet "end" } ". If " { $snippet "end" } " is longer than " { $snippet "seq" } ", this word outputs " { $link f } "." } ;
 927
 928 { delete-nth remove delete } related-words
 929
 930 HELP: cut-slice
 931 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" "a slice" } }
 932 { $description "Outputs a pair of sequences, where " { $snippet "before" } " consists of the first " { $snippet "n" } " elements of " { $snippet "seq" } " and has the same type, while " { $snippet "after" } " is a slice of the remaining elements." }
 933 { $notes "Unlike " { $link cut } ", the run time of this word is proportional to the length of " { $snippet "before" } ", not " { $snippet "after" } ", so it is suitable for use in an iterative algorithm which cuts successive pieces off a sequence." } ;
 934
 935 HELP: cut
 936 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
 937 { $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" } "." }
 938 { $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." } ;
 939
 940 HELP: cut*
 941 { $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
 942 { $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" } "." } ;
 943
 944 HELP: start*
 945 { $values { "subseq" sequence } { "seq" sequence } { "n" "a start index" } { "i" "a start index" } }
 946 { $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 } "." } ;
 947
 948 HELP: start
 949 { $values { "subseq" sequence } { "seq" sequence } { "i" "a start index" } }
 950 { $description "Outputs the start index of the first contiguous subsequence equal to " { $snippet "subseq" } ", or " { $link f } " if no matching subsequence is found." } ;
 951
 952 HELP: subseq?
 953 { $values { "subseq" sequence } { "seq" sequence } { "?" "a boolean" } }
 954 { $description "Tests if " { $snippet "seq" } " contains the elements of " { $snippet "subseq" } " as a contiguous subsequence." } ;
 955
 956 HELP: drop-prefix
 957 { $values { "seq1" sequence } { "seq2" sequence } { "slice1" "a slice" } { "slice2" "a slice" } }
 958 { $description "Outputs a pair of virtual sequences with the common prefix of " { $snippet "seq1" } " and " { $snippet "seq2" } " removed." } ;
 959
 960 HELP: unclip
 961 { $values { "seq" sequence } { "rest" sequence } { "first" object } }
 962 { $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." }
 963 { $examples
 964     { $example "USING: prettyprint sequences ;" "{ 1 2 3 } unclip suffix ." "{ 2 3 1 }" }
 965 } ;
 966
 967 HELP: unclip-slice
 968 { $values { "seq" sequence } { "rest" slice } { "first" object } }
 969 { $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." } ;
 970
 971 HELP: sum
 972 { $values { "seq" "a sequence of numbers" } { "n" "a number" } }
 973 { $description "Outputs the sum of all elements of " { $snippet "seq" } ". Outputs zero given an empty sequence." } ;
 974
 975 HELP: product
 976 { $values { "seq" "a sequence of numbers" } { "n" "a number" } }
 977 { $description "Outputs the product of all elements of " { $snippet "seq" } ". Outputs one given an empty sequence." } ;
 978
 979 HELP: infimum
 980 { $values { "seq" "a sequence of real numbers" } { "n" "a number" } }
 981 { $description "Outputs the least element of " { $snippet "seq" } "." }
 982 { $errors "Throws an error if the sequence is empty." } ;
 983
 984 HELP: supremum
 985 { $values { "seq" "a sequence of real numbers" } { "n" "a number" } }
 986 { $description "Outputs the greatest element of " { $snippet "seq" } "." }
 987 { $errors "Throws an error if the sequence is empty." } ;
 988
 989 HELP: produce
 990 { $values { "pred" "a quotation with stack effect " { $snippet "( -- ? )" } } { "quot" "a quotation with stack effect " { $snippet "( -- obj )" } } { "tail" "a quotation" } { "seq" "a sequence" } }
 991 { $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." }
 992 { $examples
 993     "The following example divides a number by two until we reach zero, and accumulates intermediate results:"
 994     { $example "USING: kernel math prettyprint sequences ;" "1337 [ dup 0 > ] [ 2/ dup ] [ ] produce nip ." "{ 668 334 167 83 41 20 10 5 2 1 0 }" }
 995     "The " { $snippet "tail" } " quotation is used when the predicate produces more than one output value. In this case, we have to drop this value even if the predicate fails in order for stack inference to calculate a stack effect for the " { $link produce } " call:"
 996     { $unchecked-example "USING: kernel prettyprint random sequences ;" "[ 10 random dup 1 > ] [ ] [ drop ] produce ." "{ 8 2 2 9 }" }
 997 } ;
 998
 999 HELP: sigma
1000 { $values { "seq" sequence } { "quot" quotation } { "n" number } }
1001 { $description "Like map sum, but without creating an intermediate sequence." }
1002 { $example
1003     "! Find the sum of the squares [0,99]"
1004     "USING: math math.ranges sequences prettyprint ;"
1005     "100 [1,b] [ sq ] sigma ."
1006     "338350"
1007 } ;
1008
1009 HELP: count
1010 { $values { "seq" sequence } { "quot" quotation } { "n" integer } }
1011 { $description "Efficiently returns the number of elements that the predicate quotation matches." }
1012 { $example
1013     "USING: math math.ranges sequences prettyprint ;"
1014     "100 [1,b] [ even? ] count ."
1015     "50"
1016 } ;
1017
1018 HELP: pusher
1019 { $values
1020      { "quot" "a predicate quotation" }
1021      { "quot" quotation } { "accum" vector } }
1022 { $description "Creates a new vector to accumulate the values which return true for a predicate.  Returns a new quotation which accepts an object to be tested and stored in the accumulator if the test yields true. The accumulator is left on the stack for convenience." }
1023 { $example "! Find all the even numbers:" "USING: prettyprint sequences math kernel ;"
1024            "10 [ even? ] pusher [ each ] dip ."
1025            "V{ 0 2 4 6 8 }"
1026 }
1027 { $notes "Used to implement the " { $link filter } " word." } ;
1028
1029 HELP: trim-left
1030 { $values
1031      { "seq" sequence } { "quot" quotation }
1032      { "newseq" sequence } }
1033 { $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." }
1034 { $example "" "USING: prettyprint math sequences ;"
1035            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-left ."
1036            "{ 1 2 3 0 0 }"
1037 } ;
1038
1039 HELP: trim-right
1040 { $values
1041      { "seq" sequence } { "quot" quotation }
1042      { "newseq" sequence } }
1043 { $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." }
1044 { $example "" "USING: prettyprint math sequences ;"
1045            "{ 0 0 1 2 3 0 0 } [ zero? ] trim-right ."
1046            "{ 0 0 1 2 3 }"
1047 } ;
1048
1049 HELP: trim
1050 { $values
1051      { "seq" sequence } { "quot" quotation }
1052      { "newseq" sequence } }
1053 { $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." }
1054 { $example "" "USING: prettyprint math sequences ;"
1055            "{ 0 0 1 2 3 0 0 } [ zero? ] trim ."
1056            "{ 1 2 3 }"
1057 } ;
1058
1059 { trim-left trim-right trim } related-words