gauche.sequence- Sequence framework
Provides a generic operations on sequences. A sequence is a collection with ordered elements. Besides all the operations applicable on collections, you can associate integer index to each element, and apply order-aware operations on the elements.
This module inherits
gauche.collection (see Collection framework).
All the collection generic operations can be applied to a sequence as well.
Among Gauche builtin class, lists, vectors and strings are sequences and the specialized methods are defined for them. Other extension types, such as SRFI-4 uniform vector, have the methods as well.
|• Fundamental sequence accessors:|
|• Slicing sequence:|
|• Mapping over sequences:|
|• Other operations over sequences:|
|• Implementing sequence:|
Returns index-th element of the sequence seq. This method enables uniform access for any sequence types.
When index is less than zero, or greater than or equal to the size of the sequence, fallback is returned if provided, or an error is signaled if not.
(ref '(a b c) 1) ⇒ b (ref '#(a b c) 1) ⇒ b (ref "abc" 1) ⇒ #\b
Sets value to the index-th element of the sequence seq. This is the uniform sequence modifier.
Note: Some sequences may not support arbitrary modification by index. For example, if you have a sequence representing a set of sorted integers, you cannot modify i-th element with arbitrary value. Yet such sequence may provide other means of modification, such as inserting or deleting elements.
(let ((x (list 'a 'b 'c))) (set! (ref x 1) 'z) x) ⇒ (a z c) (let ((x (vector 'a 'b 'c))) (set! (ref x 1) 'z) x) ⇒ #(a z c) (let ((x (string #\a #\b #\c))) (set! (ref x 1) #\z) x) ⇒ "azc"
Retrieve a subsequence of the sequence seq, from start-th element (inclusive) to end-th element (exclusive). If end is omitted, up to the end of sequence is taken. The type of the returned sequence is the same as seq.
(subseq '(a b c d e) 1 4) ⇒ (b c d) (subseq '#(a b c d e) 1 4) ⇒ #(b c d) (subseq "abcde" 1 4) ⇒ "bcd" (subseq '(a b c d e) 3) ⇒ (d e)
Sets the elements of value-seq from the start-th element (inclusive) to the end-th element (exclusive) of the sequence seq. Value-seq can be any sequence, but its size must be larger than (end - start).
In the second form, end is figured out by the length of value-seq.
(define s (vector 'a 'b 'c 'd 'e)) (set! (subseq s 1 4) '(4 5 6)) s ⇒ #(a 4 5 6 e) (set! (subseq s 0) "ab") s ⇒ #(#\a #\b 5 6 e)
You can use extended
for-each and other
generic functions on sequences, since a sequence is also a collection.
However, sometimes you want to have index as well as the element itself
during iteration. There are several generic functions for it.
fold, except kons is given
the index within seq, as the first argument,
as well as each element from seqs and the accrued value.
(fold-with-index acons '() '(a b c)) ⇒ ((2 . c) (1 . b) (0 . a))
for-each, except proc
receives the index as the first argument.
(map-with-index list '(a b c d) '(e f g h)) ⇒ ((0 a e) (1 b f) (2 c g) (3 d h)) (map-to-with-index <vector> cons '(a b c d)) ⇒ #((0 . a) (1 . b) (2 . c) (3 . d))
Finds the first element in seq that satisfies pred
find, but returns two values, the index of the element
and the element itself. If no element satisfies pred,
#f’s are returned.
(find-with-index char-upper-case? "abraCadabra") ⇒ 4 and #\C (find-with-index char-numeric? "abraCadabra") ⇒ #f and #f
find, but returns the index of the first element
that satisfies pred in seq, instead of the element itself.
If no element in seq satisfies pred,
#f is returned.
(find-index char-upper-case? "abraCadabra") ⇒ 4 (find-index char-numeric? "abraCadabra") ⇒ #f
list-index in SRFI-1 (see SRFI-1 List utilities).
fold-right on lists.
fold, this method applies a higher-order function
kons over given sequence(s), passing the "seed" value
whose default is knil. The difference between
fold-right is the associative order of elements on
which kons is applied.
When we have one sequence,
[E0, E1, ..., En],
fold-right work as follows, respectively.
fold: (kons En (kons En-1 (kons ... (kons E1 (kons E1 knil)) ...))) fold-right (kons E0 (kons E1 (kons ... (kons En-1 (kons En knil)) ...)))
This method isn’t defined on
collections don’t care the order of elements.
Both needle and haystack must be sequences.
Searches needle from haystack from the beginning of haystack.
If needle is found, the index in haystack where it begins is
#f is returned. The keyword argument
test is used to compare elements; its defaule is
(sequence-contains '#(a b r a c a d a b r a) '#(b r a)) ⇒ 1 (sequence-contains '#(a b r a c a d a b r a) '#(c r a)) ⇒ #f
This can be regarded as generalization of
string-contains in srfi-13
(see SRFI-13 String searching).
Searches a sequence needle from list,
and if found, breaks list
to two parts—the prefix of list up to right befor needle
begins, and the rest—and returns them.
List must be a list, but needle can be any sequence.
Elements are compared by test, defaulted to
(break-list-by-sequence '(a b r a c a d a b r a) '(c a d)) ⇒ (a b r a) and (c a d a b r a)
If needle isn’t found in list, it returns list itself
(). This behavior is aligned to
(see SRFI-1 List utilities), which split a list by predicate but
returns the whole list if split condition isn’t met.
(break-list-by-sequence '(a b r a c a d a b r c a) '(c a z)) ⇒ (a b r a c a d a b r c a) and ()
The linear update version
modifies list to create the return value if necessary,
so list must be mutable. The caller must use the return
value instead of relying on side-effects, though,
for list may not be modified.
This is an internal routine to search subsequence (needle) inside
larger sequence, using Knuth-Morris-Pratt (KMP) algorithm.
It is used in
Returns a procedure that performs one step of KMP search.
The procedure takes two arguments, an element elt
and an index k. It compares elt with
(~ needle k), and returns two values—the next index and
a flag indicating the match is completed. When the match is
completed, the next index is equal to the length of needle.
As an edge case, if needle is an empty sequence,
Elements are compared using test, which is defaulted to
The following is a skeleton of searcher using
sequence->kmp-stepper. Here we assume haystack
is a list, and we just return whether the needle is
found or not, or needle is empty; you might want to carry
around other info in the loop (e.g.
tracks the current index of haystack in order to
return the found index.)
(if-let1 stepper (sequence->kmp-stepper needle) (let loop ([haystack haystack] [k 0]) (if (null? haystack) 'not-found (receive (k found) (stepper (car haystack) k) ; KMP step (if found 'found (loop (cdr kaystack) k))))) 'needle-is-empty)
Note that selection and searching methods for collections can also be applied to sequences. See Selection and searching in collection.
Groups consecutive elements in a sequence seq which
have the common key value. A key value of an element is
obtained by applying the procedure key to the element;
the default procedure is
For each element in seq, key is applied exactly once.
The equal-ness of keys are compared by test procedure,
whose default is
(group-sequence '(1 1 1 2 3 4 4 2 2 3 1 1 3)) ⇒ ((1 1 1) (2) (3) (4 4) (2 2) (3) (1 1) (3)) (group-sequence '(1 1 1 2 3 4 4 2 2 3 1 1 3) :key (cut modulo <> 2))) ⇒ ((1 1 1) (2) (3) (4 4 2 2) (3 1 1 3)) (group-sequence '#("a" "a" "b" "b" "c" "d" "d") :test string=?) ⇒ (("a" "a") ("b" "b") ("c") ("d" "d")) (group-sequence "aabbcdd" :test char=?) ⇒ ((#\a #\a) (#\b #\b) (#\c) (#\d #\d))
This method is similar to Haskell’s
If you want to group elements that are not adjacent,
(see Selection and searching in collection).
Returns a new sequence of the same type of a which contains the common prefix of sequences a and b. The types of a and b doesn’t need to match. The type of a must have a builder.
For each corresponding element in a and b, the key
procedure is applied (default
identity), then compared with
test procedure (default
(common-prefix '(a b c d e) '(a b c e f)) ⇒ (a b c) (common-prefix "abcef" '#(#\a #\b #\c #\d #\e)) ⇒ "abc"
srfi-13 has a specific function with
(see SRFI-13 String Prefixes & Suffixes).
Returns a new sequence of the type class which contains the common prefix of sequences a and b. The types of a and b doesn’t need to match, and neither needs to have a builder. The class must be a sequence class with a builder.
The meanings of keyword arguments are the same as
(common-prefix-to <list> "abcde" "ABCEF" :test char-ci=?) ⇒ '(#\a #\b #\c)
Returns a newly created sequence of the same type as src, in which the elements are permuted from src according to permuter.
Permuter is a sequence of exact integers. When the k-th element
of permuter is i, the k-th element of the result
(ref src i). Therefore, the size of the result
sequence is the same as the size of permuter. Permuter
can be any kind of sequence, unrelated to the type of src.
It is allowed that the same index i can appear more than once in permuter.
(permute '(a b c d) '(3 2 0 1)) ⇒ (d c a b) (permute '(a b c d) '(0 2)) ⇒ (a c) (permute '(a b c d) '(0 0 1 1 2 2)) ⇒ (a a b b c c)
If an integer in permuter is out of the valid range as the index
of src, then an error is signaled unless fallback is given.
If fallback is given, what value is used depends on the result of
(ref src i fallback)—which usually returns
fallback for the out-of-range index i.
(permute '#(a b c) '(3 2 1 0) 'foo) ⇒ #(foo c b a) (permute "!,HWdelor" #(2 5 6 6 7 1 -1 3 7 8 6 4 0) #\space) ⇒ "Hello, World!"
permute, but the result will be an instance of the given class
instead of the class of src.
(permute-to <string> '(#\a #\b #\c #\d #\r) '(0 1 4 0 2 0 3 0 1 4 0)) ⇒ "abracadabra"
permute, but the result is stored back to src.
Src must be a mutable sequence, and the length of src and
permuter must be the same.
Returns a new sequence of the same type and size as src, in which elements are randomly permuted.
(shuffle '(a b c d e)) ⇒ (e b d c a) (shuffle "abcde") ⇒ "bacde"
This generic function uses
srfi-27 (see Sources of random bits).
By default it uses
default-random-source, but you can pass
an alternative random source by the optional argument.
shuffle, except that the result will be an instance of
class instead of the class of src.
shuffle, but the result is stored back to src.
Src must be a mutable sequence.