CSC151.02 2015S, Review Session Week 10: Pairs and Pair Structures
==================================================================

_Overview_

* We do a quick overview of the quiz.
* You ask questions about the exam, I attempt to answer.
* You ask questions about quiz and recent concepts, I attempt to answer.
* We talk about the forthcoming quiz.

About the Quiz
--------------

Main topics:

* Pairs and pair structures.
* Trees.
* Deep recursion (recursion over trees): Key idea: Recurr over both
  the car and the cdr.
* Vectors (maybe)

Likely quiz questions:

* Interpret _this code_.
* Finish writing _this code_ that is supposed to accomplish _this task_.
* Correct _this code_.
* Draw _this expression_.

Your Questions: Exam
--------------------

Your Questions: Quiz (Pairs, Trees, Etc.)
-----------------------------------------

_Can we go over deep recursion a bit?_

        (define ccc
          (lambda (t)
            (if (pair? t)
                (+ 1
                   (ccc (car t))
                   (ccc (cdr t)))
                0)))

        > (ccc (cons (cons (cons 6 1)
                           7)
                (cons (cons 1 9)
                      6)))
        5

> Counts the number of pairs in a pair structure

_Should we solve this by drawing out the tree or ...?_

> For some, drawing out the tree is good.

> For others, working through the steps is good
        
        > (ccc (cons (cons (cons 6 1) 7) (cons (cons 1 9) 6)))
        > (+ 1 (ccc (cons (cons 6 1) 7)) (ccc (cons (cons 1 9) 6)))
        > (+ 1 (+ 1 (ccc (cons 6 1)) (ccc 7)) (ccc (cons (cons 1 9) 6)))
        ...

> You might also try a smaller example.

> On the exam, you may have to generate your own examples (problem 6?)

> On the exam, you can also try running it.

_What's the difference between a pair and a list?_

> Nonempty lists are composed of pairs.  (That's why pairs are in Scheme.)

> But we can build non-lists with pairs.   For a pair structure to be a
  list, all the cdrs of the top-level elements have to be lists (either
  a pair that is a list or null)

> We don't care whether the pairs within a list are themselves lists,
  only the "spine".

_Can you draw `(cons null (cons null null))`_

> Yes, but only on the whiteboard.

_When do you draw pair structures going across and when going downward?_

> If you're thinking about them as lists, draw across. 

> If you're thinking about them as trees, draw down.

> But either is correct.

_How do we recursively build a tree?_

> It depends a bit on the tree you want to build.

        (define build-tree
          (lambda (info)
            (if (simple? info)
                simple-tree
                (cons (build-tree (simplify1 info))
                      (build-tree (simplify2 info))))))

> We have to write simple?, simple-tree, simplify1, and simplify2.

> Color tree for an image

        ; Build a tree that describes the vertical segments of a
        ; tree
        (define build-color-tree
          (lambda (image left top width height)
            (if (most-of-the-pixels-are-the-same image left top width height)
                (color-of-the-pixels image left top width height)
                (cons (build-color-tree image left top (/ width 2) heihgt)
                      (build-color-tree image (+ left  (/ width 2))
                                              top (/ width 2) height)))))

_Are vectors on the quiz?_

> Potentially.

_Can we do the `vector-rotate!` problem from the extras?_

> Goal: Procedure that shifts everything left 1, moves leftmost value
  to the end.

> Strategy:

        ; 1. Remember the leftmost value for using at the end
        ; 2. Recurse through the positions, moving things left
        ; 3. Put that stored value at the end.

        (define vector-rotate!
          (lambda (vec)
            (let ([save (vector-ref vec 0)]
                  [last-index (- (vector-length vec) 1)])
              (let kernel ([i 0])
                (when (< i last-index)
                   (vector-set! vec i (vector-ref vec (+ i 1)))
                   (kernel (+ i 1))))
              (vector-set! vec last-index save))))

Sample Quiz Questions, Revisited
--------------------------------

_Draw `'(1 2 3 . 4)`_

_Draw `'(1 (2 . 3) 4)`_

_Draw `'(1 (2 . 3) . 4)`_

_Draw `'(1 ((2 . 3) . 4))`_

_Fill in the blanks in the following to get a working version of 
 `vector-rotate!`_

        (define vector-rotate!
          (lambda (vec)
            (let ([save _____________________]
                  [last-index (- (vector-length vec) 1)])
              (let kernel ([i 0])
                (when (< i last-index)
                   (vector-set! vec i _______________________)
                   (kernel (+ i 1))))
              (vector-set! vec last-index save))))