1.15.5 Operations

Function: stream-length stream

Take an input stream and return the number of elements in the stream; it does not evaluate its elements. stream-length may only be used on finite streams; it enters an infinite loop with infinite streams.

Example:

(define strm123
  (stream 1 2 3))

(stream-length strm123)
⇒ 3

Function: stream-ref stream n

Return the n-th element of stream, counting from zero. An error is signaled if n is greater than or equal to the length of stream.

Example:

(define (fact n)
  (stream-ref
    (stream-scan * 1 (stream-from 1))
    n))

Function: stream-reverse stream

Return a newly–allocated stream containing the elements of the input stream but in reverse order. stream-reverse may only be used with finite streams; it enters an infinite loop with infinite streams. stream-reverse does not force evaluation of the elements of the stream.

(define s (stream 1 (/ 1 0) -1))
(define r (stream-reverse s))

(stream-ref r 0)
(stream-ref r 2)        ⇒ 1
(stream-ref r 1)        error→ division by zero

Function: stream-append stream ...

Return a newly–allocated ‘stream’ containing in its elements those elements contained in its input streams, in order of input. If any of the input streams is infinite, no elements of any of the succeeding input streams will appear in the output stream; thus, if x is infinite, (stream-append x y) is identical to x. See also stream-concat.

Example: quicksort can be used to sort a ‘stream’, using stream-append to build the output; the sort is lazy; so if only the beginning of the output stream is needed, the end of the stream is never sorted.

(define-stream (qsort lt? strm)
  (if (stream-null? strm)
      stream-null
      (let ((x (stream-car strm))
            (xs (stream-cdr strm)))
        (stream-append
          (qsort lt?
            (stream-filter
              (lambda (u) (lt? u x))
              xs))
          (stream x)
          (qsort lt?
            (stream-filter
              (lambda (u) (not (lt? u x)))
              xs))))))

Note also that, when used in tail position as in qsort, stream-append does not suffer the poor performance of append on lists. The list version of append requires re–traversal of all its list arguments except the last each time it is called. But stream-append is different. Each recursive call to stream-append is suspended; when it is later forced, the preceding elements of the result have already been traversed, so tail–recursive loops that produce streams are efficient even when each element is appended to the end of the result stream. This also implies that during traversal of the result only one promise needs to be kept in memory at a time.

Function: stream-concat stream

Take a stream consisting of one or more streams and return a newly–allocated stream containing all the elements of the input streams. If any of the streams in the input stream is infinite, any remaining streams in the input stream will never appear in the output stream. See also stream-append.

Example:

(stream->list
  (stream-concat
    (stream
      (stream 1 2) (stream) (stream 3 2 1))))
⇒ (1 2 3 2 1)

Example: the permutations of a finite stream can be determined by interleaving each element of the stream in all possible positions within each permutation of the other elements of the stream; interleave returns a stream of streams with x inserted in each possible position of yy:

(define-stream (interleave x yy)
  (stream-match yy
    (() (stream (stream x)))
    ((y .  ys)
      (stream-append
        (stream (stream-cons x yy))
        (stream-map
          (lambda (z) (stream-cons y z))
          (interleave x ys))))))

(define-stream (perms xs)
  (if (stream-null? xs)
      (stream (stream))
    (stream-concat
      (stream-map
        (lambda (ys)
          (interleave (stream-car xs) ys))
        (perms (stream-cdr xs))))))

Function: stream-zip stream ...

Take one or more input streams and return a newly–allocated stream in which each element is a list (not a stream) of the corresponding elements of the input streams. The output stream is as long as the shortest input stream, if any of the input streams is finite, or is infinite if all the input streams are infinite.

A common use of stream-zip is to add an index to a stream, as in:

(stream-finds eqv? obj strm)

which returns all the zero–based indices in strm at which obj appears; (stream-find eqv? obj strm) returns the first such index, or #f if obj is not in strm.

(define-stream (stream-finds item= obj strm)
  (stream-of (car x)
    (x in (stream-zip (stream-from 0) strm))
    (item= obj (cadr x))))

(define (stream-find item= obj strm)
  (stream-car
    (stream-append
      (stream-finds item= obj strm)
      (stream #f))))

(stream-find char=? #\l
  (list->stream
    (string->list "hello")))
⇒ 2

(stream-find char=? #\l
  (list->stream
    (string->list "goodbye")))
⇒ #f

stream-find is not as inefficient as it looks; although it calls stream-finds, which finds all matching indices, the matches are computed lazily, and only the first match is needed for stream-find.