For Development HEAD DRAFTSearch (procedure/syntax/module):

Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

12.92 util.stream - Stream library

Module: util.stream

This module provides a library of lazy streams, including the functions and syntaxes defined in SRFI-40 and SRFI-41, the latter of which became a part of R7RS large (as (scheme stream),

Gauche has a built-in lazy sequences (see Lazy sequences), which is a lazy stream integrated to a list so that you can use all list procedures on it. Lazy streams provided in this module are somewhat heavier than lazy sequences and you need to use special procedures, but it is strictly lazy (while a lazy sequence evaluates one element ahead) and portable.


12.92.1 Stream primitives

Function: stream? obj

[R7RS stream] {util.stream} Returns #t iff obj is a stream created by a procedure of util.stream.

Variable: stream-null

[R7RS stream] {util.stream} The singleton instance of NULL stream.

Macro: stream-cons object stream

[R7RS stream] {util.stream} A fundamental constructor of a stream. Adds object to the head of a stream, and returns a new stream.

Function: stream-null? obj

[R7RS stream] {util.stream} Returns #t iff obj is the null stream.

Function: stream-pair? obj

[R7RS stream] {util.stream} Returns #t iff obj is a non-null stream.

Function: stream-car s

[R7RS stream] {util.stream} Returns the first element of the stream s.

Function: stream-cdr s

[R7RS stream] {util.stream} Returns the remaining elements of the stream s, as a stream.

Macro: stream-delay expr

[SRFI-40]{util.stream} Returns a stream which is a delayed form of expr.

As a rule of thumb, any stream-producing functions should wrap the resulting expression by stream-delay. (Or you can use stream-lambda, stream-let or stream-define, described below.)

Macro: stream-lambda formals body body2 …

[R7RS stream] {util.stream} A convenience macro to create a function that returns a stream. Effectively, (stream-lambda formals body body2 …) is the same as (lambda formals (stream-delay body body2 …)).


12.92.2 Stream constructors

Function: stream obj …

[SRFI-40]{util.stream} Returns a new stream whose elements are obj ….

Note: This differs from SRFI-41’s (scheme.stream’s) stream, which is a macro so that arguments are lazily evaluated. SRFI-41’s stream is provided as stream+ in this module.

(stream 1 2 3))     ⇒ a stream that contains (1 2 3)
(stream 1 (/ 1 0))) ⇒ error
Macro: stream+ expr …

{util.stream} Returns a new stream whose elements are the result of expr ….

This is the same as SRFI-41(scheme.stream)’s stream. Each expr isn’t evaluated until it is accessed.

(define s (stream+ 1 (/ 1 0)))  ;; doesn't yield an error

(stream-car s)  ⇒ 1

(stream-cadr s) ⇒ error
Function: stream-unfold f p g seed

[R7RS stream] {util.stream} Creates a new stream whose element is determined as follows:

  • A “go” predicate p is called on the current seed value. If it yields #f, the stream terminates.
  • Otherwise, (f s) is the element of the stream, and (g s) becomes the next seed value, where s is the current seed value. The initial seed value is given by seed.

Note: Unfortunately, the order of arguments differs from other *-unfold procedures, which takes p f g (predicate, value-generator and seed-generator). Furthermore, the predicate is stop-predicate (returning true stops iteration).

(stream->list
 (stream-unfold integer->char (cut < <> 58) (cut + 1 <>) 48))
 ⇒ (#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)
Function: stream-unfoldn f seed n

[SRFI-40]{util.stream} Creates n streams related each other, whose contents are generated by f and seed.

The f is called with the current seed value, and returns n+1 values:

(f seed)
  => seed result_0 result_1 … result_n-1

The first value is to be the next seed value. Result_k must be one of the following forms:

(val)

val will be the next car of k-th stream.

#f

No new information for k-th stream.

()

The end of k-th stream has been reached.

The following example creates two streams, the first one produces an infinite series of odd numbers and the second produces evens.

gosh> (define-values (s0 s1)
        (stream-unfoldn (lambda (i)
                          (values (+ i 2)          ;; next seed
                                  (list i)         ;; for the first stream
                                  (list (+ i 1)))) ;; for the second stream
                        0 2))
#<undef>
gosh> (stream->list (stream-take s0 10))
(0 2 4 6 8 10 12 14 16 18)
gosh> (stream->list (stream-take s1 10))
(1 3 5 7 9 11 13 15 17 19)
Function: stream-unfolds f seed

[R7RS stream] {util.stream} Like stream-unfoldn, but the number of created streams is determined by the number fo return values from f. See stream-unfoldn above for the details.

Function: stream-constant obj …

[R7RS stream] {util.stream} Returns an infinite stream that repeats obj ….

(stream->list 10 (stream-constant 1 2))
  ⇒ (1 2 1 2 1 2 1 2 1 2)
Function: make-stream n :optional init

{util.stream} Creates a new stream of n elements of init. If init is omitted, #f is used. Specifying a negative number to n creates an infinite stream.

Function: stream-tabulate n init-proc

{util.stream} Creates a new stream of n elements. The k-th element is obtained by applying init-proc to k. Specifying a negative number to n creates an infinite stream.

Function: stream-iota :optional count start step

{util.stream} Creates a new stream of numbers, starting from start and incrementing step. The length of stream is maximum integer not greater than nonnegative real number count. The default values of count, start and step are +inf.0, 0 and 1, respectively.

If start and step are exact, and count is exact or infinite, a sequence of exact numbers are created. Otherwise, a sequence of inexact numbers are created.

Function: stream-range start :optional end step

[R7RS stream] {util.stream} Creates a new stream of real numbers, starting from start and stops before end, stepping by step. If end is omitted, positive infinity is assumed. If step is omitted, 1 is assumed if end is greater than start, and -1 if end is less than start.

The generated numbers are exact if start and step are exact and end is either exact or infinite. Otherwise, inexact numbers are generated.

In R7RS scheme.stream, end argument is required.

(stream->list (stream-range 0 10))
 ⇒ (0 1 2 3 4 5 6 7 8 9)
Function: stream-from start :optional step

[R7RS stream] {util.stream} This is yet another number sequence generator. Generates an infinite sequence whose i-th element is (+ start (* i step)). If step is omitted, 1 is assumed. If both start and step are exact, exact numbers are generated. Otherwise, inexact numbers are generated.

Function: stream-iterate f seed

[R7RS stream] {util.stream} Returns a stream starting from seed, and each successive element is calculated by (f s) where s is the previous element.

(stream->list 5 (stream-iterate (cut cons 'x <>) '()))
  ⇒ (() (x) (x x) (x x x) (x x x x))

See also literate in gauche.lazy (see gauche.lazy - Lazy sequence utilities).

Function: stream-xcons a b

{util.stream} (stream-cons b a). Just for convenience.

Function: stream-cons* elt … stream

{util.stream} Creates a new stream which appends elt … before stream.

Function: list->stream list

[R7RS stream] {util.stream} Returns a new stream whose elements are the elements in list.

Function: string->stream string :optional tail-stream

{util.stream} Converts a string to a stream of characters. If an optional tail-stream is given, it becomes the tail of the resulting stream.

(stream->list (string->stream "abc" (list->stream ’(1 2 3)))) ⇒ (#\a #\b #\c 1 2 3)

Function: stream-format fmt arg …

{util.stream} Returns a stream which is a result of applying string->stream to (format fmt arg …).

Function: port->stream :optional iport reader closer

[R7RS stream] {util.stream} Creates a stream, whose elements consist of the items read from the input port iport. The default iport is the current input port. The default reader is read-char.

The result stream terminates at the point where reader returns EOF (EOF itself is not included in the stream). The port won’t be closed by default when it reaches EOF.

If closer is given, it is called with iport as an argument just after reader reads EOF. You can close the port with it.

The reader and closer arguments are Gauche’s extension. R7RS scheme.stream only takes one optional argument, iport.

Function: generator->stream gen

{util.stream} Creates a lazy stream of values generated by a generator gen. A generator is a thunk that returns a value every time it is called, with returning EOF to indicate the end of the input. See gauche.generator - Generators, for the details of generators.

See also generator->lseq, which is another way to get a lazy sequence from a generator (see Lazy sequences, for the details).

Function: iterator->stream iter

{util.stream} A generic procedure to turn an internal iterator iter into a stream of iterated results.

The iter argument is a procedure that takes two arguments, next and end, where next is a procedure that takes one argument and end is a thunk. Iter is supposed to iterate over some set and call next for each argument, then call end to indicate the end of the iteration. Here’s a contrived example:

(stream->list
 (iterator->stream
  (lambda (next end) (for-each next '(1 2 3 4 5)) (end))))
 ⇒ (1 2 3 4 5)

Internally iterator->stream uses the “inversion of iterator” technique, so that iter only iterates to the element that are needed by the stream. Thus iter can iterate over an infinite set. In the following example, iter is an infinite loop calling next with increasing integers, but only the first 10 elements are calculated because of stream-take:

(stream->list
 (stream-take
  (iterator->stream
   (lambda (next end)
     (let loop ((n 0)) (next n) (loop (+ n 1)))))
  10))
 ⇒ (0 1 2 3 4 5 6 7 8 9)
Macro: stream-of elt-expr clause …

[R7RS stream] {util.stream} Stream comprehension. Returns a stream in which each element is computed by elt-expr. The clause creates scope of elt-expr and controls iterations. Each clause can be one of the following forms:

(x in stream-expr)

Iterate over stream-expr, binding x to each element in each iteration. The variable x is visible in successive clauses and elt-expr

(x is expr)

Bind a variable x with the value of expr. The variable x is visible in successive clauses and elt-expr.

expr

If expr evaluates to #f, this iteration is skipped without generating a new element.

The following comprehension generates infinite sequence of pythagorean triples:

(define pythagorean-triples
  (stream-of (list a b c)
    (c in (stream-from 3))
    (b in (stream-range 2 c))
    (a in (stream-range 1 b))
    (= (square c) (+ (square b) (square a)))))

(stream->list 5 pythagorean-triples)
  ⇒ ((3 4 5) (6 8 10) (5 12 13) (9 12 15) (8 15 17))

12.92.3 Stream binding

Macro: define-stream (name . formals) body body2 …

[R7RS stream] {util.stream} A convenient macro to define a procedure that yields a stream. Same as the following form:

(define (name . formals)
  (stream-delay
    (let () body body2 …)))
Macro: stream-let loop-var ((var init) …) body body2 …

[R7RS stream] {util.stream} A handy macro to write a lazy named-let loop. It is the same as the following:

(let loop-var ((var init) …)
  (stream-delay
    (let () body body2 …)))
Macro: stream-match stream-expr clause …

[R7RS stream] {util.stream} This allows accessing streams via simple pattern matching. The stream-expr argument is evaluated and must yield a stream. Each clause must be either a form of (pattern expr) or (pattern fender expr).

The content of the stream is matched to each pattern, which must have one of the following forms:

()

Matches a null stream.

(p0 p1 …)

Matches a stream that has exactly the same number of elements as the number of pattern elements.

(p0 p1 … . pRest)

Matches a stream that has at least the same number of elements as the number of pattern elements except pRest. The rest of stream matches with pRest.

pRest

Matches an entire stream.

Each pattern element can be an identifier or a literal underscore. If it is an identifier, it is bound to the matched element while evaluating the corresponding fender and expr.

If fender is present in the clause, it is evaluated; if it yields #f, the match of the clause fails and next clauses will be tried.

Otherwise, expr is evaluated and the result(s) becomes the result(s) of stream-match.

Only the elements from the stream that is required to match are accessed.

The following example defines a procedure to count the number of true values in the stream:

(define (num-trues strm)
  (stream-match strm
    (() 0)
    ((head . tail) head (+ 1 (num-trues tail)))
    ((_ . tail) (num-trues tail))))

(num-trues (stream #f #f #t #f #t #f #t #t))
  ⇒ 4

12.92.4 Stream consumers

These procedures takes stream(s) and consumes its/their elements until one of the streams is exhausted.

Function: stream-for-each func . streams

[R7RS stream] {util.stream} Applies func for each element of streams. Terminates if one of streams reaches the end.

Function: stream-fold f seed stream

[R7RS stream] {util.stream} Apply f on the current seed value and an element from stream to obtain the next seed value, and repeat it until stream is exhausted, then returns the last seed value. The initial seed value is given by seed.

Note: The argument order of f differs from other *-fold procedures, e.g. fold (see Walking over lists) takes the element first, then the seed value.

(stream-fold - 0 (stream 1 2 3 4 5))
  ⇒ -15

12.92.5 Stream operations

Function: stream-append stream …

[R7RS stream] {util.stream} Returns a new stream which is concatenation of given streams.

Function: stream-concat streams
Function: stream-concatenate streams

[R7RS stream] {util.stream} R7RS scheme.stream defines stream-concat. Gauche had stream-concatenate, and keeps it for the backward compatibility. Both are the same.

The streams argument is a stream of streams. Returns a new stream that is concatenation of them. Unlike stream-append, streams can generate infinite streams.

Function: stream-map func stream stream2 …

[R7RS stream] {util.stream} Returns a new stream, whose elements are calculated by applying func to each element of stream ….

Function: stream-scan func seed stream

[R7RS stream] {util.stream} Returns a stream of seed, (func seed e0), (func (func seed e0) e1), …, where e0, e1 … are the elements from the input stream. If stream is finite, the result stream has one more elements than the number of elements in the original stream.

(stream->list
  (stream-scan xcons '() (stream 1 2 3 4 5)))
 ⇒ (() (1) (2 1) (3 2 1) (4 3 2 1) (5 4 3 2 1))
Function: stream-zip stream …

[R7RS stream] {util.stream} Returns a new stream whose elements are lists of corresponding elements from input streams. The output stream ends when one of input streams is exhausted.

(stream->list
 (stream-zip (stream 1 2 3) (stream 'a 'b 'c 'd)))
 ⇒ ((1 a) (2 b) (3 c))
Function: stream-filter pred stream

[R7RS stream] {util.stream} Returns a new stream including only elements passing pred. This procedure returns immediately; stream can be infinite.

Function: stream-remove pred stream

{util.stream} Returns a new stream including only elements that doesn’t satisfy pred. It is the same as (stream-filter (complement pred) stream).

Function: stream-partition pred stream

{util.stream} Returns two streams, one consists of the elements in stream that satisfy pred, the other consists of the ones that doesn’t satisfy pred.

Function: stream->list stream
Function: stream->list n stream

[R7RS stream] {util.stream} Converts a stream to a list. In the first form, all elements from stream are taken (thus it never returns if stream is infinite). In the second form, at most n elements are taken, where n must be a nonnegative exact integer.

Note: In usual Scheme conventions, the optional n comes after the main argument (stream).

Function: stream->string stream

{util.stream} Converts a stream to a string. All elements of stream must be characters, or an error is signaled.

Function: stream-lines stream

{util.stream} Splits stream where its element equals to #\n, and returns a stream of splitted streams. The character #\n won’t be included in the results.

(stream->list
 (stream-map stream->string
             (stream-lines (string->stream "abc\ndef\nghi"))))
 ⇒ ("abc" "def" "ghi")
Function: stream= elt= stream …

{util.stream} Returns true iff each corresponding element of stream … are the same in terms of elt=, which takes two arguments. This procedure won’t terminate if all of streams is infinite.

Function: stream-prefix= stream prefix :optional elt=

{util.stream} Compares initial elements of stream against a list prefix by elt=. Returns true iff they match. Only as many elements of stream as prefix has are checked.

Function: stream-caar s
Function: stream-cadr s

Function: stream-cdddar s
Function: stream-cddddr s

{util.stream} (stream-caar s) = (stream-car (stream-car s)) etc.

Function: stream-ref stream pos

[R7RS stream] {util.stream} Returns the pos-th element in the stream. Pos must be a nonnegative exact integer.

Function: stream-first s
Function: stream-second s
Function: stream-third s
Function: stream-fourth s
Function: stream-fifth s
Function: stream-sixth s
Function: stream-seventh s
Function: stream-eighth s
Function: stream-ninth s
Function: stream-tenth s

{util.stream} (stream-first s) = (stream-ref s 0) etc.

Function: stream-take stream count
Function: stream-take-safe stream count

{util.stream} Returns a new stream that consists of the first count elements of the given stream. If the given stream has less than count elements, the stream returned by stream-take would raise an error when the elements beyond the original stream is accessed. On the other hand, the stream returned by stream-take-safe will return a shortened stream when the given stream has less than count elements.

(stream->list (stream-take (stream-iota -1) 10))
 ⇒ (0 1 2 3 4 5 6 7 8 9)

(stream-take (stream 1 2) 5)
 ⇒ stream

(stream->list (stream-take (stream 1 2) 5))
 ⇒ error

(stream->list (stream-take-safe (stream 1 2) 5))
 ⇒ (1 2)

Note: SRFI-41 (scheme.stream) also defines stream-take, but the argument order is reversed, and also it allows stream to have less than count elements.

Function: stream-drop stream count
Function: stream-drop-safe stream count

{util.stream} Returns a new stream that consists of the elements in the given stream except the first count elements. If the given stream has less than count elements, stream-drop returns a stream that raises an error if its element is accessed, and stream-drop-safe returns an empty stream.

Note: SRFI-41 (scheme.stream) also defines stream-drop, but the argument order is reversed, and also it allows stream to have less than count elements.

Function: stream-intersperse stream element

{util.stream} Returns a new stream in which element is inserted between each consecutive two elements of stream.

(stream->list (stream-intersperse (stream 1 2 3) 0))
 ⇒ (1 0 2 0 3)
Function: stream-split stream pred

{util.stream} Split stream on elements that satisfy pred, and returns a stream of splitted streams. The delimiting element won’t be included in the result.

(stream->list
 (stream-map stream->list
             (stream-split (stream 1 3 2 5 7 9 6 8 1) even?))))
 ⇒ ((1 3) (5 7 9) () (1))
Function: stream-last stream

{util.stream} Returns the last element of stream. If stream is empty, an error is thrown. If stream is infinite, this procedure won’t return.

Function: stream-last-n stream count

{util.stream} Returns a stream that contains the last count elements in stream. The count argument must be a nonnegative exact integer. If the length of stream is smaller than count, the resulting stream is the same as stream. If stream is infinite, this procedure won’t return.

Function: stream-butlast stream

{util.stream} Returns a stream which is the same as stream but without the last element. If stream is empty, an empty stream is returned. immediately. The argument can be an infinite stream.

Function: stream-butlast-n stream count

{util.stream} Returns a stream which is the same as stream but without the last count elements. The count argument must be a nonnegative exact integer. If stream is shorter than count, a null stream is returned. Stream can be infinite.

Function: stream-length stream

[R7RS stream] {util.stream} Returns the number of elements in stream. It diverges if stream is infinite.

Function: stream-length>= stream n
Function: stream-length= stream n

{util.stream} Returns true iff the length of stream is greater than or equal to, and exactly equal to, n, respectively. These procedures only realizes stream up to n elements.

Function: stream-reverse stream :optional tail-stream

[R7RS stream] {util.stream} Returns a stream that returns the elements of stream in reverse order. If tail-stream is given, it is added after the reversed stream.

The optional argument is Gauche’s extension. The description of reverse (see Other list procedures) for more details.

Function: stream-count pred stream …

{util.stream} The predicate pred is called with each of the first element of stream …, then each of the second element, and so on, until any of the stream is exhausted. Then returns the number that pred returns a true value. At least one stream needs to be finite.

(stream-count < (stream 1 2 3 4 5) (stream 2 2 2 10 10))
 ⇒ 3
Function: stream-find pred stream

{util.stream} The predicate pred is applied to each element of stream in turn, and as soon as the pred returns true, returns the element that caused pred to return true. Remaining elements of stream won’t be realized.

If no elements in stream satisfy pred, #f is returned.

Function: stream-find-tail pred stream

{util.stream} The predicate pred is applied to each element of stream in turn, and as soon as the pred returns true, returns a stream that contains the element and the rest of the input stream. Remaining elements of stream won’t be realized.

If no elements in stream satisfy pred, the empty stream is returned.

Function: stream-take-while pred stream
Function: stream-drop-while pred stream

[R7RS stream] {util.stream} Returns a stream that contains or excludes initial consecutive elements of stream that satisfy pred, respectively.

(stream->list (stream-take-while even? (stream 2 4 6 1 4 2)))
 ⇒ (2 4 6)
(stream->list (stream-drop-while even? (stream 2 4 6 1 4 2)))
 ⇒ (1 4 2)
Function: stream-span pred stream
Function: stream-break pred stream

{util.stream} Return two streams; the first one consists of the initial consequent elements of stream that satisfy or dissatisfy pred, and the second one is the rest of the stream.

(map stream->list
     (values->list (stream-span even? (stream 2 4 6 1 4 2))))
 ⇒ ((2 4 6) (1 4 2))
(map stream->list
     (values->list (stream-break even? (stream 1 9 6 1 4 2))))
 ⇒ ((1 9) (6 1 4 2))
Function: stream-any pred stream …
Function: stream-every pred stream …

{util.stream} The predicate pred is applied to each of the first elements of stream …, then second, and so on. When pred returns a true value, stream-any returns the value immediately without looking further. When pred returns #f, stream-every returns #f immediately without looking further.

If none of applications of pred returns a true value until one of the streams is exhausted, stream-any returns #f. If none of applications of pred returns #f until one of the streams is exhausted, stream-every returns the last result of pred.

(stream-any (^[x y] (and (> x y) (list x y)))
            (stream 1 2 3 4 5)
            (stream 3 3 3 3 3))
 ⇒ (4 3)

(stream-every (^[x y] (and (> x y) (list x y)))
              (stream 6 6 6 6 6)
              (stream 1 2 3 4 5))
 ⇒ (6 5)
Function: stream-index pred stream …

{util.stream} The predicate pred is applied to each of the first elements of stream …, then second, and so on. If it returns a true value, stream-index returns immediately with the index. If pred never returns a true value until one of the streams is exhausted, stream-index returns #f.

(stream-index odd? (stream 2 4 6 7 8))
 ⇒ 3
Function: stream-member obj stream :optional elt=
Function: stream-memq obj stream
Function: stream-memv obj stream

{util.stream} Stream version of member, memq, and memv (see Other list procedures). Search an element equivalent to obj from stream, and if it is found, returns a stream consists of the element and the rest of the stream. If no such element is found, #f is returned.

They differ regarding which equivalent procedure to be used; stream-member uses the given elt= procedure, or equal? if omitted, stream-memq uses eq?, and stream-memv uses eqv?.

Function: stream-delete obj stream :optional elt=

{util.stream} Equivalent to (stream-remove (cut elt= obj <>) stream), that is, returns a stream that is the same as input except objs. If elt= is omitted, equal? is used.

Function: stream-delete-duplicates stream :optional elt=

{util.stream} Returns a stream that is the same as input except the consecutive equivalent elements are removed but the first one. Elements are compared with elt=, defaulted to equal?.

Function: stream-grep re stream

{util.stream} The re argument must be a regexp object, or a string representation of regexp (which is converted to regexp by string->regexp).

Returns a stream that contains input elements that matches re.

Function: write-stream stream :optional oport writer

{util.stream} Writes each element of stream to oport, using writer. When oport is omitted, the current output port is used. When writer is omitted, write-char is used.

No ’spacer’ is written between elements. As the default suggests, this is most useful to write out a stream of characters.


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]


For Development HEAD DRAFTSearch (procedure/syntax/module):
DRAFT