-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
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
{ $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\""
}
}
}
} ;
+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: 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" } "." }
{ 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 ."
"{ }"
}
}
}
"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 }"
}
}
{ tail tail* tail-slice tail-slice* } related-words
{ head head* head-slice head-slice* } related-words
-{ cut cut* cut-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
{ 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: subseq-start-from
-{ $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: 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" "a start index" } }
+{ $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: 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 { "seq" sequence } { "elt" object } }
-{ $description "Outputs the shortest element of " { $snippet "seq" } "." } ;
+{ $values { "seqs" sequence } { "elt" object } }
+{ $description "Outputs the shortest sequence from " { $snippet "seqs" } "." } ;
HELP: longest
-{ $values { "seq" sequence } { "elt" object } }
-{ $description "Outputs the longest element of " { $snippet "seq" } "." } ;
+{ $values { "seqs" sequence } { "elt" object } }
+{ $description "Outputs the longest sequence from " { $snippet "seqs" } "." } ;
{ shortest longest } related-words
{ $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"
}
} ;
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." }
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"
} } ;
}
} ;
+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
$nl
"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 }
"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 subseq-start subseq-start-from }
+{ $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" }