% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, April 16}

{\Large\bf 1. Streams}

In lecture yesterday, we looked at a simple implementation of streams
which used two new special forms:
\begin{itemize}
\itemx {\cf (delay x)} which returns a promise and is equivalent to {\cf (lambda () x)}
\itemx {\cf (cons-stream a b)} which is equivalent to {\cf (cons a (delay b))}
\end{itemize}
and a few data abstrations:

\begin{tabular}[t]{p{3.5in}p{3in}}
\beginlisp
(define (force obj) (obj))
\endlisp & \beginlisp
(define (stream-car stream) (car stream))
\endlisp
\\
\beginlisp
(define (stream-cdr stream) (force (cdr stream)))
\endlisp
\end{tabular}

Using these basic functions, we can build infinite streams.  For example:

\begin{tabular}[t]{p{3.5in}p{3.5in}}
\beginlisp
(define ones (cons-stream 1 ones))
\endlisp & \beginlisp
(define twos (cons-stream 2 twos))
\endlisp
\end{tabular}

Here's another way we can define {\tt twos} using {\tt stream-map} a
very useful function that works like {\tt map}, except on streams:

\beginlisp
(define twos
  (stream-map + ones ones))
\endlisp

{\Large\bf 2. Warm Up}

Write a procedure {\cf powers-of-2-from} which takes a power of 2
({\cf n}) and returns the stream n, n*2, (n*2)*2, ((n*2)*2)*2, ...

\beginlisp
(define (powers-of-2-from n)
\ANSWER{
  (cons-stream n (powers-of-2-from (* 2 n)))
})
\endlisp

Define a stream of the whole numbers N = \{0, 1, 2, 3 ...\} using
ones

\beginlisp
(define whole  
\ANSWER{
  (cons-stream 0 (stream-map + whole ones))
})
\endlisp

{\Large\bf 3. Taylor Series}

We can represent an infinite Taylor Series as a stream.  The series 
$f(x) = (a_0 x + a_1 x + a_2 x^2 + a_3 x^3 + \ldots) $
can simply be represented as the stream of numbers 
$(a_0 \; a_1 \; a_2 \; a_3 \; \ldots)$.

Recall that (for $-1 < x < 1$), $\;\;f(x) = \frac{1}{1-x} = 1 + x + x^2 +
x^3 + \ldots$.  What series could we use to represent this series?
\ANSWER{ones}

For example, recall that $e^x = 1 + x + \frac{x^2}{2!} +
\frac{x^3}{3!} + \frac{x^4}{4!} + \ldots$.  Using {\tt stream-map},
{\tt fact} (factorial), and {\tt whole}, define the stream corresponding
to this series.

\beginlisp
(define e\^{}x
\ANSWER{
  (stream-map
    (lambda (n) (/ 1 (fact n)))
    whole)
})
\endlisp

\newpage
{\Large\bf 4. Evaluating a Series}

Now say we want to evaluate $e^x$ for some $x$.  Write a function 
{\tt eval-series} that takes a series {\tt s}, a value {\tt x}, and
the number of terms to use {\tt n}, and evaluates the series.

\beginlisp
(define (eval-series s x n)
\ANSWER{
  (define (iter s count ans) 
    (if (= count n)
        ans
        (iter (stream-cdr s) 
              (+ count 1) 
              (+ ans (* (stream-car s) (expt x count))))))
  (iter s n 0 0)
})
\endlisp

Now we can evaluate our series: 
\beginlisp
(eval-series e\^{}x -0.5 100)     ; value .6065306597126333
\endlisp

{\Large\bf 5. More Stream Tools}

Write the function {\tt interleave} that takes two infinite streams
and interleaves them.  For example 

\beginlisp
(define all-ints 
  (cons-stream 0 (interleave integers (stream-map - integers))))
\endlisp

This would be the infinite stream (0 1 -1 2 -2 3 -3 4 -4 $\ldots$)

\beginlisp
(define (interleave s t)
\ANSWER{
     (cons-stream (stream-car s)
                  (interleave s (stream-cdr t)))
})
\endlisp

{\Large\bf 6. Cosine Series}

For example, recall that $cos(x) = 1 - \frac{x^2}{2!} +
\frac{x^4}{4!} - \frac{x^6}{6!} + \ldots$.  How could we create this
stream using the {\tt e\^{}x} stream we already created?  (What stream
could we create that we could multiply with {\tt e\^{}x}?)

\begin{tabular}{cccccccccccccccc}
$e^x$ & = & 1 & $+ x$ & $+ \frac{x^2}{2!} $ & $+ \frac{x^3}{3!}$
& $+ \frac{x^4}{4!}$
& $+ \frac{x^5}{5!}$
& $+ \frac{x^6}{6!}$ & $+ \ldots$ \\ 
$cos(x)$ & = & 1 & $+ 0$ & $- \frac{x^2}{2!}$ & $+ 0$ 
& $+ \frac{x^4}{4!}$  
& $+ 0$
& $- \frac{x^6}{6!}$ & $+ \ldots$ \\
\hline
& & \ANSWER{1} & \ANSWER{0} & \ANSWER{-1} & \ANSWER{0} & \ANSWER{1} & \ANSWER{0} & \ANSWER{-1} & $\ldots$
\end{tabular}

How could we define the cosine stream in this way using {\tt ones} and
{\tt zeros} and {\tt interleave} twice?

\beginlisp
(define cos-x \ANSWER{
  (stream-map * e\^{}x 
    (interleave (interleave ones (stream-map - ones)) zeros))
})
\endlisp

{\Large\bf 7. All Pairs}

What about the set of all pairs of positive integers:
$\{ \langle x,y \rangle \; | \; x, y \in Positive Integers \}$?  
How can we capture this infinite-way infinite sequence into a stream? 
Let's define a procedure {\tt pairs} that takes two infinite streams
and returns a stream of all possible pairs of elements of the two
streams.  

\begin{tabular}{p{3.5in}p{3.5in}}
\vspace{-0.7in}
\beginlisp
(define (pairs s t)
\ANSWER{
  (cons-stream 
     (list (stream-car s) (stream-car t))
     (interleave 
        (stream-map 
          (lambda (x) (list (stream-car s) x))
          (stream-cdr t))
        (pairs (stream-cdr s) t))
}))
\null
\endlisp
&
\begin{tabular}{c|cccccc}
  & 1 & 2 & 3 & 4 & 5 & \ldots \\
\hline
1 & 
$\langle 1,1 \rangle $ &
$\langle 1,2 \rangle $ & 
$\langle 1,3 \rangle $ &
$\langle 1,4 \rangle $ &
$\langle 1,5 \rangle $ & \ldots\\
2 &
$\langle 2,1 \rangle $ &
$\langle 2,2 \rangle $ & 
$\langle 2,3 \rangle $ &
$\langle 2,4 \rangle $ &
$\langle 2,5 \rangle $ & \ldots \\
3 &
$\langle 3,1 \rangle $ &
$\langle 3,2 \rangle $ & 
$\langle 3,3 \rangle $ &
$\langle 3,4 \rangle $ &
$\langle 3,5 \rangle $ & \ldots \\
4 & 
$\langle 4,1 \rangle $ &
$\langle 4,2 \rangle $ & 
$\langle 4,3 \rangle $ &
$\langle 4,4 \rangle $ &
$\langle 4,5 \rangle $ & \ldots \\
5 &
$\langle 5,1 \rangle $ &
$\langle 5,2 \rangle $ & 
$\langle 5,3 \rangle $ &
$\langle 5,4 \rangle $ &
$\langle 5,5 \rangle $ & \ldots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
\end{tabular}
\end{tabular}




\end{document}
