\documentstyle[6.001-ps]{article}
\begin{document}
\header{7}{April 12, 1989}
\part{1: Homework exercises}
\exercise{7.1}
\bv
(define (accumulate-n op init streams)
  (if (empty-stream? (head streams))
      the-empty-stream
      (cons-stream
       (accumulate op init (map head streams))
       (accumulate-n op init (map tail streams)))))
\end{verbatim}
\exercise{7.2}
\bv
(define (dot-product v w)
  (accumulate + 0 (accumulate-n * 1 (cons-stream v
                                     (cons-stream w
                                      the-empty-stream)))))

(define (matrix-times-vector m v)
  (map (lambda (x) (dot-product x v)) m))

(define (transpose mat)
  (accumulate-n cons-stream the-empty-stream mat))

(define (matrix-times-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x) (matrix-times-vector cols x)) m)))
\end{verbatim}
\exercise{7.3}
\begin{enumerate}
\item[(a)]
\verb+(define x (map show (enumerate-interval 0 10)))+
\begin{quote}
In this case, \verb+x+ is defined as the result of evaluating a
combination. \verb+map+ and \verb+show+ evaluate to compound procedures.
The last element is another combination.  The arguments evaluate
to \verb+0+ and \verb+10+, and \verb+enumerate-interval+ evaluates
to a compound procedures.  The function \verb+enumerate-interval+ is
evaluated with \verb+0+ and \verb+10+ as parameters.  The \verb+if+
special form evaluates to a \verb+cons-stream+.  This special form
returns a cons of \verb+0+ and a ``black box'' delayed execution.
When \verb+map+ is called, it too evaluates a \verb+cons-stream+, where the
first argument is evaluated immediately (this is where the \verb+0+ is
actually printed) and returns \verb+0+, and the second argument is a
delayed evaluation of \verb+(map proc (tail stream))+.
This the end of the read-eval-print loop.  The \verb+X+ is printed
because the \verb+define+ returns the name of what was defined.
\end{quote}
\item[(b)]
\bv
(head x)
;Value: 0
\end{verbatim}
\begin{quote}
Quite simply, \verb+x+ already has it's \verb+car+ evaluated.  This is
\verb+0+, and is printed.
\end{quote}
\bv
(tail x)
1+
;Value: (1 . #[DELAYED #xBEF08])
\end{verbatim}
\begin{quote}
This is more complex.  When \verb+tail+ is evaluated, the delayed evaluation
of the second half of the \verb+cons-stream+ is forced.  This results in
the evaluation of the delayed \verb+map, which in turn results in the
evaluation of a \verb+show+ (which prints the \verb+1+) and returns
the \verb+cons-stream+ of \verb+1+ (the return value of the \verb+show+)
and \verb+(map proc (tail stream))+ (which, of course, is delayed).  Basically,
this is all what happens when the initial \verb+define+ is executed.
\end{quote}
\item[(c)]
\bv
(nth-stream 5 x)
2 
3 
4 
5 
;Value: 5
\end{verbatim}
\begin{quote}
When \verb+nth-stream+ is called, each element in the stream (up to
the nth) is evaluated by \verb+tail+.  The first two elements just
evaluate to \verb+0+ and \verb+1+.  Each element after that evaluates
to a \verb+map+ (see part b) which prints the element before it returns it.
The function itself returns the value of the nth element (where the
first element is element 0).
\end{quote}
\bv
(nth-stream 7 x)
6
7
;Value: 7
\end{verbatim}
\begin{quote}
This prints what it does for the same reason that the previous example
prints what it did.  The first 6 elements of the stream have already
been \verb+map+ped, and the next two had not been.  The nth element is
again returned.
\end{quote}
\end{enumerate}
\exercise{7.4}
\bv
(define s (cons-stream 1 (merge (scale-stream 2 s)
                                (merge (scale-stream 3 s)
                                       (scale-stream 5 s)))))
\end{verbatim}
\exercise{7.5}
\begin{tabular}{r@{$\Longrightarrow$}l}
\verb+x+ & \verb+1 1 2 3 4+ \\
\verb+y+ & \verb+1 2 3 4 8+
\end{tabular}
\parttext{Laboratory: Streams}
\problem{7.1}
\bv
(define (interleave-pairs s t)
  (cons-stream (list (head s) (head t))
               (interleave
                (map (lambda (x) (list (head s) x)) (tail t))
                (interleave-pairs (tail s) (tail t)))))
\end{verbatim}
\vbreak
Basically, the pairs are ordered such that all of the pairs under
a given row are interleaved in the pairs in that row.  Of course, that
whole sequence is interleaved in the row above it, etc.  Here is
a function which will compute the number of pairs before a given pair:
\vbreak
\bv
(define (precede p q)
  (define (toobig a b)
    (if (= a 1)
        (if (= b 1)
            2
            (-1+ (* 2 b)))
        (* 2 (toobig (-1+ a) (-1+ b)))))
  (- (toobig p q) 2))

(precede 1 1)
;Value: 0

(precede 1 100)
;Value: 197

(precede 99 100)
;Value: 950737950171172051122527404030

(precede 100 100)
;Value: 1267650600228229401496703205374
\end{verbatim}
\problem{7.2}
\bv
(define (merge-weighted s1 s2 weight)
  (let ((wh1 (weight (head s1)))
        (wh2 (weight (head s2))))
    (if (< wh1 wh2)
        (cons-stream (head s1) (merge-weighted (tail s1) s2 weight))
        (cons-stream (head s2) (merge-weighted s1 (tail s2) weight)))))
\end{verbatim}
\problem{7.3}
\begin{enumerate}
\item
\bv
(define x (weighted-pairs integers integers (lambda (i j) (+ i j))))
;Value: X

(stream-first 10 x)
(1 1) 
(1 2) 
(2 2) 
(1 3) 
(2 3) 
(1 4) 
(3 3) 
(2 4) 
(1 5) 
(3 4) 
\end{verbatim}
\item
\bv
(define (not-div-235? x)
  (and (> (remainder x 2) 0)
       (and (> (remainder x 3) 0)
            (> (remainder x 5) 0))))
;Value: NOT-DIV-235?

(define not-235 (filter not-div-235? integers))
;Value: NOT-235

(define y (weighted-pairs not-235 not-235
                          (lambda (i j) (+ (* 2 i) (* 3 j) (* 5 i j)))))
;Value: Y

(stream-first 10 y)
(stream-first 15 y)
(1 1) 
(1 7) 
(1 11) 
(1 13) 
(1 17) 
(1 19) 
(1 23) 
(1 29) 
(1 31) 
(7 7) 
(1 37) 
(1 41) 
(1 43) 
(1 47) 
(1 49) 
\end{verbatim}
\end{enumerate}
\problem{7.4}
\bv
(define (combine-same-weights pairs pair-weight)
  (define (p-weight p)
    (pair-weight (car p) (cadr p)))
  (let ((head-weight (p-weight (head pairs))))
    (define (pairs-of-weight pairs)
      (if (= (p-weight (head pairs)) head-weight)
          (cons (head pairs) (pairs-of-weight (tail pairs)))
          '()))
    (define (pairs-after-weight pairs)
      (if (= (p-weight (head pairs)) head-weight)
          (pairs-after-weight (tail pairs))
          pairs))
    (cons-stream (cons head-weight (pairs-of-weight pairs))
                 (combine-same-weights (pairs-after-weight pairs)
                                       pair-weight))))

(define z (combine-same-weights x +))
;Value: Z

(stream-first 10 z)
(2 (1 1)) 
(3 (1 2)) 
(4 (2 2) (1 3)) 
(5 (2 3) (1 4)) 
(6 (3 3) (2 4) (1 5)) 
(7 (3 4) (2 5) (1 6)) 
(8 (4 4) (3 5) (2 6) (1 7)) 
(9 (4 5) (3 6) (2 7) (1 8)) 
(10 (5 5) (4 6) (3 7) (2 8) (1 9)) 
(11 (5 6) (4 7) (3 8) (2 9) (1 10)) 
\end{verbatim}
\problem{7.5}
\begin{enumerate}
\item[(a)]
\bv
(define (stream-get-car n s)
  (filter (lambda (x) (= (car x) n)) s))
;Value: STREAM-GET-CAR

(head (stream-get-car 12 (same-weight-pairs integers integers +)))
;Value: (12 (6 6) (5 7) (4 8) (3 9) (2 10) (1 11))
\end{verbatim}
\item[(b)]
\bv
(define x (filter (lambda (x) (> (remainder x 3) 0)) integers))
;Value: X

(head (stream-get-car 32 (same-weight-pairs x x +)))
;Value: (32 (16 16) (13 19) (10 22) (7 25) (4 28) (1 31))
\end{verbatim}
\end{enumerate}
\problem{7.6}
\bv
(define (stream-get-multiple-cdr s)
  (filter (lambda (x) (not (null? (cddr x)))) s))
;Value: STREAM-GET-MULTIPLE-CDR

(define ramanujan (same-weight-pairs integers integers
                                     (lambda (i j) (+ (cube i) (cube j)))))
;Value: RAMANUJAN

(stream-first 5 (stream-get-multiple-cdr ramanujan))
(1729 (9 10) (1 12)) 
(4104 (9 15) (2 16)) 
(13832 (18 20) (2 24)) 
(20683 (19 24) (10 27)) 
(32832 (18 30) (4 32)) 
\end{verbatim}
\problem{7.8}
Ben's method attempts to streamline the process of deriving
Ramanujan numbers.  At the very least, it is simpler.  The streams
go througe the following stages:
\begin{itemize}
\item the ``source'' stream is the stream of integers
\item a stream of all possible pairs (of integers) is generated
\item a stream of $i^{3}+j^{3}$ for each pair is generated
\item a stream of all possible pairs of these integers is generated
\item a stream of all pairs where $i=j$ is generated
\item a stream of these integers is generated
\end{itemize}
This final stream is the Ramanujan number stream.  It should generate
the same series of numbers as Problem 7.6.
\problem{7.9}
Louis's function will never return.  When the combination \verb+(map . . . )+
is evaluated, \verb+unique-pairs is called recursively.  Because 
\verb+s+ is an infinite stream, \verb+(tail s)+ is always defined,
and the function will never return.
\problem{7.10}
Ben's definition takes so long to run because \verb+unique-pairs+ must be run
not only on the list of integers, but on the list of cubes as well.
Unfortunately, \verb+unique-pairs+ is ${\cal O}(n^{2})$, so
\verb+ben-ramanujan-numbers+ is at least an ${\cal O}(n^{4})$
algorithm in time.  To get to the first number, \verb+unique-pairs+
has to grind through something like 1.5 billion iterations.
This is the value of \verb+(precede (precede 1 12) (precede 9 10))+ from
Problem 7.1.
\end{document}
