\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 4 -- Solutions}
\author{David Ziegler}
\date{October 4, 2004}
\maketitle

\section{Quiz Stuff}
\begin{itemize}
\item Quiz, Thursday, 7:30 -- 9:30 pm
\item Room 32-123 (where we have lecture)
\item One page of notes
\item Review session tonight and tomorrow (LAs), 7 pm, 34-302
\item Office hours tomorrow (me), 3 -- 4 pm, here
\end{itemize}

\section{Project Comments}
\begin{itemize}
\item Please, please, please indent your code.
\item Please, please, please document your code.
\item Please, please, please test your code and include the results.
\end{itemize}

\section{Higher-Order Procedures}
Higher-order procedures are procedures that either accept procedures
as arguments or return procedures their value.

\begin{verbatim}
;; This procedure curries a function,
;; e.g. it takes a function of two
;; inputs and returns a function of
;; one input, that returns a function
;; of one input, that does the same
;; thing
;; ex: (+ 1 2) ==> 3
;; (((curry +) 1) 2) ==> 3
(define (curry f)
  (lambda (x)
    (lambda (y)
      (f x y))))
\end{verbatim}

\begin{verbatim}
;; This procedure composes two
;; functions f and g, each of one
;; argument, and returns a procedure
;; of one arg that does (f (g x))
(define (compose f g)
  (lambda (x)
    (f (g x))))
\end{verbatim}

\begin{verbatim}
;; This procedure applies f to each
;; element of the list, and returns a
;; new list made from those values
(define (map f lst)
  (if (null? lst)
      nil
      (cons (f (car lst))
            (map f (cdr lst)))))
\end{verbatim}

\begin{verbatim}
;; This procedure returns a new list
;; containing the elements in the
;; original for which pred is true
(define (filter pred lst)
  (cond ((null? lst) nil)
        ((pred (car lst)) (cons (car lst)
                                (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))
\end{verbatim}

\begin{verbatim}
;; This procedure combines all the
;; elements of lst using the binary
;; operation op, terminating with init
(define (fold-right op init lst)
  (if (null? lst)
      init
      (op (car lst)
          (fold-right op init (cdr lst)))))
\end{verbatim}

\clearpage
\onecolumn
\section{Queues}
A queue is a data structure that stores elements in order.  Elements
are \verb+enqueue+d onto the tail of the queue.  Elements are
\verb+dequeue+d from the head of the queue.  Thus, the first element
enqueued is also the first element dequeued (FIFO,
first-in-first-out).  The \verb+head+ operation is used to get the
element at the head of the queue.

\begin{verbatim}
(head (enqueue 5 (empty-queue)))
;Value: 5

(define q (enqueue 4 (enqueue 5 (enqueue 6 (empty-queue)))))

(head q)
;Value: 6

(head (dequeue q))
;Value: 5
\end{verbatim}

Decide on an implementation for queues, then draw a box-and-pointer
represention of the value of \verb+q+ as defined above.
\vspace{1in}

\begin{verbatim}
;; This procedure returns an empty queue
(define (empty-queue)
  nil)
\end{verbatim}
Time = $\Theta(1)$, space = $\Theta(1)$, $n =$

\begin{verbatim}
;; This procedure returns a new queue with the element added to the tail
(define (enqueue x q)
  (fold-right cons
              (list x)
              q))
\end{verbatim}
Can you do this with {\tt fold-right}? \\
Time = $\Theta(n)$, space = $\Theta(n)$, $n =$ length of \verb+q+.

\begin{verbatim}
;; This procedure returns a new queue with the head removed
(define (dequeue q)
  (cdr q)


\end{verbatim}
Time = $\Theta(1)$, space = $\Theta(1)$, $n =$

\begin{verbatim}
;; This procedure returns the value of the head of the queue
(define (head q)
  (car q))


\end{verbatim}
Time = $\Theta(1)$, space = $\Theta(1)$, $n =$

\section{Practice With HOPs}
Suppose \verb+lst+ is bound to the list (1 2 3 4 5 6 7). Using
\verb+map+, \verb+filter+, and/or \verb+fold-right+, write an
expression involving \verb+lst+ that returns:

\begin{itemize}
\item \verb+(1 4 9 16 25 36 49)+
\begin{verbatim}
(map square lst)
\end{verbatim}

\item \verb+(1 3 5 7)+
\begin{verbatim}
(filter odd? lst)
\end{verbatim}

\item \verb+((1 1) (2 2) (3 3) (4 4) (5 5) (6 6) (7 7))+
\begin{verbatim}
(map (lambda (x) (list x x)) lst)
\end{verbatim}

\item \verb+((2) ((4) ((6) #f)))+
\begin{verbatim}
(fold-right list nil lst)
\end{verbatim}

\item The maximum element of \verb+lst+: 7
\begin{verbatim}
(fold-right max (car lst) (cdr lst))
\end{verbatim}

\item The last pair of \verb+lst+: (7)

\emph{Impossible!}  \verb+map+, \verb+filter+, and \verb+fold-right+
only give you access to the \emph{members} of the list, not the
\emph{backbone} -- the cons cells which make up the list.

\end{itemize}

\end{document}