-USING: assocs arrays generic.single help.markup help.syntax kernel
+USING: arrays generic.single help.markup help.syntax kernel
layouts math math.order quotations sequences.private vectors ;
IN: sequences
{ $examples "This word is equivalent to " { $link if-empty } " with an empty first quotation:"
{ $example
"USING: sequences prettyprint ;"
- "{ 4 5 6 } [ ] [ sum ] if-empty ."
+ "{ 4 5 6 } [ ] [ sum . ] if-empty"
"15"
}
{ $example
"USING: sequences prettyprint ;"
- "{ 4 5 6 } [ sum ] unless-empty ."
+ "{ 4 5 6 } [ sum . ] unless-empty"
"15"
}
} ;
HELP: delete-all
{ $values { "seq" "a resizable sequence" } }
{ $description "Resizes the sequence to zero length, removing all elements. Not all sequences are resizable." }
-{ $errors "Throws a " { $link bounds-error } " if the new length is negative, or if the sequence is not resizable." }
+{ $errors "Throws an error if the sequence is not resizable." }
{ $side-effects "seq" } ;
HELP: resize
HELP: ?set-nth
{ $values { "elt" object } { "n" integer } { "seq" sequence } }
-{ $description "A forgiving version of " { $link set-nth } ". If the index is out of bounds, does nothing." } ;
+{ $description "A forgiving version of " { $link set-nth } ". If the index is out of bounds, does nothing." } ;
HELP: ?first
{ $values { "seq" sequence } { "elt/f" { $maybe object } } }
HELP: 2all?
{ $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ? ) } } { "?" boolean } }
-{ $description "Tests the predicate pairwise against elements of " { $snippet "seq1" } " and " { $snippet "seq2" } ". If the sequences have different lengths, then only the smallest sequences items are compared with the other." }
+{ $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." }
{ $examples
{ $example
"USING: math prettyprint sequences ;"
}
} ;
+HELP: 2any?
+{ $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ? ) } } { "?" boolean } }
+{ $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." }
+{ $examples
+ { $example
+ "USING: math prettyprint sequences ;"
+ "{ 2 4 5 8 } { 2 4 6 8 } [ < ] 2any? ."
+ "t"
+ }
+} ;
+
HELP: find
{ $values { "seq" sequence }
{ "quot" { $quotation ( ... elt -- ... ? ) } }
{ "quot" { $quotation ( ... elt i -- ... ? ) } }
{ "i" { $maybe "the index of the first match" } }
{ "elt" { $maybe "the first matching element" } } }
-{ $description "A varient of " { $link find } " where the quotation takes both an element and its index." } ;
+{ $description "A variant of " { $link find } " where the quotation takes both an element and its index." } ;
HELP: find-index-from
{ $values { "n" "a starting index" }
{ "quot" { $quotation ( ... elt i -- ... ? ) } }
{ "i" { $maybe "the index of the first match" } }
{ "elt" { $maybe "the first matching element" } } }
-{ $description "A varient of " { $link find-from } " where the quotation takes both an element and its index." } ;
+{ $description "A variant of " { $link find-from } " where the quotation takes both an element and its index." } ;
HELP: map-find
{ $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... result/f ) } } { "result" "the first non-false result of the quotation" } { "elt" { $maybe "the first matching element" } } }
{ $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "?" boolean } }
{ $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 } "." } ;
+HELP: none?
+{ $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "?" boolean } }
+{ $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 } "." } ;
+
HELP: all?
{ $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ? ) } } { "?" boolean } }
{ $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 } "." } ;
HELP: remove
{ $values { "elt" object } { "seq" sequence } { "newseq" "a new sequence" } }
-{ $description "Outputs a new sequence containing all elements of the input sequence except for given element." }
+{ $description "Outputs a new sequence containing all elements of the input sequence except for the given element." }
{ $notes "This word uses equality comparison (" { $link = } ")." } ;
HELP: remove-eq
{ $description "Replaces a range of elements beginning at index " { $snippet "from" } " and ending before index " { $snippet "to" } " with a new sequence." }
{ $errors "Throws an error if " { $snippet "new" } " contains elements whose types are not permissible in " { $snippet "seq" } "." } ;
-{ push prefix suffix } related-words
+{ push push-either push-if pop pop* prefix suffix suffix! } related-words
HELP: suffix
{ $values { "seq" sequence } { "elt" object } { "newseq" sequence } }
{ $examples
"Join a list of strings as a string buffer:"
{ $example "USING: sequences prettyprint ;"
- "{ \"a\" \"b\" \"c\" } \"1\" SBUF\" \"join-as ."
+ "{ \"a\" \"b\" \"c\" } \"1\" SBUF\" \" join-as ."
"SBUF\" a1b1c\""
}
}
{ $description "Outputs the last element of a sequence." }
{ $errors "Throws an error if the sequence is empty." } ;
-{ pop pop* } related-words
-
HELP: pop*
{ $values { "seq" "a resizable mutable sequence" } }
{ $description "Removes the last element and shortens the sequence." }
}
} ;
+HELP: >slice<
+{ $values
+ { "slice" slice }
+ { "from" integer } { "to" integer } { "seq" sequence }
+}
+{ $description "Sets up the stack for iteration with slots from a " { $link slice } ". Used with iteration in words such as " { $link sequence-operator } "." } ;
+
+HELP: >underlying<
+{ $values
+ { "slice/seq" object }
+ { "i" integer } { "n" integer }
+}
+{ $description "Sets up the stack for iteration with slots from a " { $link sequence } ". Used with iteration in words such as " { $link sequence-operator } "." } ;
+
HELP: slice
{ $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."
$nl
HELP: <slice>
{ $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "slice" slice } }
-{ $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" } "." }
-{ $errors "Throws an error if " { $snippet "m" } " or " { $snippet "n" } " is out of bounds." }
+{ $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" } "." }
+{ $errors "Throws an error if " { $snippet "from" } " or " { $snippet "to" } " are out of bounds." }
{ $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> } "." } ;
{ <slice> subseq } related-words
}
} ;
-{ append append-as } related-words
+{ append append-as append! 3append 3append-as push-all } related-words
HELP: prepend
{ $values { "seq1" sequence } { "seq2" sequence } { "newseq" sequence } }
}
} ;
-{ 3append 3append-as } related-words
-
HELP: surround
{ $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
{ $description "Outputs a new sequence with " { $snippet "seq1" } " inserted between " { $snippet "seq2" } " and " { $snippet "seq3" } "." }
}
} ;
+HELP: surround-as
+{ $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "exemplar" sequence } { "newseq" sequence } }
+{ $description "Outputs a new sequence with " { $snippet "seq1" } " inserted between " { $snippet "seq2" } " and " { $snippet "seq3" } " of the same type as " { $snippet "exemplar" } "." }
+{ $examples
+ { $example "USING: sequences prettyprint ;"
+ "\"sssssh\" \"(\" \")\" SBUF\" \" surround-as ."
+ "SBUF\" (sssssh)\""
+ }
+} ;
+
+{ surround surround-as } related-words
+
HELP: glue
{ $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "newseq" sequence } }
{ $description "Outputs a new sequence with " { $snippet "seq3" } " inserted between " { $snippet "seq1" } " and " { $snippet "seq2" } "." }
}
} ;
+HELP: glue-as
+{ $values { "seq1" sequence } { "seq2" sequence } { "seq3" sequence } { "exemplar" sequence } { "newseq" sequence } }
+{ $description "Outputs a new sequence with " { $snippet "seq3" } " inserted between " { $snippet "seq1" } " and " { $snippet "seq2" } " of the same type as " { $snippet "exemplar" } "." }
+{ $examples
+ { $example "USING: sequences prettyprint ;"
+ "\"a\" \"b\" \",\" SBUF\" \" glue-as ."
+ "SBUF\" a,b\""
+ }
+} ;
+
+{ glue glue-as } related-words
+
HELP: subseq
{ $values { "from" "a non-negative integer" } { "to" "a non-negative integer" } { "seq" sequence } { "subseq" "a new sequence" } }
{ $description "Outputs a new sequence consisting of all elements starting from and including " { $snippet "from" } ", and up to but not including " { $snippet "to" } "." }
{ $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." }
{ $errors "Throws an error if the index is out of bounds." } ;
+{ head-slice head-slice* } related-words
+
HELP: tail-slice*
{ $values { "seq" sequence } { "n" "a non-negative integer" } { "slice" "a slice" } }
{ $description "Outputs a virtual sequence sharing storage with the last " { $snippet "n" } " elements of the input sequence." }
{ $errors "Throws an error if the index is out of bounds." } ;
+{ tail-slice tail-slice* } related-words
+
+HELP: head-to-index
+{ $values
+ { "seq" sequence } { "to" integer }
+ { "zero" object }
+}
+{ $description "Sets up the stack for the " { $link head } " word." } ;
+
HELP: head
{ $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
{ $description "Outputs a new sequence consisting of the first " { $snippet "n" } " elements of the input sequence." }
}
"When a sequence may not have enough elements:"
{ $example "USING: sequences prettyprint ;"
- "{ 1 2 } 5 short head ."
+ "{ 1 2 } 5 index-or-length head ."
"{ 1 2 }"
}
}
{ $errors "Throws an error if the index is out of bounds." } ;
+HELP: index-to-tail
+{ $values
+ { "seq" sequence } { "from" integer }
+ { "length" object }
+}
+{ $description "Sets up the stack for the " { $link tail } " word." } ;
+
HELP: tail
{ $values { "seq" sequence } { "n" "a non-negative integer" } { "tailseq" "a new sequence" } }
{ $description "Outputs a new sequence consisting of the input sequence with the first " { $snippet "n" } " items removed." }
}
"When a sequence may not have enough elements:"
{ $example "USING: sequences prettyprint ;"
- "{ 1 2 } 5 short tail ."
+ "{ 1 2 } 5 index-or-length tail ."
"{ }"
}
}
HELP: head*
{ $values { "seq" sequence } { "n" "a non-negative integer" } { "headseq" "a new sequence" } }
-{ $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." }
+{ $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." }
{ $examples
{ $example "USING: sequences prettyprint ;"
"{ 1 2 3 4 5 6 7 } 2 head* ."
}
"When a sequence may not have enough elements:"
{ $example "USING: sequences prettyprint ;"
- "{ 1 2 } 5 short head* ."
+ "{ 1 2 } 5 index-or-length head* ."
"{ }"
}
}
}
"When a sequence may not have enough elements:"
{ $example "USING: sequences prettyprint ;"
- "{ 1 2 } 5 short tail* ."
+ "{ 1 2 } 5 index-or-length tail* ."
"{ 1 2 }"
}
}
{ $errors "Throws an error if the index is out of bounds." } ;
+{ tail tail* tail-slice tail-slice* } related-words
+{ head head* head-slice head-slice* } related-words
+{ cut cut* cut-slice cut-slice* } related-words
+{ unclip unclip-slice unclip-last unclip-last-slice } related-words
+{ first last but-last but-last-slice rest rest-slice } related-words
+
HELP: shorter?
{ $values { "seq1" sequence } { "seq2" sequence } { "?" boolean } }
{ $description "Tests if the length of " { $snippet "seq1" } " is smaller than the length of " { $snippet "seq2" } "." } ;
{ remove remove-nth remove-eq remove-eq! remove! remove-nth! } related-words
HELP: cut-slice
-{ $values { "seq" sequence } { "n" "a non-negative integer" } { "before-slice" sequence } { "after-slice" "a slice" } }
-{ $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." }
-{ $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." } ;
+{ $values { "seq" sequence } { "n" "a non-negative integer" } { "before-slice" "a slice" } { "after-slice" "a slice" } }
+{ $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." }
+{ $notes "Unlike " { $link cut } ", this is suitable for use in an iterative algorithm which cuts successive pieces off a sequence." } ;
+
+HELP: cut-slice*
+{ $values { "seq" sequence } { "n" "a non-negative integer" } { "before-slice" "a slice" } { "after-slice" "a slice" } }
+{ $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." }
+{ $notes "Unlike " { $link cut* } ", this is suitable for use in an iterative algorithm which cuts successive pieces off a sequence." } ;
HELP: cut
{ $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
{ $values { "seq" sequence } { "n" "a non-negative integer" } { "before" sequence } { "after" sequence } }
{ $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" } "." } ;
-HELP: start*
-{ $values { "subseq" sequence } { "seq" sequence } { "n" "a start index" } { "i" "a start index" } }
+HELP: subseq-starts-at?
+{ $values { "i" "a start index" } { "seq" sequence } { "subseq" sequence } { "?" boolean } }
+{ $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." } ;
+
+HELP: subseq-index
+{ $values { "seq" sequence } { "subseq" sequence } { "i/f" "a start index or " { $snippet "f" } } }
+{ $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 } "." } ;
+
+HELP: subseq-index-from
+{ $values { "n" "a start index" } { "seq" sequence } { "subseq" sequence } { "i/f" "a start index or " { $snippet "f" } } }
{ $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 } "." } ;
-HELP: start
-{ $values { "subseq" sequence } { "seq" sequence } { "i" "a start index" } }
+HELP: subseq-start-from
+{ $values
+ { "subseq" object } { "seq" sequence } { "n" integer }
+ { "i/f" { $maybe integer } }
+}
+{ $description "Outputs the start index of the first contiguous subsequence equal to " { $snippet "subseq" } ", or " { $link f } " if no matching subsequence is found starting from " { $snippet "n" } "." } ;
+
+HELP: subseq-start
+{ $values { "subseq" sequence } { "seq" sequence } { "i/f" "a start index or " { $snippet "f" } } }
{ $description "Outputs the start index of the first contiguous subsequence equal to " { $snippet "subseq" } ", or " { $link f } " if no matching subsequence is found." } ;
HELP: subseq?
{ $values { "subseq" sequence } { "seq" sequence } { "?" boolean } }
{ $description "Tests if " { $snippet "seq" } " contains the elements of " { $snippet "subseq" } " as a contiguous subsequence." } ;
+HELP: subseq-of?
+{ $values { "seq" sequence } { "subseq" sequence } { "?" boolean } }
+{ $description "Tests if " { $snippet "seq" } " contains the elements of " { $snippet "subseq" } " as a contiguous subsequence." } ;
+
HELP: drop-prefix
{ $values { "seq1" sequence } { "seq2" sequence } { "slice1" "a slice" } { "slice2" "a slice" } }
{ $description "Outputs a pair of virtual sequences with the common prefix of " { $snippet "seq1" } " and " { $snippet "seq2" } " removed." } ;
HELP: unclip-last-slice
{ $values { "seq" sequence } { "butlast-slice" slice } { "last" object } }
-{ $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." } ;
+{ $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." } ;
HELP: sum
{ $values { "seq" { $sequence number } } { "n" number } }
HELP: infimum
{ $values { "seq" sequence } { "elt" object } }
{ $description "Outputs the least element of " { $snippet "seq" } "." }
+{ $examples
+ "Example:"
+ { $example "USING: sequences prettyprint ;"
+ "{ 1 2 3 4 5 } infimum ."
+ "1"
+ }
+ "Example:"
+ { $example "USING: sequences prettyprint ;"
+ "{ \"c\" \"b\" \"a\" } infimum ."
+ "\"a\""
+ }
+}
+{ $errors "Throws an error if the sequence is empty." } ;
+
+HELP: infimum-by
+{ $values
+ { "seq" sequence } { "quot" quotation }
+ { "elt" object }
+}
+{ $description "Outputs the least element of " { $snippet "seq" } " according to the " { $snippet "quot" } "." }
+{ $examples
+ "Example:"
+ { $example "USING: sequences prettyprint ;"
+ "{ { 1 2 } { 1 2 3 } { 1 2 3 4 } } [ length ] infimum-by ."
+ "{ 1 2 }"
+ }
+}
{ $errors "Throws an error if the sequence is empty." } ;
HELP: supremum
{ $values { "seq" sequence } { "elt" object } }
{ $description "Outputs the greatest element of " { $snippet "seq" } "." }
+{ $examples
+ "Example:"
+ { $example "USING: sequences prettyprint ;"
+ "{ 1 2 3 4 5 } supremum ."
+ "5"
+ }
+ "Example:"
+ { $example "USING: sequences prettyprint ;"
+ "{ \"c\" \"b\" \"a\" } supremum ."
+ "\"c\""
+ }
+}
{ $errors "Throws an error if the sequence is empty." } ;
-{ min max supremum infimum } related-words
+HELP: supremum-by
+{ $values
+ { "seq" sequence } { "quot" quotation }
+ { "elt" object }
+}
+{ $description "Outputs the greatest element of " { $snippet "seq" } " according to the " { $snippet "quot" } "." }
+{ $examples
+ "Example:"
+ { $example "USING: sequences prettyprint ;"
+ "{ { 1 2 } { 1 2 3 } { 1 2 3 4 } } [ length ] supremum-by ."
+ "{ 1 2 3 4 }"
+ }
+}
+{ $errors "Throws an error if the sequence is empty." } ;
+
+{ min max infimum infimum-by supremum supremum-by } related-words
+
+HELP: shortest
+{ $values { "seqs" sequence } { "elt" object } }
+{ $description "Outputs the shortest sequence from " { $snippet "seqs" } "." } ;
+
+HELP: longest
+{ $values { "seqs" sequence } { "elt" object } }
+{ $description "Outputs the longest sequence from " { $snippet "seqs" } "." } ;
+
+{ shortest longest } related-words
HELP: produce
{ $values { "pred" { $quotation ( ..a -- ..b ? ) } } { "quot" { $quotation ( ..b -- ..a obj ) } } { "seq" sequence } }
{ $description "Like " { $snippet "map sum" } ", but without creating an intermediate sequence." }
{ $examples
{ $example
- "USING: math math.ranges sequences prettyprint ;"
- "100 [1,b] [ sq ] map-sum ."
+ "USING: math ranges sequences prettyprint ;"
+ "100 [1..b] [ sq ] map-sum ."
"338350"
}
} ;
{ $description "Efficiently returns the number of elements that the predicate quotation matches." }
{ $examples
{ $example
- "USING: math math.ranges sequences prettyprint ;"
- "100 [1,b] [ even? ] count ."
+ "USING: math ranges sequences prettyprint ;"
+ "100 [1..b] [ even? ] count ."
"50"
}
} ;
{ $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." }
{ $examples
{ $example "! Find all the even numbers:" "USING: prettyprint sequences math kernel ;"
- "10 iota [ even? ] selector [ each ] dip ."
+ "10 <iota> [ even? ] selector [ each ] dip ."
"V{ 0 2 4 6 8 }"
}
}
{ $values
{ "seq" sequence }
{ "newseq" sequence } }
- { $description "Outputs a new sequence with all instance of " { $link f } " removed." }
+ { $description "Outputs a new sequence with all instances of " { $link f } " removed." }
{ $examples
{ $example "USING: prettyprint sequences ;"
"{ \"a\" 3 { } f } sift ."
HELP: 2map-reduce
{ $values
- { "seq1" sequence } { "seq2" sequence } { "map-quot" { $quotation ( ..a elt1 elt2 -- ..b intermediate ) } } { "reduce-quot" { $quotation ( ..b prev intermediate -- ..a next ) } }
+ { "seq1" sequence } { "seq2" sequence } { "map-quot" { $quotation ( ..a elt1 elt2 -- ..a intermediate ) } } { "reduce-quot" { $quotation ( ..a prev intermediate -- ..a next ) } }
{ "result" object } }
{ $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." }
{ $errors "Throws an error if the sequence is empty." }
{ $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 } "." }
{ $examples "Computing factorial:"
{ $example "USING: prettyprint sequences math ;"
- "40 iota rest-slice 1 [ * ] binary-reduce ."
+ "40 <iota> rest-slice 1 [ * ] binary-reduce ."
"20397882081197443358640281739902897356800000000" }
} ;
HELP: map-reduce
{ $values
- { "seq" sequence } { "map-quot" { $quotation ( ..a elt -- ..b intermediate ) } } { "reduce-quot" { $quotation ( ..b prev intermediate -- ..a next ) } }
+ { "seq" sequence } { "map-quot" { $quotation ( ..a elt -- ..a intermediate ) } } { "reduce-quot" { $quotation ( ..a prev intermediate -- ..a next ) } }
{ "result" object } }
{ $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." }
{ $errors "Throws an error if the sequence is empty." }
{ "newhash" integer } }
{ $description "An implementation word that computes a running hashcode of a sequence using some bit-twiddling. The resulting hashcode is always a fixnum." } ;
-HELP: short
+HELP: index-or-length
{ $values
{ "seq" sequence } { "n" integer } { "n'" integer } }
{ $description "Returns the input sequence and its length or " { $snippet "n" } ", whichever is less." }
{ $examples { $example "USING: sequences kernel prettyprint ;"
- "\"abcd\" 3 short [ . ] bi@"
+ "\"abcd\" 3 index-or-length [ . ] bi@"
"\"abcd\"\n3"
} } ;
"V{ 1 2 3 }"
} } ;
-HELP: iota
+HELP: <iota>
{ $values { "n" integer } { "iota" iota } }
{ $description "Creates an immutable virtual sequence containing the integers from 0 to " { $snippet "n-1" } "." }
{ $examples
{ $example
"USING: math sequences prettyprint ;"
- "3 iota [ sq ] map ."
+ "3 <iota> [ sq ] map ."
"{ 0 1 4 }"
}
} ;
}
} ;
+HELP: cartesian-find
+{ $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ? ) } } { "elt1" object } { "elt2" object } }
+{ $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." } ;
+
HELP: cartesian-each
{ $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... ) } } }
{ $description "Applies the quotation to every possible pairing of elements from the two sequences." } ;
{ $values { "seq1" sequence } { "seq2" sequence } { "quot" { $quotation ( ... elt1 elt2 -- ... newelt ) } } { "newseq" "a new sequence of sequences" } }
{ $description "Applies the quotation to every possible pairing of elements from the two sequences, collecting results into a new sequence of sequences." } ;
+HELP: cartesian-product-as
+{ $values { "seq1" sequence } { "seq2" sequence } { "exemplar" sequence } { "newseq" "a new sequence of sequences of pairs" } }
+{ $description "Outputs a sequence of all possible pairings of elements from the two sequences so that the output sequence is the exemplar's type." }
+{ $examples
+ { $example
+ "USING: bit-arrays prettyprint sequences ;"
+ "\"ab\" ?{ t f } { } cartesian-product-as ."
+ "{ { { 97 t } { 97 f } } { { 98 t } { 98 f } } }"
+ }
+} ;
+
HELP: cartesian-product
{ $values { "seq1" sequence } { "seq2" sequence } { "newseq" "a new sequence of sequences of pairs" } }
-{ $description "Outputs a sequence of all possible pairings of elements from the two sequences." }
+{ $description "Outputs a sequence of all possible pairings of elements from the two sequences, using the type of " { $snippet "seq2" } "." }
{ $examples
{ $example
"USING: prettyprint sequences ;"
"{ 1 2 } { 3 4 } cartesian-product ."
"{ { { 1 3 } { 1 4 } } { { 2 3 } { 2 4 } } }"
}
+ { $example
+ "USING: prettyprint sequences ;"
+ "\"abc\" \"def\" cartesian-product ."
+ "{ { \"ad\" \"ae\" \"af\" } { \"bd\" \"be\" \"bf\" } { \"cd\" \"ce\" \"cf\" } }"
+ }
} ;
+{ cartesian-find cartesian-each cartesian-map cartesian-product cartesian-product-as } related-words
+
ARTICLE: "sequences-unsafe" "Unsafe sequence operations"
"The " { $link nth-unsafe } " and " { $link set-nth-unsafe } " sequence protocol bypasses bounds checks for increased performance."
$nl
ARTICLE: "sequences-integers" "Counted loops"
"A virtual sequence is defined for iterating over integers from zero."
-{ $subsection iota }
-"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 } ":"
-{ $example "USING: sequences prettyprint ; 3 iota [ . ] each" "0\n1\n2" }
+{ $subsection <iota> }
+"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 } ":"
+{ $example "USING: sequences prettyprint ; 3 <iota> [ . ] each" "0\n1\n2" }
"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 } "."
$nl
-"Combinators that produce new sequences, such as " { $link map } ", will output an array if the input is an instance of " { $link iota } "."
+"Combinators that produce new sequences, such as " { $link map } ", will output an array if the input is an instance of " { $link <iota> } "."
$nl
-"More elaborate counted loops can be performed with " { $link "math.ranges" } "." ;
+"More elaborate counted loops can be performed with " { $link "ranges" } "." ;
ARTICLE: "sequences-if" "Control flow with sequences"
"To reduce the boilerplate of checking if a sequence is empty, several combinators are provided."
{ $subsections repetition <repetition> }
"Reversing a sequence:"
{ $subsections reverse }
-"A " { $emphasis "reversal" } " presents a reversed view of an underlying sequence:"
+"A " { $emphasis "reversed" } " is a virtual sequence presenting a reversed view of an underlying sequence:"
{ $subsections reversed <reversed> }
"Transposing a matrix:"
{ $subsections flip } ;
3append
3append-as
surround
+ surround-as
glue
+ glue-as
}
"Collapse a sequence unto itself:"
{ $subsections concat join }
{ $list
"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."
{ "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." }
- "Accessing elements from a concrete sequence (such as a string or an array) is often faster than accessing elements from a slice, because slice access entails additional indirection. However, in some cases, if the slice is immediately consumed by an iteration combinator, the compiler can eliminate the slice allocation and indirect altogether."
+ "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."
"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."
}
{ $heading "Subsequence operations" }
"Testing if a sequence contains an object:"
{ $subsections member? member-eq? }
"Testing if a sequence contains a subsequence:"
-{ $subsections head? tail? subseq? } ;
+{ $subsections head? tail? subseq? subseq-of? } ;
ARTICLE: "sequences-search" "Searching sequences"
"Finding the index of an element:"
last-index-from
}
"Finding the start of a subsequence:"
-{ $subsections start start* }
+{ $subsections
+ subseq-start
+ subseq-start-from
+ subseq-index
+ subseq-index-from
+ subseq-starts-at?
+}
"Finding the index of an element satisfying a predicate:"
{ $subsections
find
ARTICLE: "sequences-destructive" "Destructive sequence operations"
"Many operations have destructive variants that side effect an input sequence, instead of creating a new sequence:"
{ $table
- { "Constructive" "Destructive" }
+ { { $strong "Constructive" } { $strong "Destructive" } }
{ { $link suffix } { $link suffix! } }
{ { $link remove } { $link remove! } }
{ { $link remove-eq } { $link remove-eq! } }
{ $subsections
cartesian-each
cartesian-map
+ cartesian-find
}
"Computing the cartesian product of two sequences:"
{ $subsections
"Using sequences for looping:"
{ $subsections
"sequences-integers"
- "math.ranges"
+ "ranges"
}
"Using sequences for control flow:"
{ $subsections "sequences-if" }
projects / factor.git / blobdiff