For Gauche 0.9.9


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

12.71 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),


Next: , Previous: , Up: Stream library   [Contents][Index]

12.71.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 …)).


Next: , Previous: , Up: Stream library   [Contents][Index]

12.71.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:

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 sequence 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))
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: 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))

Next: , Previous: , Up: Stream library   [Contents][Index]

12.71.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

Next: , Previous: , Up: Stream library   [Contents][Index]

12.71.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

Previous: , Up: Stream library   [Contents][Index]

12.71.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.

Function: stream-remove pred stream

{util.stream} Returns a new stream including only elements that doesn’t satisfy pred.

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 list. 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.

(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=. This procedure won’t terminate if any of streams is infinite.

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

{util.stream} Compares initial elements of stream against a list prefix by elt=. 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 elements of stream.

Function: stream-split stream pred

{util.stream}

Function: stream-last stream

{util.stream}

Function: stream-last-n stream count

{util.stream}

Function: stream-butlast stream

{util.stream}

Function: stream-butlast-n stream count

{util.stream}

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}

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}

Function: stream-find pred stream

{util.stream}

Function: stream-find-tail pred stream

{util.stream}

Function: stream-take-while pred stream

[R7RS stream] {util.stream}

Function: stream-drop-while pred stream

[R7RS stream] {util.stream}

Function: stream-span pred stream

{util.stream}

Function: stream-break pred stream

{util.stream}

Function: stream-any pred stream …

{util.stream}

Function: stream-every pred stream …

{util.stream}

Function: stream-index pred stream …

{util.stream}

Function: stream-member obj stream :optional elt=
Function: stream-memq obj stream
Function: stream-memv obj stream

{util.stream}

Function: stream-delete obj stream :optional elt=

{util.stream}

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

{util.stream}

Function: stream-grep re stream

{util.stream}

Function: write-stream stream :optional oport writer

{util.stream}


Previous: , Up: Stream library   [Contents][Index]