I. flat recursion over lists (Little Schemer ch. 2-4, EOPL 1.2.1)
 A. inductive definition of lists
------------------------------------------
      INDUCTIVE DEFINITION OF LISTS

def: a (list-of T) is
   - either 
   - or 




Grammar:


------------------------------------------
 B. tips (summary)
  1. write examples
------------------------------------------
    TIPS FOR REDUCING HOMEWORK TIME
         FOR RECURSIVE PROGRAMS

1. Write out your own examples if needed
	a. base case(s)
	b. related simpler example





------------------------------------------
  2. write down the type
------------------------------------------
             MORE TIPS

2. What are the types?  Write it down

(deftype sum-squares 



------------------------------------------
  3. follow the grammar
------------------------------------------
              MORE TIPS

3. Use an outline that matches the grammar
   for the input data type.

   "Follow the grammar!"

<list-of-T>::= () | (<T> . <list-of-T>)











------------------------------------------
  4. fill in by generalizing examples
------------------------------------------
             MORE TIPS

4. Fill in the outline
   by generalizing the examples


a. What's returned in the base case(s)?

   (sum-squares '()) ==> 0


b. How do we get the answer
   from
      - recursive call's answer, and
      - other information?

   (sum-squares '(3 4 2)) ==> 29
                 _______      __
                  lst    (sum-squares lst)

   (sum-squares '(4 2)) ==> 20
                 _____      __
             (cdr lst)  (sum-squares
                             (cdr lst))
------------------------------------------
  5. when debugging, work bottom up
------------------------------------------
            MORE TIPS
5. When debugging, work bottom up
   from subexpressions

    (define lst '(3 4 2))
    (cdr lst)
    (car lst)
    (* (car lst) (car lst))
    ...

   If you need to use a recursive call
   when debugging, use the value instead

    (+ (car lst) (car lst) 20)
------------------------------------------
 C. deriving recursive programs from examples
  1. example
------------------------------------------
     DERIVATION FROM RELATED EXAMPLES


(zip '(3 4 2) '(5 9 7))
   ==> ((3 5) (4 9) (2 7))
(zip '(4 2) '(9 7))
   ==> ((4 9) (2 7))


(zip '() '(3 1 4 1 5 9))
   ==> ()
(zip '(2 7 3 4) '())
   ==> ()


------------------------------------------
        What's a related simpler example for the second example?
	What's the type?
	What are the cases?  What's the outline?
	What is the answer for the base cases?
	How to decompose?  Where is the recursion?
	How do we get from the answer for the recursion to what we want?
  2. trace
------------------------------------------
	   HOW IT WORKS

(zip '(3 4 2) '(5 9 7))
  = ((lambda (fsts snds) (cond ...))
     '(3 4 2) '(5 9 7))
  = (cond ((null? '(3 4 2)) '())
          ((null? '(5 9 7)) '())
           (else (cons (list (car '(3 4 2)) (car '(5 9 7)))
		       (zip (cdr '(3 4 2)) (cdr '(5 9 7))))))
  = (cons (list (car '(3 4 2)) (car '(5 9 7)))
	  (zip (cdr '(3 4 2)) (cdr '(5 9 7))))
  = (cons (list 3 5)
	  (zip '(4 2) '(9 7)))
  = (cons (list 3 5)
	  (cons (list 4 9)
                (zip '(2) '(7))))
  = (cons (list 3 5)
	  (cons (list 4 9)
                (cons (list 2 7)
                      (zip '() '()))))
  = (cons (list 3 5)
	  (cons (list 4 9)
                (cons (list 2 7)
                      '())))
  = (cons (list 3 5)
	  (cons (list 4 9)
                '((2 7))))
  = (cons (list 3 5)
	  '((4 9) (2 7)))
  = '((3 5) (4 9) (2 7))

------------------------------------------
  3. try it
------------------------------------------
           FOR YOU TO DO

(xerox '(3 9 2)) ==> (3 3 9 9 2 2)
(xerox   '(9 2)) ==> (9 9 2 2)
(xerox      '()) ==> ()









------------------------------------------
	What's a related example?
	What's the type?
	How do you make (3 9 9 2 2) from (3 9 2) and (9 9 2 2)?
	How do you make (3 3 9 9 2 2) from (3 9 2) and (3 9 9 2 2)?
 D. more complex cases
  1. give yourself examples to cover all cases
------------------------------------------
 GIVE YOURSELF EXAMPLES TO COVER ALL CASES

(insert-before 'x 'q '()) ==> ()
(insert-before 'x 'q '(x y z x))
                ==> (q x y z x)
(insert-before 'x 'q '(a x y z))
                ==> (a q x y z)




Type:
(deftype insert-before
  (-> (symbol symbol (list-of symbol))
             (list-of symbol)))

Grammar for input data:
<list-of-symbol> ::= ()
              | (<symbol> . <list-of-symbol>)

Outline that matches grammar:
(define insert-before
  (lambda (where what los)








------------------------------------------
	What examples are we missing?
	Which argument has an inductively specified type?
  2. example for you
------------------------------------------
	FOR YOU TO DO (IN PAIRS)

(remove 'x 'q '()) ==> ()
(remove 'x 'q '(x y z x))
         ==> (q x y z q x)
(remove 'x 'q '(a x y z x))
        ==> '(a q x y z q x)

Any other examples you want?



What's the type?


What's the structure of the code?

Write it!







------------------------------------------
	How does this differ from insert-before?