Week 13 solutions
LAB
===
1. The result of (delay ...) is of type *promise*.
The result of (force (delay ...)) is of whatever type the "..." would
be without delay; in this case it's (force (delay (+ 1 27))) and that's of
type integer.
2. (stream-cdr (stream-cdr (cons-stream 1 '(2 3)))) causes an error because
(2 3) isn't a stream.
(stream-cdr (cons-stream 1 '(2 3))) --> (2 3)
(stream-cdr '(2 3)) --> (force (cdr '(2 3)))
--> (force '(3))
but (3) isn't a promise!
3. (delay (enumerate-interval 1 3)) returns a promise.
(stream-enumerate-interval 1 3) returns a stream, i.e., a pair whose car
is 1 and whose cdr is a promise.
The only thing you can do with the result of (delay ...) is FORCE it; you
can't ask for its stream-car or stream-cdr, etc. By contrast, with the
stream, you can stream-car or stream-cdr it, but *not* force it, because
it's not a promise.
4. the 4-2-1 stream.
(define (next-num n)
(if (even? n)
(/ n 2)
(+ (* n 3) 1)))
(define (num-seq n)
(cons-stream n (num-seq (next-num n))))
(define (seq-length s)
(if (= (stream-car s) 1)
1
(+ 1 (seq-length (stream-cdr s)))))
HOMEWORK
========
3.50 stream-map
(define (stream-map proc . argstreams)
(if (STREAM-NULL? (car argstreams))
the-empty-stream
(CONS-STREAM
(apply proc (map STREAM-CAR argstreams))
(apply stream-map
(cons proc (map STREAM-CDR argstreams))))))
3.51 stream-ref
> (stream-ref x 5)
1
2
3
4
5
5
> (stream-ref x 7)
6
7
7
>
The repeated last number in each case is the actual value returned by
stream-ref; the other numbers are printed by show. The only numbers
shown are the ones we haven't already computed. If we ask for a value
nearer the front of the stream, nothing is SHOWn at all:
> (stream-ref x 4)
4
>
Notice that the first element of the stream is zero, not one -- why
isn't the zero printed? Answer: It was printed when you defined X
in the first place.
NOTE: The important thing to take away from this example is that if
DELAY didn't involve memoization, the printed results would be quite
different. All the numbers would be printed every time.
3.52 accum/filter
To make the situation more visible, I've chosen to define accum to use
show (as above), so we can see intermediate results:
> (define sum 0)
SUM
> (define (accum x)
(set! sum (+ (show x) sum))
sum)
ACCUM
> (define seq (stream-map accum (stream-enumerate-interval 1 20)))
1
SEQ
;; map applies the function argument to the stream-car of the stream only.
> sum
1
> (define y (stream-filter even? seq))
2
3
Y
;; filter keeps forcing stream elements until it finds an even sum, 1+2+3.
> sum
6
> (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq))
4
Z
;; 1+2+3+4 is divisible by 5.
> (stream-ref y 7)
5
6
7
8
9
10
11
12
13
14
15
16
136
;; even sums are 6, 10, 28, 36, 66, 78, 120, 136 (1+...+16).
;; (Notice how they come in pairs, by the way. Two odd sums, then two even.)
> sum
136
> (print-stream z)
{10 15 45 55 105 120
17
18
19 190
20 210}
;; This may look confusing. Had I not used show, print-stream would have
;; printed {10 15 45 55 105 120 190 210}. This is the entire stream z.
;; The numbers 17 to 20 were printed by show as the stream seq was forced.
> sum
210
>
Had we not used the memoizing version of delay, the computation of z would
have forced the stream seq over again, from the beginning. Not only would
accum have shown the results 1, 3, 6, 10, etc. over again, it would have
gotten the wrong answers! Since it uses the global variable sum, it only
works if each term is added to the sum only once.
3.53 implicit definition
Try it yourself!
We know the first element of S is 1 and the STREAM-CDR is the result
of adding S and S, so we get:
1 ...
+ 1 ...
--------
2 ...
So the second element must be 2. That means we have:
1 2 ...
+ 1 2 ...
----------
2 4 ...
So the third element is 4, and so on.
3.54 factorials
(define (mul-streams s1 s2)
(stream-map * s1 s2))
(define factorials (cons-stream 1 (mul-streams FACTORIALS INTEGERS)))
will give you the stream {1 1 2 6 24 ...} starting with zero factorial, or
(define factorials (cons-stream 1 (mul-streams FACTORIALS
(STREAM-CDR INTEGERS))))
will give the stream {1 2 6 24 ...} starting with one factorial.
3.55 partial sums
(define (partial-sums s)
(define result (cons-stream (stream-car s)
(add-streams (stream-cdr s) result)))
result)
Alternatively, it can be done explicitly:
(define (partial-sums s)
(define (helper s sofar)
(cons-stream sofar (helper (stream-cdr s) (+ sofar (stream-car s)))))
(helper (stream-cdr s) (stream-car s)))
but the first version is way cooler.
3.56 merge and Hamming's problem
This is easy:
> (define S (cons-stream 1 (merge (scale-stream S 2)
(merge (scale-stream S 3)
(scale-stream S 5)))))
S
> (show-stream S 41)
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72
75 80 81 90 96 100 108 120 125 128 135 144 150 ...)
3.64 stream-limit
(define (stream-limit s tolerance)
(if (< (abs (- (stream-car s)
(stream-car (stream-cdr s))))
tolerance)
(stream-car (stream-cdr s))
(stream-limit (stream-cdr s) tolerance)))
3.66 examine the pairs of integers
One thing to try is to look at each half of the pairs separately.
> (ss (stream-map car p) 100)
(1 1 2 1 2 1 3 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2
1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1
3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 ...)
Every other element is 1. Leaving those out, we get
1 2 2 3 2 3 2 4 2 3 2 4 2 3 2 5 2 3 2 4 ...
Except right at the beginning, every other element is 2. Leaving those
out we are left with
2 3 3 4 3 4 3 5 3 4 ...
Looks like every other element is 3... sounds like a pattern!
> (ss (stream-map cadr p) 100)
(1 2 2 3 3 4 3 5 4 6 4 7 5 8 4 9 6 10 5 11 7 12 5 13 8 14 6 15 9 16 5 17 10
18 7 19 11 20 6 21 12 22 8 23 13 24 6 25 14 26 9 27 15 28 7 29 16 30 10 31
17 32 6 33 18 34 11 35 19 36 8 37 20 38 12 39 21 40 7 41 22 42 13 43 23 44
9 45 24 46 14 47 25 48 7 49 26 50 15 51 ...)
The even-numbered elements are
2 3 4 5 6 7 8 9 10 11 12 ...
The odd-numbered ones are
1 2 3 3 4 4 5 4 6 5 7 5 8 6 ...
What can you make of those?
3.68 Louis
INTERLEAVE is an ordinary Scheme procedure, so its arguments must
be computed before INTERLEAVE is called. One of those arguments
is a recursive call to PAIRS. This will be an infinite loop.
The book's version works because it uses CONS-STREAM, which
doesn't evaluate its second argument until later, if ever.
--------------------
2. fract-stream problem
(define (fract-stream fraction)
(cons-stream (quotient (* (car fraction) 10) (cadr fraction))
(fract-stream (list (remainder (* (car fraction) 10)
(cadr fraction))
(cadr fraction)))))
(define (approximation str num)
(if (= num 0)
'()
(cons (stream-car str) (approximation (stream-cdr str) (- num 1))) ))
Extra for Experts
=================
1. Book exercises.
3.59
(a)
(define (integrate-series s)
(stream-map / s integers))
(b)
(define cosine-series
(cons-stream 1 (integrate-series (stream-map - sine-series))))
(define sine-series
(cons-stream 0 (integrate-series cosine-series)))
We can check our work two ways. One is by comparing the results with the
explicit definitions given for the sin and cos series in the exercise:
STk> (ss sine-series)
(0 1 0 -0.166666666666667 0 0.00833333333333333 0 -0.000198412698412698
0 2.75573192239859e-06 ...)
STk> (ss (stream-map (lambda (n)
(cond ((= (remainder n 2) 0) 0)
((= (remainder n 4) 3)
(/ -1 (factorial n)))
(else (/ 1 (factorial n)))))
(cons-stream 0 integers)))
(0 1 0 -0.166666666666667 0 0.00833333333333333 0 -0.000198412698412698
0 2.75573192239859e-06 ...)
STk> (ss cosine-series)
(1 0 -0.5 0 0.0416666666666667 0 -0.00138888888888889 0 2.48015873015873e-05 0 ...)
STk> (ss (stream-map (lambda (n)
(cond ((= (remainder n 2) 1) 0)
((= (remainder n 4) 2)
(/ -1 (factorial n)))
(else (/ 1 (factorial n)))))
(cons-stream 0 integers)))
(1 0 -0.5 0 0.0416666666666667 0 -0.00138888888888889 0 2.48015873015873e-05 0 ...)
For a second check, we can actually evaluate an approximation to the value of
a series. (This goes beyond what the problem asked you to do!)
(define (approximate-value s x terms)
(define x-stream (cons-stream x x-stream))
(if (= terms 0)
0
(+ (stream-car s)
(approximate-value (stream-map * (stream-cdr s) x-stream)
x
(- terms 1)))))
STk> (sin 3)
0.141120008059867
STk> (approximate-value sine-series 3 30)
0.141120008059867
STk> (sin -2)
-0.909297426825682
STk> (approximate-value sine-series -2 30)
-0.909297426825682
Infinite series have a limited domain of convergence. Luckily for sin and cos
there's no reason to give a value of X with magnitude larger than pi.
3.60
Suppose we have two series
A = a0 + a1 * x^1 + a2 * x^2 + ...
B = b0 + b1 * x^1 + b2 * x^2 + ...
Multiply them by multiplying every term of A times every term of B, collecting
the results according to the resulting power of X:
AB = (a0b0) + (a0b1+a1b0) * x^1 + (a0b2+a1b1+a2b0) * x^2
+ (a0b3+a1b2+a2b1+a3b0) * x^3 + ...
(In the above, "a0b0" means a0 * b0, written more compactly so the big picture
is easier to see.)
The term for x^n is a sum of n+1 products of ai*bj where i+j=n.
We are told to express this in the form
(cons-stream _____ (add-streams _____ _____))
It's clear what goes in the first blank: a0b0, the constant term in AB.
The rest of the problem takes some cleverness; one key observation is that
each term of AB includes the product a0bi. These products, taken together,
are (scale-stream b a0). But we can't quite say that because we used up a0b0
in the first blank. So...
(define (mul-series s1 s2)
(cons-stream (* (stream-car s1) (stream-car s2))
(add-streams (scale-stream (stream-cdr s2) (stream-car s1))
(mul-series (stream-cdr s1) s2))))
STk> (ss (add-streams (mul-series sine-series sine-series)
(mul-series cosine-series cosine-series)))
(1 0 0.0 0.0 5.55111512312578e-17 0.0 -6.93889390390723e-18 0.0 0.0 0.0 ...)
The result we wanted was (1 0 0 0 0 0 0 0 0 0 ...). We didn't quite get that
because of arithmetic roundoff errors, but the few nonzero terms are quite
small, except for the expected 1 as the constant term.
3.61
(define (invert-unit-series s)
(define x (cons-stream 1 (stream-map - (mul-series (stream-cdr s) x))))
x)
STk> (ss cosine-series)
(1 0 -0.5 0 0.0416666666666667 0 -0.00138888888888889 0 2.48015873015873e-05 0 ...)
STk> (ss (invert-unit-series cosine-series))
(1 0 0.5 0.0 0.208333333333333 0.0 0.0847222222222222 0.0 0.0343501984126984 0.0 ...)
STk> (ss (invert-unit-series (invert-unit-series cosine-series)))
(1 0 -0.5 0.0 0.0416666666666667 0.0 -0.00138888888888888 0.0 2.48015873015855e-05
0.0 ...)
3.62
Since invert-unit-series only works for series with constant term 1, if the
denominator starts with anything else we have to scale it by 1/const, so we have
an appropriate argument. Since we made the stream smaller (if const > 1), the
reciprocal of the scaled denominator will be *larger* than the reciprocal of
the original stream, so we have to scale it again by 1/const.
(define (div-series s1 s2)
(if (= (stream-car s2) 0)
(error "Can't divide by zero-constant-term series")
(mul-series s1
(scale-stream (invert-unit-series
(scale-stream s2 (stream-car s2)))
(stream-car s2)))))
(define tangent-series (div-series sine-series cosine-series))
STk> (ss tangent-series)
(0 1 0.0 0.333333333333333 0.0 0.133333333333333 0.0 0.053968253968254
0.0 0.0218694885361552 ...)
STk> (approximate-value tangent-series (/ pi 4) 30)
0.999999999209469
STk> (approximate-value tangent-series (/ pi 4) 200)
1.0
2. Hanoi-stream.
This was a final exam problem in fall 97 (but only worth 2 points and marked as
harder than the others). Here are the solutions as posted from that exam:
The most obvious approach is to try to generalize from the finite case.
You can't, of course, say (HANOI-STREAM INFINITY). Instead of recursion
to smaller streams, as in HANOI-STREAM, you have to start with a small
example and try to make it bigger in each recursion. The goal is something
like this:
(make-bigger () 1) -->
(make-bigger (1) 2) -->
(make-bigger (1 2 1) 3) -->
(make-bigger (1 2 1 3 1 2 1) 4) --> etc.
Here's the attempted code:
(define (make-bigger stream num)
(make-bigger (stream-append stream (cons-stream num stream))
(+ num 1)))
(define hanoi (make-bigger the-empty-stream 1)) ; wrong!
But of course this won't work. The recursion in MAKE-BIGGER isn't
delayed (by happening in the second argument to a CONS-STREAM) so
the program really does loop forever with no result.
There were five general categories of solution to this problem.
First category (three correct solutions):
We know how to make finite Hanoi streams. The problem points out
that the infinite Hanoi stream has any particular finite Hanoi
stream as a leading substring. So for example, the infinite stream
(1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
starts with
(1 2 1 3 1 2 1)
which is (hanoi-stream 3). So, the Nth element of the infinite
Hanoi stream is also the Nth element of any finite Hanoi stream
whose length is at least N. The simplest such finite stream to
choose is (hanoi-stream N), whose length is always at least N.
So...
(define (nth-hanoi-element n)
(stream-nth n (hanoi-stream n)))
(define (stream-nth n stream)
(if (= n 1)
(stream-car stream)
(stream-nth (- n 1) (stream-cdr stream))))
(define hanoi (stream-map nth-hanoi-element integers))
Second category (four correct solutions):
The idea of computing a function that finds the Nth number in the
stream, and mapping that function over the integers, is nice and
simple. But the NTH-HANOI-ELEMENT above takes time Theta(2^N) for
each element. By choosing a smaller argument to HANOI-STREAM, we
can get that down to Theta(N), but why can't we calculate the
Nth number directly, instead of building a stream each time?
If N is odd, (HANOI-NUMBER N) should be 1.
If N is divisible by 2 but not by 4, (HANOI-NUMBER N) must be 2.
If N is divisible by 4 but not by 8, the number is 3.
And so on... We must find the largest power of 2 that's a factor
of N.
(define (hanoi-number n)
(if (odd? n)
1
(+ 1 (hanoi-number (/ n 2)))))
(define hanoi (stream-map hanoi-number integers))
Third category (three correct solutions):
One way to characterize the infinite Hanoi stream is that it's
(stream-append (hanoi-stream 3) (everything-starting-with-4))
(1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
(1 2 1 3 1 2 1) (4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
Since the first argument to stream-append is finite, this is a reasonable
thing to try to compute. The second argument has a funny asymmetrical
shape, though. (Remember that there's more than one 4 in the infinite
stream, but we're singling out the first one as special.) What's in that
right part? It's
* The number 4
* then another copy of (hanoi-stream 3)
* and then (everything-starting-with-5).
(4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
4 (1 2 1 3 1 2 1) (5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
Clearly instead of picking a specific number such as 4, we need a general
function for the right part starting with any number.
(define (right-part n)
(cons-stream n
(stream-append (hanoi-stream (- n 1))
(right-part (+ n 1)))))
In particular, if we take n=1, the left part is empty, so we can
forget about it:
(define hanoi (right-part 1))
Fourth category (two correct solutions):
Let's look at the infinite Hanoi stream again.
(1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
Every other number is 1, so let's think about interleaving ONES with
something:
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)
( 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 ...)
In that second stream, every other number is 2, so if we had a TWOS stream
we could interleave it with something else:
( 2 2 2 2 2 2 2 2 2 ...)
( 3 4 3 5 3 4 3 6 ...)
But in *that* new stream, every other number is 3... A pattern emerges.
First we need a way to make an infinite stream of all the same N, for
any N:
(define (n-stream n)
(cons-stream n (n-stream n)))
At this point it's easy to make a mistake, as follows:
(define (bad-hanoi-substream n)
(interleave (n-stream n)
(bad-hanoi-substream (+ n 1))))
(define hanoi (bad-hanoi-substream 1)) ;;; wrong!
The problem is that INTERLEAVE is an ordinary procedure, not a special
form, so it doesn't delay its second argument as CONS-STREAM does.
If you run this program it'll loop forever without returning a stream.
There are two ways to solve this. One is to use explicit delays:
(define (hanoi-substream-delayed n)
(interleave-delayed (n-stream n)
(delay (hanoi-substream (+ n 1)))))
(define hanoi (hanoi-substream-delayed 1))
The other solution is to rearrange the order so that we use an
explicit CONS-STREAM in the definition:
(define (hanoi-substream n)
(cons-stream n
(interleave (hanoi-substream (+ n 1))
(n-stream n))))
(define hanoi (hanoi-substream 1))
Note that interchanging the order of the arguments to interleave
is necessary to counteract the extra N at the beginning.
Fifth category (two correct solutions):
As in the fourth category, we notice that ones are interleaved with
non-ones:
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)
( 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 ...)
Subtract 1 from every element of that second stream, and what do you get?
( 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 ...)
Hey! It's the infinite Hanoi stream! With this insight we don't even
have to write a procedure; we can use an implicit recursion based on
the stream's name.
Again we have to be careful either to use INTERLEAVE-DELAYED or to start
with an explicit CONS-STREAM:
(define hanoi (cons-stream 1 (interleave (stream-map + hanoi ones)
ones)))
Scoring: Two points for a correct solution. There were three basic
categories of incorrect solution:
(a) Ones that would work in a normal-order Scheme, namely the ones
we had to fix with explicit DELAYs: one point, because the math is
correct and it's a Scheme deficiency that gets in the way.
(b) Streams of streams, e.g., ((1) (2 1) (3 1 2 1) (4 1 2 1 3 1 2 1) ...)
(c) Wrong sequences, e.g., (1 2 1 2 1 2 1 2 ...)
No points for (b) or (c).