% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input 6001mac.tex

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Wednesday, February 25}

{\Large\bf 1. Student Presentation}

Using box and pointer notation, explain how map works. In particular,
use a simple example of applying map to a list, e.g.

\beginlisp
(map (lambda (x) (* x 2)) (list 1 2 3))
\endlisp

and show at each stage what box and pointer structures are present and
which ones are arguments to a call to map . 

\vskip .05in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

{\tt Map} takes a procedure and a list as arguments, and returns a
list of the results of applying the procedure to each item in the list.
Using {\tt map}, write a procedure {\tt apply-all} that takes a list
of procedures and an item as arguments and returns a list of the results
of applying each procedure to the item.

\beginlisp
$==>$ (apply-all (list sqrt square cube factorial fib) 4)
(2 16 64 24 3)
\endlisp

\beginlisp
(define (apply-all ops x) 
%    (map (lambda (op) (op x)) ops)
\null
)
\endlisp

\vskip .1in

{\Large\bf 3. Recursive Append}

Let's take a closer look at the procedure {\tt append} that was
introduced in lecture:

\beginlisp
(define (append a b)
  (if (null? a)
      b
      (cons (car a) (append (cdr a) b))))
\endlisp

Draw the box and pointer diagrams for 
{\tt (append (list 1 2) (list 3 4 5))}.  Notice that the second list
is never looked at!

\vskip .1in

{\Large\bf 4. Copy}

Consider the procedure {\tt copy} which takes a list and returns a
copy of the list.  How do each of the following differ?

\beginlisp
(define (copy-ident x) x)
\null
(define (copy-map x) (map (lambda (y) y) x))
\null
(define (copy-recurse x)
  (if (null? x)
      nil
      (cons (car x) (copy-recurse (cdr x)))))
\endlisp

\newpage
Notice that {\tt copy-map} and {\tt copy-recurse} are both recursive
processes.  Let's write an iterative copy:

\beginlisp
(define (copy-iter x)
\null
\null
\null
\null
\null
)
\endlisp
% {\bf Warning: the below is not copy!}
% 
% \beginlisp
% (define (*copy-iter* x)
%   (define (aux x ans) 
%     (if (null? x)
%         ans
%         (aux (cdr x) (cons (car x) ans))))
%   (aux x nil))
% \endlisp
% 
% {\bf The above is not copy.  Actually, it's reverse!}
%
% \beginlisp
% (define (copy-iter x) (reverse (reverse x)))
% \endlisp

\vskip .1in

{\Large\bf 5. Iterative Append}

Given what we learned about iterative vs. recursive processes
operating on lists, write an iterative version of append.

\beginlisp
(define (append a b)
%  (define (aux x ans)
%    (if (null? x)
%        ans
%        (aux (cdr x) (cons (car x) ans))))
%  (aux (reverse a) b)
\null
\null
\null
\null
\null
)
\endlisp

\vskip .1in

{\Large\bf 6. Lists Vs. Trees}

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)
%  (cond ((null? x) nil)
%        ((not (pair? x)) x)
%        (else 
%          (cons (deep-reverse (car x))
%                (deep-reverse (cdr x)))))
\null 
\null 
\null 
\null 
\null 
)
\endlisp

\vskip .1in

{\Large\bf 7. More Trees}

Write the function {\tt fringe} that takes a tree structure and returns a flat
list of the leaves of the tree.  For example \\
{\tt (fringe (list 1 (list 2) 3)) ==> (1 2 3)}

\beginlisp
(define (fringe x)
%  (cond ((null? x) nil)
%        ((not (pair? x)) (list x))
%        (else 
%          (append (fringe (car x))
%                  (fringe (cdr x)))))
\null
\null
\null
\null
\null
)
\endlisp

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
