4.15.1 Sequences
Sequence Constructors in The Racket Guide introduces sequences.
A sequence encapsulates an ordered collection of values. The elements of a sequence can be extracted with one of the for syntactic forms, with the procedures returned by sequence-generate, or by converting the sequence into a stream.
The sequence datatype overlaps with many other datatypes. Among built-in datatypes, the sequence datatype includes the following:
exact nonnegative integers (see below)
strings (see Strings)
byte strings (see Byte Strings)
lists (see Pairs and Lists)
mutable lists (see Mutable Pairs and Lists)
vectors (see Vectors)
flvectors (see Flonum Vectors)
fxvectors (see Fixnum Vectors)
hash tables (see Hash Tables)
dictionaries (see Dictionaries)
sets (see Sets)
input ports (see Ports)
streams (see Streams)
An exact number k that is a non-negative integer acts as a sequence similar to (in-range k), except that k by itself is not a stream.
Custom sequences can be defined using structure type properties. The easiest method to define a custom sequence is to use the gen:stream generic interface. Streams are a suitable abstraction for data structures that are directly iterable. For example, a list is directly iterable with first and rest. On the other hand, vectors are not directly iterable: iteration has to go through an index. For data structures that are not directly iterable, the iterator for the data structure can be defined to be a stream (e.g., a structure containing the index of a vector).
For example, unrolled linked lists (represented as a list of vectors) themselves do not fit the stream abstraction, but have index-based iterators that can be represented as streams:
> (struct unrolled-list-iterator (idx lst) #:methods gen:stream [(define (stream-empty? iter) (define lst (unrolled-list-iterator-lst iter)) (or (null? lst) (and (>= (unrolled-list-iterator-idx iter) (vector-length (first lst))) (null? (rest lst))))) (define (stream-first iter) (vector-ref (first (unrolled-list-iterator-lst iter)) (unrolled-list-iterator-idx iter))) (define (stream-rest iter) (define idx (unrolled-list-iterator-idx iter)) (define lst (unrolled-list-iterator-lst iter)) (if (>= idx (sub1 (vector-length (first lst)))) (unrolled-list-iterator 0 (rest lst)) (unrolled-list-iterator (add1 idx) lst)))])
> (define (make-unrolled-list-iterator ul) (unrolled-list-iterator 0 (unrolled-list-lov ul)))
> (struct unrolled-list (lov) #:property prop:sequence make-unrolled-list-iterator) > (define ul1 (unrolled-list '(#(cracker biscuit) #(cookie scone)))) > (for/list ([x ul1]) x) '(cracker biscuit cookie scone)
The prop:sequence property provides more flexibility in specifying iteration, such as when a pre-processing step is needed to prepare the data for iteration. The make-do-sequence function creates a sequence given a thunk that returns procedures to implement a sequence, and the prop:sequence property can be associated with a structure type to implement its implicit conversion to a sequence.
For most sequence types, extracting elements from a sequence has no side-effect on the original sequence value; for example, extracting the sequence of elements from a list does not change the list. For other sequence types, each extraction implies a side effect; for example, extracting the sequence of bytes from a port causes the bytes to be read from the port. A sequence’s state may either span all uses of the sequence, as for a port, or it may be confined to each distinct time that a sequence is initiated by a for form, sequence->stream, sequence-generate, or sequence-generate*. Concretely, the thunk passed to make-do-sequence is called to initiate the sequence each time the sequence is used.
Individual elements of a sequence typically correspond to single
values, but an element may also correspond to multiple values. For
example, a hash table generates two values—
4.15.1.1 Sequence Predicate and Constructors
procedure
end : real? (in-range start end [step]) → stream? start : real? end : real? step : real? = 1
When given zero as step, in-range returns an infinite sequence. It may also return infinite sequences when step is a very small number, and either step or the sequence elements are floating-point numbers.
procedure
(in-naturals [start]) → stream?
start : exact-nonnegative-integer? = 0
> (for/list ([k (in-naturals)] [x (in-range 10)]) (list k x)) '((0 0) (1 1) (2 2) (3 3) (4 4) (5 5) (6 6) (7 7) (8 8) (9 9))
See Pairs and Lists for information on using lists as sequences.
Changed in version 6.7.0.4 of package base: Improved element-reachability guarantee for lists in for.
See Mutable Pairs and Lists for information on using mutable lists as sequences.
> (for/list ([x (in-mlist (mcons "RACKET" (mcons "LANG" '())))]) (string-length x)) '(6 4)
procedure
vec : vector? start : exact-nonnegative-integer? = 0 stop : (or/c exact-integer? #f) = #f step : (and/c exact-integer? (not/c zero?)) = 1
See Vectors for information on using vectors as sequences.
The optional arguments start, stop, and step are analogous to in-range, except that a #f value for stop is equivalent to (vector-length vec). That is, the first element in the sequence is (vector-ref vec start), and each successive element is generated by adding step to index of the previous element. The sequence stops before an index that would be greater or equal to end if step is non-negative, or less or equal to end if step is negative.
If start is not a valid index, then the exn:fail:contract exception is raised, except when start, stop, and (vector-length vec) are equal, in which case the result is an empty sequence.
> (for ([x (in-vector (vector 1) 1)]) x) > (for ([x (in-vector (vector 1) 2)]) x) in-vector: starting index is out of range
starting index: 2
valid range: [0, 0]
vector: '#(1)
> (for ([x (in-vector (vector) 0 0)]) x) > (for ([x (in-vector (vector 1) 1 1)]) x)
If stop is not in [-1, (vector-length vec)], then the exn:fail:contract exception is raised.
If start is less than stop and step is negative, then the exn:fail:contract exception is raised. Similarly, if start is more than stop and step is positive, then the exn:fail:contract exception is raised.
An in-vector application can provide better performance for vector iteration when it appears directly in a for clause.
> (define (histogram vector-of-words) (define a-hash (make-hash)) (for ([word (in-vector vector-of-words)]) (hash-set! a-hash word (add1 (hash-ref a-hash word 0)))) a-hash) > (histogram #("hello" "world" "hello" "sunshine")) '#hash(("hello" . 2) ("sunshine" . 1) ("world" . 1))
procedure
str : string? start : exact-nonnegative-integer? = 0 stop : (or/c exact-integer? #f) = #f step : (and/c exact-integer? (not/c zero?)) = 1
See Strings for information on using strings as sequences.
The optional arguments start, stop, and step are as in in-vector.
An in-string application can provide better performance for string iteration when it appears directly in a for clause.
> (define (line-count str) (for/sum ([ch (in-string str)]) (if (char=? #\newline ch) 1 0))) > (line-count "this string\nhas\nthree \nnewlines") 3
procedure
bstr : bytes? start : exact-nonnegative-integer? = 0 stop : (or/c exact-integer? #f) = #f step : (and/c exact-integer? (not/c zero?)) = 1
See Byte Strings for information on using byte strings as sequences.
The optional arguments start, stop, and step are as in in-vector.
An in-bytes application can provide better performance for byte string iteration when it appears directly in a for clause.
> (define (has-eof? bs) (for/or ([ch (in-bytes bs)]) (= ch 0))) > (has-eof? #"this byte string has an \0embedded zero byte") #t
> (has-eof? #"this byte string does not") #f
procedure
r : (input-port? . -> . any/c) = read in : input-port? = (current-input-port)
procedure
(in-input-port-bytes in) → sequence?
in : input-port?
procedure
(in-input-port-chars in) → sequence?
in : input-port?
procedure
in : input-port? = (current-input-port)
mode : (or/c 'linefeed 'return 'return-linefeed 'any 'any-one) = 'any
procedure
(in-bytes-lines [in mode]) → sequence?
in : input-port? = (current-input-port)
mode : (or/c 'linefeed 'return 'return-linefeed 'any 'any-one) = 'any
If bad-index-v is supplied, then bad-index-v is returned as both the key and the value in the case that the hash is modified concurrently so that iteration does not have a valid hash index. Providing bad-index-v is particularly useful when iterating through a hash table with weakly held keys, since entries can be removed asynchronously (i.e., after in-hash has committed to another iteration, but before it can access the entry for the next iteration).
> (define table (hash 'a 1 'b 2))
> (for ([(key value) (in-hash table)]) (printf "key: ~a value: ~a\n" key value))
key: b value: 2
key: a value: 1
See Hash Tables for information on using hash tables as sequences.
Changed in version 7.0.0.10 of package base: Added the optional bad-index-v argument.
procedure
(in-hash-keys hash) → sequence?
hash : hash? (in-hash-keys hash bad-index-v) → sequence? hash : hash? bad-index-v : any/c
> (define table (hash 'a 1 'b 2))
> (for ([key (in-hash-keys table)]) (printf "key: ~a\n" key))
key: b
key: a
Changed in version 7.0.0.10 of package base: Added the optional bad-index-v argument.
procedure
(in-hash-values hash) → sequence?
hash : hash? (in-hash-values hash bad-index-v) → sequence? hash : hash? bad-index-v : any/c
> (define table (hash 'a 1 'b 2))
> (for ([value (in-hash-values table)]) (printf "value: ~a\n" value))
value: 2
value: 1
Changed in version 7.0.0.10 of package base: Added the optional bad-index-v argument.
procedure
(in-hash-pairs hash) → sequence?
hash : hash? (in-hash-pairs hash bad-index-v) → sequence? hash : hash? bad-index-v : any/c
The bad-index-v argument, if supplied, is used in the same way as by in-hash. When an invalid index is encountered, the pair in the sequence with have bad-index-v as both its car and cdr.
> (define table (hash 'a 1 'b 2))
> (for ([key+value (in-hash-pairs table)]) (printf "key and value: ~a\n" key+value))
key and value: (b . 2)
key and value: (a . 1)
Changed in version 7.0.0.10 of package base: Added the optional bad-index-v argument.
Added in version 6.4.0.6 of package base.
Changed in version 7.0.0.10: Added the optional bad-index-v argument.
procedure
(in-directory [dir use-dir?]) → sequence?
dir : (or/c #f path-string?) = #f
use-dir? : ((and/c path? complete-path?) . -> . any/c) = (lambda (dir-path) #t)
An in-directory sequence traverses nested subdirectories recursively (filtered by use-dir?). To generate a sequence that includes only the immediate content of a directory, use the result of directory-list as a sequence.
The immediate content of each directory is reported as sorted by path<?, and the content of a subdirectory is reported before subsequent paths within the directory.
> (current-directory (collection-path "info"))
> (for/list ([f (in-directory)]) f)
'(#<path:compiled>
#<path:compiled/main_rkt.dep>
#<path:compiled/main_rkt.zo>
#<path:main.rkt>)
> (for/list ([f (in-directory "compiled")]) f) '(#<path:main_rkt.dep> #<path:main_rkt.zo>)
> (for/list ([f (in-directory "compiled")]) f) '(#<path:compiled/main_rkt.dep> #<path:compiled/main_rkt.zo>)
> (for/list ([f (in-directory #f (lambda (p) (not (regexp-match? #rx"compiled" p))))]) f) '(#<path:main.rkt> #<path:compiled>)
Changed in version 6.0.0.1 of package base: Added use-dir? argument.
Changed in version 6.6.0.4: Added guarantee of sorted results.
procedure
(in-producer producer) → sequence?
producer : procedure? (in-producer producer stop arg ...) → sequence? producer : procedure? stop : any/c arg : any/c
If a stop value is not given, the sequence goes on infinitely, and therefore it common to use it with a finite sequence or using #:break etc. If a stop value is given, it is used to identify a value that marks the end of the sequence (and the stop value is not included in the sequence); stop can be a predicate that is applied to the results of producer, or it can be a value that is tested against the result of with eq?. (The stop argument must be a predicate if the stop value is itself a function or if producer returns multiple values.)
If additional args are specified, they are passed to every call to producer.
> (define (counter) (define n 0) (lambda ([d 1]) (set! n (+ d n)) n)) > (for/list ([x (in-producer (counter))] [y (in-range 4)]) x) '(1 2 3 4)
> (for/list ([x (in-producer (counter))] #:break (= x 5)) x) '(1 2 3 4)
> (for/list ([x (in-producer (counter) 5)]) x) '(1 2 3 4)
> (for/list ([x (in-producer (counter) 5 1/2)]) x) '(1/2 1 3/2 2 5/2 3 7/2 4 9/2)
> (for/list ([x (in-producer read eof (open-input-string "1 2 3"))]) x) '(1 2 3)
procedure
(in-indexed seq) → sequence?
seq : sequence?
procedure
(in-sequences seq ...) → sequence?
seq : sequence?
procedure
(in-parallel seq ...) → sequence?
seq : sequence?
procedure
(in-values-sequence seq) → sequence?
seq : sequence?
procedure
(in-values*-sequence seq) → sequence?
seq : sequence?
procedure
(make-do-sequence thunk) → sequence?
thunk :
(or/c (-> (values (any/c . -> . any) (any/c . -> . any/c) any/c (or/c (any/c . -> . any/c) #f) (or/c (() () #:rest list? . ->* . any/c) #f) (or/c ((any/c) () #:rest list? . ->* . any/c) #f))) (-> (values (any/c . -> . any) (or/c (any/c . -> . any/c) #f) (any/c . -> . any/c) any/c (or/c (any/c . -> . any/c) #f) (or/c (() () #:rest list? . ->* . any/c) #f) (or/c ((any/c) () #:rest list? . ->* . any/c) #f))))
The first result is a pos->element procedure that takes the current position and returns the value(s) for the current element.
The optional second result is an early-next-pos procedure that is described further below. Alternatively, the optional second result can be #f, which is equivalent to the identity function.
The third (or second) result is a next-pos procedure that takes the current position and returns the next position.
The fourth (or third) result is the initial position.
The fifth (or fourth) result is a continue-with-pos? function that takes the current position and returns a true result if the sequence includes the value(s) for the current position, and false if the sequence should end instead of including the value(s). Alternatively, the fifth (or fourth) result can be #f to indicate that the sequence should always include the current value(s). This function is checked on each position before pos->element is used.
The sixth (or fifth) result is a continue-with-val? function that is like the fourth result, but it takes the current element value(s) instead of the current position. Alternatively, the sixth (or fifth) result can be #f to indicate that the sequence should always include the value(s) at the current position.
The seventh (or sixth) result is a continue-after-pos+val? procedure that takes both the current position and the current element value(s) and determines whether the sequence ends after the current element is already included in the sequence. Alternatively, the seventh (or sixth) result can be #f to indicate that the sequence can always continue after the current value(s).
The early-next-pos procedure, which is the optional second result, takes the current position and returns an updated position. This updated position is used for next-pos and continue-after-pos+val?, but not with continue-with-pos? (which uses the original current position). The intent of early-next-pos is to support a sequence where the position must be incremented to avoid keeping a value reachable while a loop processes the sequence value, so early-next-pos is applied just after pos->element.
Each of the procedures listed above is called only once per position. Among the last three procedures, as soon as one of the procedures returns #f, the sequence ends, and none are called again. Typically, one of the functions determines the end condition, and #f is used in place of the other two functions.
Changed in version 6.7.0.4 of package base: Added support for the optional second result.
Using a pre-existing sequence:
> (struct my-set (table) #:property prop:sequence (lambda (s) (in-hash-keys (my-set-table s))))
> (define (make-set . xs) (my-set (for/hash ([x (in-list xs)]) (values x #t))))
> (for/list ([c (make-set 'celeriac 'carrot 'potato)]) c) '(potato celeriac carrot)
Using make-do-sequence:
> (define-struct train (car next) #:property prop:sequence (lambda (t) (make-do-sequence (lambda () (values train-car train-next t (lambda (t) t) (lambda (v) #t) (lambda (t v) #t))))))
> (for/list ([c (make-train 'engine (make-train 'boxcar (make-train 'caboose #f)))]) c) '(engine boxcar caboose)
4.15.1.2 Sequence Conversion
procedure
(sequence->stream seq) → stream?
seq : sequence?
If extracting an element from seq involves a side-effect, then the effect is performed each time that either stream-first or stream-rest is first used to access or skip an element.
procedure
(sequence-generate* seq)
→
(or/c list? #f) (-> (values (or/c list? #f) procedure?)) seq : sequence?
4.15.1.3 Additional Sequence Operations
| (require racket/sequence) | package: base |
value
procedure
(sequence->list s) → list?
s : sequence?
procedure
s : sequence?
procedure
(sequence-ref s i) → any
s : sequence? i : exact-nonnegative-integer?
procedure
(sequence-tail s i) → sequence?
s : sequence? i : exact-nonnegative-integer?
In case initiating s involves a side effect, the sequence s is not initiated until the resulting sequence is initiated, at which point the first i elements are extracted from the sequence.
procedure
(sequence-append s ...) → sequence?
s : sequence?
If all given ss are streams, the result is also a stream.
procedure
(sequence-map f s) → sequence?
f : procedure? s : sequence?
If s is a stream, then the result is also a stream.
procedure
f : procedure? s : sequence?
If s is a stream, then the result is also a stream.
procedure
(sequence-add-between s e) → sequence?
s : sequence? e : any/c
If s is a stream, then the result is also a stream.
> (let* ([all-reds (in-cycle '("red"))] [red-and-blues (sequence-add-between all-reds "blue")]) (for/list ([n (in-range 10)] [elt red-and-blues]) elt)) '("red" "blue" "red" "blue" "red" "blue" "red" "blue" "red" "blue")
> (for ([text (sequence-add-between '("veni" "vidi" "duci") ", ")]) (display text)) veni, vidi, duci
procedure
(sequence/c [ #:min-count min-count] elem/c ...) → contract? min-count : (or/c #f exact-nonnegative-integer?) = #f elem/c : contract?
If min-count is a number, the stream is required to have at least that many elements in it.
> (define/contract predicates (sequence/c (-> any/c boolean?)) (in-list (list integer? string->symbol)))
> (for ([P predicates]) (printf "~s\n" (P "cat"))) #f
predicates: broke its own contract
promised: boolean?
produced: 'cat
in: an element of
(sequence/c (-> any/c boolean?))
contract from: (definition predicates)
blaming: (definition predicates)
(assuming the contract is correct)
at: eval:29.0
> (define/contract numbers&strings (sequence/c number? string?) (in-dict (list (cons 1 "one") (cons 2 "two") (cons 3 'three))))
> (for ([(N S) numbers&strings]) (printf "~s: ~a\n" N S))
1: one
2: two
numbers&strings: broke its own contract
promised: string?
produced: 'three
in: an element of
(sequence/c number? string?)
contract from: (definition numbers&strings)
blaming: (definition numbers&strings)
(assuming the contract is correct)
at: eval:31.0
> (define/contract a-sequence (sequence/c #:min-count 2 char?) "x")
> (for ([x a-sequence] [i (in-naturals)]) (printf "~a is ~a\n" i x)) 0 is x
a-sequence: broke its own contract
promised: a sequence that contains at least 2 values
produced: "x"
in: (sequence/c #:min-count 2 char?)
contract from: (definition a-sequence)
blaming: (definition a-sequence)
(assuming the contract is correct)
at: eval:33.0
4.15.1.3.1 Additional Sequence Constructors
> (for/list ([x (in-syntax #'(1 2 3))]) x) '(#<syntax:eval:35:0 1> #<syntax:eval:35:0 2> #<syntax:eval:35:0 3>)
Added in version 6.3 of package base.
procedure
length : exact-positive-integer? seq : sequence?
Added in version 6.3 of package base.