1.15.9 Folding

Function: stream-iterate proc base

Create a newly–allocated stream containing base in its first element and apply proc to each element in turn to determine the succeeding element. See also stream-unfold and stream-unfolds.

Examples:

(stream-iterate (lambda (x) (+ x 1)) 0)
  => 0 1 2 3 4 ...

(stream-iterate (lambda (x) (* x 2)) 1)
  => 1 2 4 8 16 ...

Given a seed between 0 and 232, exclusive, the following expression creates a stream of pseudo–random integers between 0 and 232, exclusive, beginning with seed, using the method described by Stephen Park and Keith Miller:

(stream-iterate
  (lambda (x) (modulo (* x 16807) 2147483647))
  seed)

Example: successive of the following stream approach the value of the “golden ratio” 1.618...:

(stream-iterate (lambda (x) (+ 1 (/ x))) 1)

Function: stream-fold proc base stream

Apply a binary procedure to base and the first element of stream to compute a new base, then apply the procedure to the new base and the next element of stream to compute a succeeding base, and so on, accumulating a value that is finally returned as the value of stream-fold when the end of the stream is reached.

stream must be finite, or stream-fold will enter an infinite loop. See also stream-scan, which is similar to stream-fold, but useful for infinite streams.

For readers familiar with other functional languages, this is a left–fold; there is no corresponding right–fold, since right–fold relies on finite streams that are fully–evaluated, at which time they may as well be converted to a list.

stream-fold is often used to summarize a stream in a single value, for instance, to compute the maximum element of a stream.

(define (stream-maximum item< strm)
  (stream-fold
    (lambda (x y)
      (if (item< x y) y x))
    (stream-car strm)
    (stream-cdr strm)))

Sometimes, it is useful to have stream-fold defined only on non–null streams:

(define (stream-fold-one proc strm)
  (stream-fold proc
    (stream-car strm)
    (stream-cdr strm)))

stream-minimum can then be defined as:

(define (stream-minimum item< strm)
  (stream-fold-one
    (lambda (x y)
      (if (item< x y) x y))
    strm))

stream-fold can also be used to build a stream:

(define-stream (isort item< strm)
  (define-stream (insert strm x)
    (stream-match strm
      (() (stream x))
      ((y .  ys)
        (if (item< y x)
            (stream-cons y (insert ys x))
          (stream-cons x strm)))))
  (stream-fold insert stream-null strm))

Function: stream-scan proc base stream

Accumulate the partial folds of an input stream into a newly–allocated output stream. The output stream is the base followed by:

(stream-fold proc base (stream-take i stream))

for each of the first i elements of stream.

Examples:

(stream-scan + 0 (stream-from 1))
⇒ (stream 0 1 3 6 10 15 ...)

(stream-scan * 1 (stream-from 1))
⇒ (stream 1 1 2 6 24 120 ...)