% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

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

{\Large\bf 1. Review of Lists}

Let's look at simple operations on lists.  Say I define a list as
follows:

\beginlisp
(define primes (list 2 3 5 7))
\endlisp

How could I make the following lists using {\tt primes}? 

\begin{tabular}{p{1.3in}p{1.0in}p{3.7in}}
{\tt non-composites} & (1 2 3 5 7) &
{\small \tt (define non-composites \ANSWER{(cons 1 primes)}~~~~~~~~~~)}
\vspace{0.05in}
\\
{\tt odd-primes} & (3 5 7) &
{\small \tt (define odd-primes \ANSWER{(cdr primes)}~~~~~~~~~~~~~~~~~)}
\vspace{0.05in}
\\
{\tt more-primes} & (2 3 5 7 11) &
{\small \tt (define more-primes \ANSWER{(append primes (list 11))}~~~)}
\vspace{0.05in}
\\
{\tt less-primes} & (2 3 5) &
{\small \tt (define less-primes \ANSWER{(lrange primes 0 2)}~~~~~~~~~)}

\end{tabular}



{\Large\bf 2. Simple 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{
  (cond ((null? x) \#t)
        ((pair? x) (list? (cdr x)))
        (else \#f))
})
\endlisp
%  (or (null? x)
%      (and (pair? x)
%           (list? (cdr x))))


\vspace{0.05in}

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

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

\vspace{0.05in}

{\Large\bf 3. More Functions on Lists}

What if we wanted to reference the $n^{th}$ element of a list?  Write
the function {\tt list-ref} that takes a list {\tt x} and an integer
{\tt n} and returns the $n^{th}$ element of the list {\tt x}.

\beginlisp
(define (list-ref x n)
\ANSWER{
  (if (= n 0)
      (car x)
      (list-ref (cdr x) (- n 1)))
})
\endlisp

Write the function {\tt length} that takes a list {\tt x} and returns
the length of the list.  Is your function iterative or recursive?
Write the other one too!

\begin{tabular}{p{3in}p{3in}}
{\beginlisp
(define (length x)
\ANSWER{
   (if (null? x)
       0
       (+ 1 (length (cdr x))))
}
)
\endlisp
} & {
\beginlisp
(define (length x)
\ANSWER{
   (define (iter x n)
     (if (null? x) n 
         (iter (cdr x) (+ n 1))))
   (iter x 0)
})
\endlisp
}
\end{tabular}

{\Large\bf 4. Recursive Append}

Consider the procedure {\tt append} that takes two lists and returns a
list that results from appending the second to the first.

\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 5. 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-recurse x)
  (if (null? x)
      nil
      (cons (car x) (copy-recurse (cdr x)))))
\endlisp

Notice that {\tt copy-recurse} is a recursive process.  Let's write an
iterative copy:

{\bf \ANSWER{Warning: the below is not copy!}}

\beginlisp
(define (*copy-iter* x)
\ANSWER{
  (define (aux x ans) 
    (if (null? x)
        ans
        (aux (cdr x) (cons (car x) ans))))
  (aux x nil)
})
\endlisp

{\bf \ANSWER{The above is not copy.  Actually, it's reverse!  Now
let's define copy using reverse:}} \\
\beginlisp
\ANSWER{
(define (copy-iter x) (reverse (reverse x)))
}
\endlisp

\vskip .1in

{\Large\bf 6. 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)
\ANSWER{
  (define (aux x ans)
    (if (null? x)
        ans
        (aux (cdr x) (cons (car x) ans))))
  (aux (reverse a) b)
}
)
\endlisp

{\Large\bf 7. One More Function for Lists}

Write the function {\tt lrange} that takes a list {\tt x} and two
integers {\tt a} and {\tt b}, and returns a list of the {\tt a}'th though
the {\tt b}'th elements of {\tt x}.  e.g.  {\small \tt (lrange (list
0 1 2 3 4) 1 3) $\Rightarrow$ (1 2 3)}.  \\
{\em I know we're not going
to get to this in class...  Try it, and the answer will be on the web.}

\beginlisp
(define (lrange x a b)
\ANSWER{
   (define (n-cdrs x n)
      (if (= n 0)
          x
          (n-cdrs (cdr x) (- n 1))))
   (define (partial-copy x n)
      (if (= n 0)
          nil
          (cons (car x) (partial-copy (cdr x) (- n 1)))))
   (partial-copy (n-cdrs x a) (+ (- b a) 1))
})
\endlisp

\end{document}



