recitation 7: some practice problems

--------------------------------------------

* write down the rules for evaluating expressions in scheme

1. if self-evaluating, ?
2. if name, ?
3. if _____, ?
4. if _____, ?

--------------------------------------------

* write down the rules for application of a procedure

1. if primitive procedure, ?
2. if compound procedure, ?

* what's the difference between a primitive procedure & a compound
  procedure?

--------------------------------------------

* fill in the blanks:

To find the value of a COMBINATION:
  a. first, find the value of ____________
  b. then, APPLY the value of the ___________ to the _______________

--------------------------------------------

* list the special forms we've learned so far.  For each special form,
  write down the syntax (and/or an example of its use), the special
  rules for evaluation, and describe why it must be special form (why
  can't we use the regular rules for application?)

--------------------------------------------

(define (map proc lst)
   (if (null? lst) nil
       (cons (proc (car lst))
             (map proc (cdr lst)))))

map:  (a->b,list(a)) -> list(b)
(map square (list 1 2 3 4)) -> (1 4 9 16)

(define (filter pred lst)
    (cond ((null? lst) nil)
          ((pred (car lst))
           (cons (car lst) (filter pred (cdr lst))))
          (else (filter pred (cdr lst)))))

filter:  (a->boolean,list(a)) -> list(a)
(filter even? (list 1 2 3 4 5 6)) -> (2 4 6)

(define (fold-right op init lst)
   (if (null? lst)
       init
       (op (car lst)
           (fold-right op init (cdr lst)))))

fold-right:  ((a,b->b),b,list(a)) -> b
(fold-right + 0 (list 1 2 3)) -> 6

--------------------------------------------

(intersection (list 1 2 3 4) (list 3 5 1 6)) -> (1 3)

* type:

* implement intersection using map, filter, and/or fold-right

--------------------------------------------

(apply-all (list abs square cube inc) -4) -> (4 16 -64 -3)

* type:

* implement apply-all recursively

* implement apply-all using map, filter and/or fold-right

--------------------------------------------

(append (list 1 2 3) (list 4 5 6)) -> (1 2 3 4 5 6)

* type:

* implement append recursively

* implement append using map, filter and/or fold-right

--------------------------------------------

(reverse (list 1 2 3 4)) -> (4 3 2 1)

* type:

* implement reverse recursively using append

* implement reverse iteratively

--------------------------------------------

(define my-tree (list 1 (list 2 3 (list 4 5)) (list (list 6))))

* draw the box & pointer diagram for my-tree

* draw a "stylized tree diagram" for my-tree

* how are they related?

--------------------------------------------

(define (leaf? tree) (not (pair? tree)))

(define (tree-manip leaf-op init merge tree)
  (if (null? tree)
      init
      (if (leaf? tree)
	  (leaf-op tree)
	  (merge (tree-manip leaf-op init merge (car tree))
		 (tree-manip leaf-op init merge (cdr tree))))))

* what's the type of tree-manip?

--------------------------------------------

* use tree manip to square every element of a tree

* use tree-manip to compute the product of all the even-valued 
  leaves of the tree (assume a tree of integers)

* use tree-manip flatten a tree

* use tree-manip to "deep-reverse" a tree (reverse the order of
  children at each node)

* use tree-manip to sum up the values of the leaves of the tree
  (assume a tree of numbers)

* use tree-manip to create a new tree, which keeps the odd-valued
  leaves of the original tree within the same tree structure, but
  removes even valued leaves.  (assume a tree of integers)

* for each of the above exercises, write down the types of arguments &
  return value for the calls to tree-manip.  Make sure it "type checks".

--------------------------------------------

For each expression below, indicate the value & type.  If it's value 
is undefined, or it produces an error or infinite loop, indicate so.

(let ((* /)
      (/ *))
  (/ 12 (* 6 3)))
      
* value:
* type:

((lambda (x + y) (+ x y))
 3 * 4)

* value:
* type:

(define (inc x) (+ 1 x))

* value:
* type:

inc

* value:
* type:

(define (foo f)
  (lambda (x) (f (f (f x)))))

* value:
* type:

foo

* value:
* type:

((foo inc) 0)

* value:
* type:

((foo (foo inc)) 0)

* value:
* type:

(((foo foo) inc) 0)

* value:
* type:

--------------------------------------------

fibonacci:
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2), for n >= 2

* write a recursive procedure to implement fibonacci

* write an iterative procedure to implement fibonacci 
  Note: this version should do something smarter...  and
        not duplicate work

* use the substitution model (in gory detail, take small steps) to
  evaluate a small example of each of your procedures.  Come up with
  the formula for the number of steps ("height") and memory
  requirements ("width") as a function of the input.  Generalize this
  to an order of growth for each.  
  Note: the math here is actually a topic for 6.042, but we just want
  you to get a flavor for it...

--------------------------------------------

* what's the difference between applicative order & normal order evaluation?

* which does scheme use?

--------------------------------------------
write an expression for ?, so that the expressions below evaluate as indicated.

(define foo ?)
(foo -5 3) => 5
(foo 2 7) => 2
(foo 7 4) => -4
(foo 10 -4) => 4

(define bar ?)
(bar 4) => 6
(bar 5) => 7
(bar 6) => error, divide by zero
(bar 7) => procedure

--------------------------------------------

(define mystery 
  (lambda (a b)
    (mystery-meat 0 a b)))

(define mystery-meat 
  (lambda (c a b)
    (if (> a b)
	c
	(mystery-meat (+ c a) (+ a 1) b))))

* write an equivalent procedure that generates a recursive process:

(define clarity (lambda (a b) 
   <your-code-here> )

--------------------------------------------

* Design a data structure to store information about students in
  6.001.  For each student, we want to store: their first name (string),
  intended major (number), and their height (number).  Explain in words
  the contract between your constructor & accessor functions.  Sketch
  out the box & pointer diagram for a simple example.

* Design an alternate data structure to store the same information.
  Try to come up with something really different, and explain in what 
  cases your first design might be more useful, and in what cases your 
  second design might be more useful.

Write the following functions.  Use your accessors & constructors.
Don't violate the abstraction barrier.  (What's an abstraction
barrier?)  Use map, filter & fold-right, when appropriate.  Also,
write helper functions to make your code concise and easy to read.

* Write a function that takes in a list of student names, and a list of
  their corresponding heights and returns a student list, with
  everyone's major set as undeclared.  Modify your data structure design
  as necessary so that you can store and detect undeclared majors.  In
  your documentation spell out any assumptions you have made about the
  input.

* Write a function that takes in a student-list, a student's first
  name, and a new major, and returns a new student list with the major 
  declared appropriately.

* Write a function that takes in a student-list and returns a student
  list where the undeclared majors have been set by the length of each
  students first name.  ("Ben" will be course 3, and "Alyssa" will be 
  course 6).

* Write a function that takes in a student-list and returns the
  average height of students in the class with a particular major.  Make
  sure you handle undeclared majors and majors with no students.

* Write a function that takes in a student-list and returns a list
  of the student names sorted by student height.

--------------------------------------------