\documentstyle[6.001-ps]{article}
\def\getvars{
  \newcount\x \newcount\y \newcount\a \newcount\b}
\def\listlab  #1 #2 #3 #4{
  \x=#1 \y=#2 \a=#4
  \multiply\x by6 \multiply\y by4
  \multiply\a by6 \advance\a by-2
  \put(\x,\y){\makebox(2,2){#3}}
  \advance\x by2 \advance\y by1
  \put(\x,\y){\vector(1,0){\a}}}
\def\numcell  #1 #2 #3 #4{
  \x=#1 \y=#2
  \multiply\x by6 \multiply\y by4
  \put(\x,\y){\framebox(#4,2){#3}}}
\def\listcell #1 #2 #3 #4{
  \x=#1 \y=#2					% declare positions
  \a=#3 \b=#4					% declare vec lengths
  \multiply\x by6 \multiply\y by4		% scale everything
  \multiply\a by4 \advance\a by-1
  \multiply\b by6 \advance\b by-3
  \put(\x,\y){\framebox(2,2){}}			% place box 1
  \advance\x by2 \put(\x,\y){\framebox(2,2){}}	% place box 2
  \advance\x by-1 \advance\y by1		% place vector 1
  \put(\x,\y){\vector(0,-1){\a}}
  \advance\x by2
  \ifnum\b=-3
    \advance\x by-1 \advance\y by-1
    \put(\x,\y){\line(1,1){2}}
  \else
    \put(\x,\y){\vector(1,0){\b}}
  \fi}
\def\conscell #1 #2 #3 #4{
  \x=#1 \y=#2
  \multiply\x by6 \multiply\y by4 \advance\x by-1
  \put(\x,\y){\framebox(2,2){}}
  \advance\x by2
  \put(\x,\y){\framebox(2,2){}}
  \advance\x by-5 \advance\y by-4
  \put(\x,\y){\framebox(4,2){#3}}
  \advance\x by6
  \put(\x,\y){\framebox(4,2){#4}}
  \advance\y by5
  \put(\x,\y){\vector(2,-3){2}}
  \advance\x by-2
  \put(\x,\y){\vector(-2,-3){2}}
}  
\begin{document}
\setlength{\unitlength}{0.1 in}
\getvars
\header{3}{March 3, 1989}
\part{1: Compound Data}
\exercise{3.1}
\bv
(define (cdr z)
  (z (lambda (p q) q)))
\end{verbatim}
\exercise{3.2}
\bv
(define (cons a b)
  (* (pow2 a) (pow3 b)))

(define (cdr c)
  (if (odd? c)
      (log3 c)
      (cdr (/ c 2))))

(define (car c)
  (log2 (/ c (pow3 (cdr c)))))

(define (pow2 x)
  (if (= x 0)
      1
      (* 2 (pow2 (-1+ x)))))

(define (pow3 x)
  (if (= x 0)
      1
      (* 3 (pow3 (-1+ x)))))

(define (log2 x)
  (if (= x 1)
      0
      (1+ (log2 (/ x 2)))))

(define (log3 x)
  (if (= x 1)
      0
      (1+ (log3 (/ x 3)))))

(define foo (cons 12 63))
;Value: FOO

foo
;Value: 4688122975972710379052849956564992

(car foo)
;Value: 12

(cdr foo)
;Value: 63
\end{verbatim}
\part{2: Lists}
\exercise{3.3}
\begin{picture}(34,18)
\listlab  0 4 L 1
\listcell 1 4 1 1
\listcell 2 4 1 2
\listcell 4 4 1 0
\numcell  1 3 1 2
\listcell 2 3 1 1
\listcell 3 3 1 0
\listcell 4 3 1 2
\listcell 6 3 1 0
\numcell  2 2 2 2
\numcell  3 2 3 2
\listcell 4 2 1 1
\listcell 5 2 1 0
\numcell  6 2 7 2
\numcell  4 1 4 2
\listcell 5 1 1 1
\listcell 6 1 1 0
\numcell  5 0 5 2
\numcell  6 0 6 2
\end{picture}
\exercise{3.4}
\bv
(cons 1
      (cons (cons 2
                  (cons 3 nil))
            (cons (cons (cons 4
                              (cons (cons 5
                                          (cons 6 nil))
                                    nil))
                        (cons 7 nil))

                  nil)))
\end{verbatim}
\exercise{3.5}
\bv
1: (car L)
2: (car (car (cdr L)))
3: (car (cdr (car (cdr L))))
4: (car (car (car (cdr (cdr L)))))
5: (car (car (cdr (car (car (cdr (cdr L)))))))
6: (car (cdr (car (cdr (car (car (cdr (cdr L))))))))
7: (car (cdr (car (cdr (cdr L)))))
\end{verbatim}
\exercise{3.6}
\bv
(define (list-tail lst k)
  (if (= k 0)
      lst
      (if (null? lst)
          'error
          (list-tail (cdr lst) (-1+ k)))))

(define (list-ref lst k)
  (let ((part-list (list-tail lst k)))
    (cond ((equal? part-list 'error) 'error)
          ((null? part-list) 'error)
          (else (car (list-tail lst k))))))
\end{verbatim}
\part{3: Navigation}
\problem{3.1}
a)

\begin{picture}(56,10)
\listlab  0 2 c 1
\listcell 1 2 1 2
\listcell 3 2 1 2
\listcell 5 2 1 2
\listcell 7 2 1 0
\conscell 1 1 10 {90}
\conscell 3 1 20 {45}
\conscell 5 1 15 {-90}
\conscell 7 1 30 {180}
\end{picture}

b)
\bv
(define (segment-turn seg)
  (car (cdr seg)))

(define (segment-distance seg)
  (car seg))
\end{verbatim}

c)

\begin{picture}(52,10)
\listlab  0 2 c 1
\listcell 1 2 1 2
\listcell 3 2 1 2
\listcell 5 2 1 2
\listcell 7 2 1 0
\listcell 1 1 1 1
\listcell 2 1 1 0
\listcell 3 1 1 1
\listcell 4 1 1 0
\listcell 5 1 1 1
\listcell 6 1 1 0
\listcell 7 1 1 1
\listcell 8 1 1 0
\numcell  1 0 10 2
\numcell  2 0 90 2
\numcell  3 0 20 2
\numcell  4 0 45 2
\numcell  5 0 15 2
\numcell  6 0 -90 3
\numcell  7 0 30 2
\numcell  8 0 180 3
\end{picture}
\problem{3.2}
\bv
(define (make-vector dx dy)
  (cons dx dy))

(define (xcor vec)
  (car vec))

(define (ycor vec)
  (cdr vec))
\end{verbatim}
\problem{3.3}
\bv
(define (endpoint course position direction-vector)
  (if (null? course)
      position
      (let ((first-segment (car course)))
        (endpoint (cdr course)
                  (+vect position (scale (segment-distance first-segment) 
                                         direction-vector))
                  (rotate direction-vector (segment-turn first-segment))))))
\end{verbatim}
\problem{3.4}
\bv
(define (total-turn course)
  (define (total-iter course total)
    (if (null? course)
        total
        (total-iter (cdr course) (+ total (segment-turn (car course))))))
  (total-iter course 0))
\end{verbatim}
\problem{3.5}
\begin{verbatim}
(define (total-turn course)
  (sum-list (mapcar segment-turn course)))

(define (sum-list lst)
  (define (sum-iter lst total)
    (if (null? lst)
        total
        (sum-iter (cdr lst) (+ total (car lst)))))
  (sum-iter lst 0))
\end{verbatim}
\problem{3.6}
a) The function will return the correct accumulated turns, but
in the reverse order.

b) 
\bv
(define (accumulated-turns course)
  (define (iter course total)
    (if (null? course)
        (cons total nil)
        (cons total (iter (cdr course)
                          (+ total (segment-turn (car course)))))))
  (iter (cdr course) (segment-turn (car course))))
\end{verbatim}
\problem{3.7}
\bv
(define (accumulated-turns course)
  (if (null? course)
      nil
      (cons (segment-turn (car course))
            (mapcar (lambda (turn) (+ turn (segment-turn (car course))))
                    (accumulated-turns (cdr course))))))
\end{verbatim}
\problem{3.8}
What's the problem?  I mean, you didn't ask anything!
\problem{3.9}
Before evaluating the time of \verb+distinct?+, I analyzed \verb+appears-in+.
It is clear that \verb+appears-in+ is O($n$), where $n$ is the length of the
list.  This O($n$) function is called $m$ times by the \verb+distinct?+, with
$m=1,2,3,\ldots,m$.  The total time is then of the order $\frac{m(m+1)}{2}$,
which is just O($n^{2}$).  Thus, \verb+distinct?+ takes O($n^{2}$) time, where
$n$ is the length of the original list.
\problem{3.10}
\bv
(define (parallel-segments? course)
  (distinct? (accumulated-turns course)))
\end{verbatim}
\problem{3.11}
\bv
(define (make-generalized-course course)
  (lambda (position-direction-pair)
    (make-position-direction-pair 
      (endpoint course
                (position position-direction-pair)
                (direction-vector position-direction-pair))
      (rotate (direction-vector position-direction-pair)
              (total-turn course)))))

(define (make-position-direction-pair pos dir)
  (cons pos dir))

(define (position pos-dir-pair)
  (car pos-dir-pair))

(define (direction-vector pos-dir-pair)
  (cdr pos-dir-pair))
\end{verbatim}
\problem{3.12}
Any non-linear course could not be represented by Ben's method.  One example
of this might be the boat making a wide turn around a buoy.
\problem{3.13}
You did it again.  Actually, you probably didn't do it, but whoever
wrote this problem set again neglected to actually ask anything.
\problem{3.14}
\bv
(define (append-generalized-course one two)
  (lambda (pos-dir-pair)
    (two (one pos-dir pair))))
\end{verbatim}
\end{document}
