CSE1729 Introduction to Programming April 23, 2018
Problem Set 10
STREAMS
Recall that a SCHEME stream is a pair of the form
(a . (lambda () …)) .
The car of the pair is the first element of the stream. The job of the cdr of the pair (the lambda expression) is
to return the rest of the stream (which is another stream, and must have exactly the same structure) when it is
called with no arguments.
Using this convention, one can define
(define (first str) (car str))
(define (rest str) ((cdr str)))
As an example, the function int-stream returns the stream of positive integers a, a+ 1, a+ 2, . . .:
(define (int-stream a)
(cons a (lambda () (int-stream (+ 1 a)))))
Then, to continue our example
> (define a (int-stream 5))
> a
’(5 . #
> (rest a)
’(6 . #
> (rest (rest a))
’(7 . #
> (first (rest (rest a)))
7
There are natural ways to operate on streams. For example, the following function takes two streams and returns
the stream containing the “elementwise product.” Note that the value returned by this function is a stream.
(define (str-product s t)
(if (or (null? s) (null? t))
’()
(cons (* (first s) (first t))
(lambda () (str-product (rest s) (rest t))))))
Then, for example
> (define a (str-product (int-stream 5) (int-stream 2)))
> a
’(10 . #
> (rest a)
’(18 . #
> (rest (rest a))
’(28 . #
1
You will notice that in the example above, we created a function that returned the stream; when such a
stream is created, it will have embedded in the cdr of the stream a call to this function. We mention that there
are circumstances where it may be helpful for the definition of the stream to carry additional information (beyond
simply the first element of the stream). As an example, consider the stream of Fibonacci numbers.
(define (fib-stream current next)
(cons current (lambda ()
(fib-stream next (+ current next )))))
To generate the stream of regular Fibonacci numbers, you would use the call (fib-stream 0 1).
Please use the stream conventions above; do not use force and delay! Why? Recall that in class, we used
the special forms
(delay x) ←→ (lambda () x)
(force x) ←→ (x)
and then used these in our definitions of streams. Each expression on the left, above, is essentially equivalent to
the expression on the right. One quirk about these functions, however, is that if an expression has been delayed
(via (delay E)), the only way you can get SCHEME to evaluate it is via (force …). (You cannot simply call
it on no arguments.) We need to know which convention is being used in order to test your code, so we ask that
you still to the “bare bones” convention that simply uses (lambda () …).
1. Write a function merge-streams that merges two streams. Specifically, if s and t are two streams of
positive numbers in increasing order, (merge-streams s t) should be the stream containing all elements
appearing in either s or t, also in increasing (sorted) order. For example, if s is the stream of all perfect
squares
1, 4,9, 16,25, 36, . . .
and t is the stream of all perfect cubes
1,8, 27,64, 125,216, . . .
then (merge-streams s t) would be the stream
1,1, 4,8, 9,16, 25,27, 36, . . . .
Note that there are numbers, such as 1 and (23)2 = (22)3 = 26 = 64 that are both perfect squares and
perfect cubes. In this case, your merged stream should produce the number twice.
2. Picking up from the previous problem, define a merge function merge-compress that avoids repeated
elements (which is to say that if an element appears in both streams, it should appear in the output stream
only once).
Use this to build a stream that generates the ordered list of all positive numbers that are divisible by 2, 3,
or 5 (in which each such element appears exactly once). To do this, merge together individual streams for
the multiples of 2, 3, and 5. Your stream should output these numbers in sorted order, and should output
any given integer only once. (You don’t need to hand in this function.)
3. (The Mandelbrot Stream.) The Mandelbrot set is a remarkable subset of the complex numbers. It’s nice
to look at, and is related to the mathematical study of “chaos.”
The set contains all complex numbers z with the property that the sequence
0, z, z2 + z, (z2 + z)2 + z, . . .
contains only “short” complex numbers (that have length≤ 2). There is a standard way that mathematicians
“picture” the complex numbers (by placing the number a+bi at position (a, b) in the plane); in this problem,
2
Figure 1: The Mandelbrot set.
you will use streams to create an image of the Mandelbrot set in the plane. (See the figure for an example
of the kind of image you can produce with this code.)
You won’t need to know anything special about the complex numbers in order to solve the problem.
(a) Recall that a complex number can be written a + bi, where a and b are real numbers. Adding two
complex numbers is straightforward:
(a+ bi) + (c + di) = (a+ c) + (b+ d)i .
Multiplication of complex numbers is defined
(a+ bi) · (c + di) = (ac − bd) + (ad + bc)i .
Finally, the length of a complex number a + bi, denoted |a + bi|, is defined to be
p
a2 + b2. For this
problem, I recommend that you simply represent complex numbers as pairs, so the complex number
a+ bi would be represented as the pair (a . b).
Write the functions c-add, c-multiply, and c-length, which add, multiply, and compute the
length of complex numbers. (Your addition and multiplication functions should take two complexes
(pairs) and return a complex with the result. Your length function should take a complex and return
its length, a real number.)
(b) In this problem you will implement a famous stream of complex numbers that define a remarkable
fractal—the Mandelbrot set. An image of the Mandelbrot set appears in Figure 1.
For a complex number z = α+β i define the function fz so that fz(y) = y
2 + z. (Here y is also meant
to be a complex number.)
The Mandelbrot-z stream consists of the infinite sequence of complex numbers
0, fz(0), fz( fz(0)), fz( fz( fz(0))), . . . .
Define a function (mandelbrot-sequence z) that returns the Mandelbrot-z stream. (Along the
way, it may help you to define a function (mandelbrot-sequence-tail z a), which returns the
stream
a, fz(a), fz( fz(a)), fz( fz( fz(a))), . . . .)
3
(c) Recall the stream-map function, which takes a function f and a stream s = s1, s2, . . . and returns the
stream f (s1), f (s2), . . ., which we defined in class. Correctly define stream-map.
Using (mandelbrot-sequence z) and stream-map, construct the stream (mandelbrot-sequence-length
z) whose elements are the lengths of the elements of the stream (mandelbrot-sequence z).
(d) Next, define a function (depth z max) which computes the index of the first element of the stream
(mandelbrot-length z) that is larger than 2. For example, the stream (mandelbrot-length
’(1/2 . 1/2)) contains the numbers
0, .707, 1.118, 1.521, 1.706, 3.550, . . .
and thus the index of the first entry that is larger than 2 is 5 (because the first element of the stream
that is larger than 2 has index equal to 5). Note that we index the elements of these streams starting
at 0–so the “first” element above is .707, etc.
Now, there are Mandelbrot streams for which this never happens (that is, the lengths are always less
than 2). To protect your function from this, it may give up after max steps; specifically, if it does not
find an element of the stream that is at least 2 in the first max elements, it should just return max.
Now, finally, you are ready to generate the Mandelbrot set. One you have depth defined, use the code
below, which will write the image to a file called mandelbrot.png. (You’ll have to be in Racket mode
for this to work.)
(define (iter- >color i)
(if (= i 255)
(make-object color% “black”)
(make-object color% (* 5 (modulo i 15))
(* 32 (modulo i 7))
(* 8 (modulo i 31)))))
(define (mandelbrot width height)
(define target (make-bitmap width height ))
(define dc (new bitmap-dc% [bitmap target ]))
(for* ([x width] [y height ])
(define real-x (- (* 3.0 (/ x width)) 2.25))
(define real-y (- (* 2.5 (/ y height )) 1.25))
(send dc set-pen
(iter- >color (depth (cons real-x real-y) 255)) 1 ’solid)
(send dc draw-point x y))
(send target save-file “mandelbrot.png” ’png))
4. Write a function sorted-stream-h which, given a heap H, returns the stream consisting of the elements
of H in sorted order.
Use our regular tree and heap conventions:
(define (maketree v L R) (list v L R))
(define (value T) (car T))
(define (left T) (cadr T))
(define (right T) (caddr T))
(define (h-min H) (value H))
(define (extract-min H) …)
5. Write a function sorted-stream which, given a list L, returns the stream consisting of the elements of L
in sorted order.
4