% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

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

{\Large\bf 1. Warm Up}

Write a function {\tt max-err} that takes a list of lists of numbers
and computes the {\bf sqrt} of the {\bf maximum} of the {\bf sum} of
the {\bf squares} of the sublists.  For example,

\beginlisp
(define data (list (list -1 2) (list 0 -4 3) (list 1 -1 -2)))    ==> ((-1 2) (0 -4 3) (1 -1 -2))
(max-err data) ==> 5    (because $\sqrt{0^2+(-4)^2+3^2}$ = 5 > $\sqrt{(-1)^2+2^2}$ and $\sqrt{1^2+(-1)^2+(-2)^2}$)
\endlisp

\beginlisp
(define (max-err data)
\ANSWER{
  (sqrt
   (accumulate max 0
     (map 
      (lambda (trial)
        (accumulate + 0
          (map square trial)))
      data)))
})
\endlisp


{\Large\bf 2. Uniqueness}

Say we have a list of numbers, and we want to get back a list where
each number in the original list appears exactly once.  For example, 

\beginlisp
(define x (list 1 2 2 3 1 5 4 3 4))   
(unique x)  ==> (1 2 3 5 4)
\endlisp

Let's write the function {\tt unique} to do this.  But first, write the
function {\tt remove} that removes all instances of an element from a
list.  (e.g. {\small \tt (remove 3 (list 1 3 2 3 4 3)) ==> (1 2 4)  }).

\beginlisp
(define (remove elt seq)
\ANSWER{  (filter (lambda (x) (not (= x elt))) seq)}
)
\endlisp

Now write {\tt unique}, using {\tt remove}.  When writing unique,
first think in English (or langunage of choice) about how you'd do
this, then translate to Scheme.

\beginlisp
(define (unique seq)
\ANSWER{
  (if (null? seq)
      nil
      (cons (car seq)
            (unique (remove (car seq) (cdr seq)))))
})
\endlisp
 
\vspace{0.1in}

{\Large\bf 3. All Pairs}

Write the function {\tt all-pairs} that takes a list and returns a
list of all pairs of the elements in the list.  For example,
\beginlisp
(all-pairs (list 1 2 3 4)) ==>  ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
\endlisp
Again, first think about how you'd do this, and then translate into
Scheme.  Maybe start with trying to just get the pairs {\tt ((1 2) (1 3) (1
4))}, and then build up from there.

\beginlisp
(define (all-pairs s)
\ANSWER{
  (if (null? s)
      nil
      (append (map (lambda (x) (list (car s) x)) (cdr s))
              (all-pairs (cdr s))))
})
\endlisp


\newpage

{\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 (hint: you can use {\tt reverse})...

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

{\Large\bf 5. Flatten}

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

\beginlisp
(define (flatten x)
\ANSWER{
  (cond ((null? x) nil)
        ((not (pair? x)) (list x))
        (else (append (flatten (car x))
                      (flatten (cdr x)))))
})
\endlisp

Now try writing flatten using map and accumulate.

\beginlisp
(define (flatten x)
\ANSWER{
  (if (not (pair? x))
      (list x)
      (accumulate append nil (map flatten x)))
})
\endlisp

{\Large\bf 6. Occurrences}

Write the function {\tt occurrences} that takes a number and a tree
and counts the number of times that number appears in the tree.  For
example, 
\beginlisp
(define tree (list 1 2 (list (list 3 1) (list 1 2) 1)))
(occurrences 1 tree)  ==>  4
\endlisp

\beginlisp
(define (occurrences elt tree)
\ANSWER{
  (cond ((null? tree) 0)
        ((not (pair? tree)) (if (= elt tree) 1 0))
        (else (+ (occurrences elt (car tree))
                 (occurrences elt (cdr tree)))))
})
\endlisp

Now write occurrences using map and accumulate..

\beginlisp
(define (occurrences elt tree)
\ANSWER{
  (define (helper subtree) 
    (cond ((pair? subtree) (occurrences elt subtree))
          ((= subtree elt) 1)
          (else 0)))
 (accumulate + 0 (map helper tree))
})
\endlisp

\end{document}
