% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, February 12}

{\Large\bf 1. Cons Pairs and Lists}

Recall the contract for {\tt cons}, {\tt car}, {\tt cdr}, {\tt pair?},
and {\tt null?}.

\begin{tabular}{p{3in}p{3in}}
{
\beginlisp
(car (cons a b)) == a 
(cdr (cons a b)) == b
(pair? (cons a b)) == \#t
(null? nil) == \#t
\endlisp
} & {
\beginlisp
(list a b c) ==  (cons a 
                    (cons b 
                       (cons c nil)))
\endlisp
}
\end{tabular}

\vspace{-0.1in}

There are three main methods of representing cons and list
structures.  You should be able to convert between them.

\begin{tabular}{|p{2in}|p{2in}|p{2in}|}
Scheme Expression & Box \& Pointer & Scheme Printout \\
\hline
(cons 1 2) & \vspace{0.1in}  & \ANSWER{(1 . 2)}  \\
\hline
(cons 1 (cons 2 nil)) & \vspace{0.1in}   & \ANSWER{(1 2)} \\
\hline
(cons 1 nil) &  \vspace{0.1in}           & \ANSWER{(1)}  \\
\hline
(cons 1 (cons 2 3)) & \vspace{0.1in}       & \ANSWER{(1 2 . 3)} \\
\hline
(cons (cons 1 2) nil) &  \vspace{0.1in}     & \ANSWER{((1 . 2))} \\ 
\hline
(list 1 2 3 4) &  \vspace{0.1in}               & \ANSWER{(1 2 3 4)} \\ 
\hline
(list 1 (cons 2 3) (list 4 5)) & \vspace{0.1in} & \ANSWER{ (1 (2 . 3) (4 5))} \\
\hline
\end{tabular}

\vspace{0.1in}
{\Large\bf 2. Other Accessors}

In scheme, we often want to access elements deep in a cons structure.
Therefore, the following accessors have been defined to help us out:

\begin{tabular}{p{3in}p{3in}}
{
\beginlisp
(cadr x)  == (car (cdr x))
(caddr x) == (car (cdr (cdr x)))
(cdaar x) == (cdr (car (car x)))
\endlisp } & {
\beginlisp
(cddr x)   == (cdr (cdr x))
(cdadar x) == (cdr (car (cdr (car x))))
etc, etc...
\endlisp
}
\end{tabular}


For lists, we also often want to easily access the n'th element of a
list.  The accessors {\tt first}, {\tt second}, {\tt third}, ...,
{\tt tenth} are defined to access the corresponding values of a list.
For example,

\beginlisp
(sixth (list 1 2 3 4 5 6 7 8 9)) 
;Value: 6
\endlisp

How could you define {\tt first}, {\tt second}, {\tt third}, and {\tt
fourth} using the {\tt c???r} functions?

\begin{tabular}{p{3in}p{3in}}
{
\beginlisp
(first x)  == \ANSWER{(car x)}
(second x) == \ANSWER{(cadr x)} 
\endlisp
} & {
\beginlisp
(third x)  == \ANSWER{(caddr x)}
(fourth x) == \ANSWER{(cadddr x)}
\endlisp
}
\end{tabular} 

\newpage
{\Large\bf 3. Practice}

Draw box and pointer diagrams and write what will Scheme print for
the following expressions.

\beginlisp
$\Rightarrow$ (define x (cons 5 2))
$\Rightarrow$ (car x)
\ANSWER{;Value: 5}
$\Rightarrow$ (cdr x)
\ANSWER{;Value: 2}
$\Rightarrow$ (car (cdr x))
\ANSWER{;Error: 2 passed car}
$\Rightarrow$ (define y (cons sqrt x))
$\Rightarrow$ (car (cdr y))
\ANSWER{;Value: 5}
$\Rightarrow$ (car y)
\ANSWER{;Value: \#[compiled-procedure 24]}
$\Rightarrow$ (define z (cons ((car y) 49) x))
$\Rightarrow$ z
\ANSWER{;Value: (7 5 . 2)}
\endlisp

\vskip 0.10in

Write a Scheme expression that will print each of the following.
Also draw box and pointer diagrams.

\beginlisp
$\Rightarrow$ \ANSWER{(list 1 2 3)}
;Value: (1 2 3)
$\Rightarrow$ \ANSWER{(cons 1 (cons 2 3))}
;Value: (1 2 . 3)
$\Rightarrow$ \ANSWER{(cons (list 1 (list 2)) 3)}
;Value: ((1 (2)) . 3)
\endlisp

\vskip 0.10in

Write Scheme expressions that correspond to the following.

\begin{tabular}{p{2.5in}p{2.5in}}
\psfig{figure=r04-2.ps,height=1in} &
\psfig{figure=r04-3.ps,height=0.75in} 
\\
\vspace{-0.2in}
{
\beginlisp
\ANSWER{(define c (list 3 4))}
\ANSWER{(define a (cons 1 c))}
\ANSWER{(define b (cons 2 c))}
\endlisp
} & 
\vspace{-0.1in}
{
\ANSWER{Trick Question!  We can't do this yet!}
}
\end{tabular}

\vspace{-0.15in}

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

{\Large\bf 4. Functions on Lists}

We saw that we have the primitive function {\tt pair?} to see if an
object is a pair.  What if we wanted to write the function {\tt list?}
to see if an object is a list?  

What is the contract for {\tt list?}
$\forall x_1, x_2, \ldots, x_n \;\;\;$
  {\tt (list? (list $x_1$ $x_2$ $\ldots$ $x_n$)) == \#t}

What's another way to write it?  
\beginlisp
(list? nil) == \#t
(list? (cons $x$ $l$)) == \#t   ==>   (list? $l$)
\endlisp

Now, how can we write {\tt list?} in scheme?

\vspace{-0.1in}

\beginlisp
(define (list? x)
\ANSWER{
  (or (null? x)
      (and (pair? x)
           (list? (cdr x))))
})
\endlisp

\vspace{0.1in}

What is the Order of Growth of {\tt pair?} and {\tt list?} ?

{\tt pair?} is $\Theta(\ANSWER{1})$ and {\tt list?} is
$\Theta(\ANSWER{n})$\ANSWER{, where $n$ is the length of the list.}

\end{document}



