Streams

My favorite topic in 61A! Streams are sequences that look a lot like lists: they're pairs whose car is a value and whose cdr is a promise of a stream. The awesome part is because the rest of the stream is a promise, you can have infinite streams, such as the stream of all prime numbers. Now that's cool.

Lists Streams Notes
(cons val rest)
(cons-stream val rest)
(cons first
      (delay rest))

Note that CONS-STREAM is a special form!

(car ls) (stream-car strm) (car strm)
(cdr ls) (stream-cdr strm) (force (cdr strm))
nil the-empty-stream ()
(map +
     '(1 2 3 4)
     '(1 2 3 4))
(stream-map +
            ints
            ints)
(filter even?
        '(1 2 3 4))
(stream-filter even?
               ints)
(append '(1 2 3 4)
        '(1 2 3 4))
(stream-append ints
               ints)
Of course, you can't append something to an infinite stream! Use interleave instead.
(list-ref 5 ls) (stream-ref 5 strm)
ls (show-stream strm)
(show-stream strm 3)
(ss strm 3)

Unfortunately, EnvDraw does not handle promises. You'll have to draw them yourself.

The simplest possible infinite stream is ones. What's the first element of the stream? 1, of course. What's the rest of the stream? ones itself!

(define ones (cons-stream 1 ones))

This looks a little weird, cause we're defining ones in terms of itself! But remember: the rest of the stream is delayed. By the time we actually ask for the stream-cdr of ones, it'll be there, just like when we make a recursive call to a procedure we're defining.

Combining Streams

Next up is ints, the stream of all positive integers. We saw how to get this using a recursive integers-from procedure, but it's actually easier and more stream-ly to define it using ones.

(define ints (cons-stream 1 (stream-map + ones ints)))

stream-map is the most powerful of our stream-building procedures; the others are stream-append, interleave, and stream-filter. To check your work with stream-map, you use a table like the one below:

   ones  1  1  1  1  …
 + ints  1  _  _  _  …
--------------------
ints  1  _  _  _  …

Write the arguments to stream-map on top and the result below. Fill in any values you already have, either because they're from another stream or because they're explicitly stated with cons-stream.

Now, we can start filling things in. We have enough information to add the first column, so we do so:

   ones  1  1  1  1  …
 + ints  1  _  _  _  …
--------------------
ints  1  2  _  _  …

But now we know the second element of ints. So we can put that in the second row:

   ones  1  1  1  1  …
 + ints  1  2  _  _  …
--------------------
ints  1  2  _  _  …

That gives us enough information to compute the next column…and so on.

   ones  1  1  1  1  …
 + ints  1  2  3  4  …
--------------------
ints  1  2  3  4  …

Key point: we never know the whole stream, but we always know enough to compute the next element.

interleave is also worth going over. We still use a table structure, but we spread the two streams out to see how they'll braid together.

(interleave ints (stream-map - ints))
 ints  1    2    3    4    …
-ints    -1   -2   -3   -4   …
---------------------------
result 1 -1 2 -2 3 -3 4 -4 …

Practice

Let's try some practice problems. For each of these problems, you may use any of the stream procedures mentioned above, and any Scheme primitives you like...but no compound procedures, no lambda!

Back to Jordy's home page | Course home page