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
!
-
Define the stream of all square numbers.
> (ss squares 5) (1 4 9 16 25 ...)
(show answer, mouseover for hint)
(define squares (stream-map * ints ints))
-
Define the stream of all factorials starting from 1!.
> (ss facts 5) (1 2 6 24 120 ...)
(show answer, mouseover for hint)
(define facts (cons-stream 1 (stream-map * facts (stream-cdr ints))))
This is all we know at first:
facts 1 _ _ _ … * (stream-cdr ints) 2 3 4 5 … --------------------------------- facts 1 _ _ _ …
Completing the streams column by column shows us that this really does work:
facts 1 2 6 24 … * (stream-cdr ints) 2 3 4 5 … --------------------------------- facts 1 2 6 24 …
-
Define the stream of all Fibonacci numbers.
> (ss fibs 7) (1 1 2 3 5 8 13 ...)
(show answer, mouseover for hint)
(define fibs (cons-stream 1 (cons-stream 1 (stream-map + fibs (stream-cdr fibs)))))
This is all we know at first:
fibs 1 1 _ _ … + (stream-cdr fibs) 1 _ _ _ … --------------------------------- fibs 1 1 _ _ _ …
You'll notice there are two base cases here! But if you think about the definition of Fibonacci numbers, they do have two base cases. And if we only had one, that second row,
(stream-cdr fibs)
, wouldn't actually have anything in it, and we'd be stuck.Completing the streams column by column shows us that this really does work:
fibs 1 1 2 3 … + (stream-cdr fibs) 1 2 3 5 … --------------------------------- fibs 1 1 2 3 5 …
-
Define a stream of alternating integers.
> (ss alternating-ints 5) (1 -2 3 -4 5 ...)
(show answer, mouseover for hint)
(define alternating-ints (interleave (stream-filter odd? ints) (stream-map - (stream-filter even? ints))))
Basically, "interleave the odd integers with the negative even ones".
-
Now, define a procedure that takes an infinite stream of positive integers and returns an alternating stream.
> (ss (alternating squares) 5) (1 -4 9 -16 25 ...)
(show answer, mouseover for hint)
(define (alternating s) (cons-stream (stream-car s) (stream-map - (alternating (stream-cdr s))))))
This one's a little tricky, but what you have to notice is that the
stream-cdr
of the result is itself an alternating stream, just one that goes negative-positive instead of positive-negative. -
Define the procedure
potstickers
that behaves as follows. (You can use helpers for this one!)> (ss (potstickers 'brian) 16) (brian likes potstickers brian really likes potstickers brian really really likes potstickers brian really really really ...)
Other TAs have this as the
chocolate
problem.(show answer, mouseover for hint)
(define (potstickers name) (define (nth-really n) (if (= n 0) (cons-stream 'likes (cons-stream 'potstickers the-empty-stream)) (cons-stream 'really (nth-really (- n 1))) )) (define (starting-from n) (cons-stream name (stream-append (nth-really n) (starting-from (+ n 1)) ))) (starting-from 0) )
Yikes! This one needs to be broken down. We know we need a procedure to count which segment we're on, so let's make
starting-from
that lets us know. Each segment starts with a name, so we'll justcons-stream
that on the front. Then there's a bunch of reallys, which end with a likes potstickers, and finally it starts all over again with the next segment.How do we do the reallys? That's a little easier: we can just count down to 0 and include one for each recursive call. Our base case, rather than just being
the-empty-stream
, is going to include the likes potstickers bit.What if we had put the
cons-stream
for the name inside thestream-append
? (Try it, if you didn't run into it while trying .) Why does this happen? Hint: isstream-append
a special form, likecons-stream
?
Back to Jordy's home page | Course home page