% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, February 24}

{\Large\bf 1. Abstracting Common Patterns}


\begin{tabular}{p{3in}p{3.5in}}
{
\beginlisp
(define (map proc seq)
  (if (null? seq)
      nil
      (cons (proc (car seq))
            (map proc (cdr seq)))))
\null
(define (accumulate op init seq)
  (if (null? seq)
      init
      (op (car seq)
        (accumulate op init (cdr seq)))))
\endlisp
} & {
\beginlisp
(define (filter pred seq)
  (if (null? seq)
      nil
      (let ((rest (filter pred (cdr seq))))
         (if (pred (car seq))
             (cons (car seq) rest)
             rest))))
\endlisp
}
\end{tabular}

{\Large\bf 2. List Warm-Up}

Write the following procedures using map, filter, and accumulate (no
recursion!).

\begin{tabular}{|p{2in}|p{2in}|p{2.5in}|}
Description & Example & Definition \\
\hline
{\tt square-list}: squares all the elements in a list
&
\beginlispA
(square-list (list 1 2 3)) 
==> (1 4 9)
\endlisp
&
\beginlispA
(define (square-list x)
\ANSWER{   (map square x)
})
\endlisp
\\
\hline
{\tt apply-all}: takes a list of procs and 
an item, and returns a list of applying
each procedure to the item. 
&
\beginlispA
(apply-all 
  (list sqrt square fact) 4)
    ==> (2 16 24) 
\endlisp
& 
\beginlispA
(define (apply-all ops x) 
\ANSWER{  (map (lambda (op) (op x)) ops)  }
)
\endlisp
\\
\hline
{\tt length}: length of a list
&
\beginlispA
(length (list 1 2 3)) 
==> 3 
\endlisp
&
\beginlispA
(define (length x)
\ANSWER{  (accumulate 
    (lambda (a b) (+ 1 b)) 
    0 x)
})
\endlisp
\\
\hline
{\tt mean}: mean of a list
&
\beginlispA
(mean (list 1 2 3 4 5)) 
==> 3 
\endlisp
&
\beginlispA
(define (mean x)
\ANSWER{  (/ (accumulate + 0 x)
      length x))
})
\endlisp
\\
\hline
{\tt range}: range of a list (max elt minus min elt)
&
\beginlispA
(range (list 1 2 3 4 5)) 
==> 4
\endlisp
&
\beginlispA
(define (range x)
\ANSWER{  (- (accumulate max (car x) x)
     (accumulate min (car x) x))
})
\endlisp
\\
\hline
{\tt element?}: returns true if elt is an element of x
&
\beginlispA
(element? (list 1 2 3 4) 3) 
==> \#t
\endlisp
&
\beginlispA
(define (element? x elt)
\ANSWER{  (not (null? 
        (filter (lambda (y) (= elt y)) 
                x)))
})
\endlisp
\\
\hline
{\tt map}: map a function over a list of elements
&
\beginlispA
(map double (list 1 2 3))
==> (2 4 6)
\endlisp
&
\beginlispA
(define (map proc x)
\ANSWER{  (accumulate 
    (lambda (a b) (cons (proc a) b))
    nil
   x)
})
\endlisp
\\
\hline

\end{tabular}

{\Large\bf 3. Depth of a Tree}

Write a function {\tt depth} that takes a tree and returns the maximum
depth of the tree.  Note that this is equivalent to the maximum number
of parenthesis open at any given time when scheme prints the tree.
For example, 
\beginlisp
(depth (list 1 (list (list 2) 3) (list 4))) ==> 3
\endlisp

\beginlisp
(define (depth tree)
\ANSWER{
  (cond ((pair? tree)
         (max
          (+ 1 (depth (car tree)))
          (depth (cdr tree))))
        (else 0))
})
\endlisp

Now write {\tt depth} using map and accumulate...

\beginlisp
(define (depth tree)
\ANSWER{
  (if (not (pair? tree))
      0
      (+ 1 (accumulate max
           0 
           (map depth tree))))
})
\endlisp

{\Large\bf 4. Deep Reverse}

So far, we've been working on lists, while we've ignored the elements
of the list.  What does the following return? \\
{\tt (reverse (list 1 (list 2 3) (list 4 5 6)))}

Write a function {\tt deep-reverse} that when called on the above tree
will reverse all the elements.
{\tt (deep-reverse (list 1 (list 2 3) (list 4 5 6))) ==> ((6 5 4) (3 2) 1)}

\beginlisp
(define (deep-reverse x)
\ANSWER{
  (define (aux x ans)
    (cond ((null? x) ans)
	   ((not (pair? x)) x)
           (else 
	    (aux (cdr x) (cons (deep-reverse (car x)) ans)))))
  (aux x nil)
})
\endlisp

Now write {\tt deep-reverse} using map...

\beginlisp
(define (deep-reverse x)
\ANSWER{
  (if (not (pair? x)) 
      x
      (map deep-reverse (reverse x)))
})
\endlisp

\vskip .1in

% {\Large\bf 5. Flatten}



{\Large\bf 6. Sieve of Eratosthenes}

Let's walk through the process of the sieve of Eratosthenes one more
time..   

\begin{center}
\begin{tabular}{ccccccccccccccc}
   &  2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 \\
16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\
\end{tabular}
\end{center}

\beginlisp
(define (sieve lst)
  (if (null? lst) 
      nil
      (cons (car lst)
            (sieve (filter (lambda (x) (not (divisible? x (car lst))))
                           (cdr lst))))))
\endlisp

% \beginlisp
% (sieve (generate 2 25)) ==> (2 3 5 7 11 13 17 19 23)
% \endlisp

\end{document}



