Homework Two
Data Definitions

1. (2pts) Recursive functions can produce surprising intermediate results during their evaluation. Consider the following three functions

   ;; fact: num -> num
   ;; Return n!, which stands for n*(n-1)*(n-2)*...*3*2*1
   ;;
   (define fact
     (lambda (n)
       (if (zero? n)
           1
           (* n (fact (- n 1))))))
   
   ;; multfib: num -> num
   ;; A multiplicative version of the fibonacci sequence.
   ;;
   (define multfib
     (lambda (n)
       (if (< n 3)
           n
           (* (multfib (- n 1))
              (multfib (- n 2))))))
   
   ;; threes: num -> num
   ;; Returns 1???
   ;;
   (define threes
     (lambda (n)
       (if (< n 2)
           1
           (threes (if (even? n)
                       (/ n 2)
                       (+ 1 (* n 3)))))))
   

   (These functions also appear in the file ~comp210/Assignments/hw02-problem1.ss.)

   Evaluate each of these functions for values of n between 0 and 6 inclusive. For each value of n, use Donkey to determine the total number of calls made to each function. (The initial call counts, so the answer for n = 0 is 1 in each case.) The point of this exercise is to see how scheme evaluates recursive functions; think about what is happening at each step!

   For a small amount of extra credit, estimate the number of recursive calls made by each function in terms of n. (Warning: I don't know the answer for threes.)

2. (5pts) Designing list-handling programs.
   Recall the design recipe for writing functions.
   1. Write any pertinent data definitions (e.g., a List-Of-Numbers).
   2. Write sample data meeting the definition.
   3. Derive a template for a generic function (e.g., handle-lon).
   4. Give your function's contract (the types of inputs and outputs), and description (as needed).
   5. Give sample test cases (presumably based on your sample data above).
   6. Fill in the template to get a working program.
   7. Test your program on the cases already developed.
   Do all of these steps inside DrScheme comments ('cept, 'course, the actual code: #6 and half of #7). Use this design recipe for the following programs. (If one part is the same as a previous answer, just refer to your previous answer.)
   1. A function total which returns the sum of the numbers in the list.
   2. A function all-positive? which returns true iff the list list contains only positive numbers.
   3. A function count-positives which returns the number of positive numbers in the list.
   4. A function positive-part which returns a list of numbers: all the positive numbers in the input list.

3. (3pts) The data definition for an Association is simple: An Association is (cons symbol (cons value empty)). (What are some examples?)

   Define an Association List (i.e., a list of Associations). Using the design recipe, write the function lookup, which takes a symbol and an Association List. It searches the association list until it finds an association whose key is the same as its first argument. If it finds such an association, it returns the value (second element) from the association. If not, it returns¹ #f.

   Hint: Your code will be easier to read and to write if you write the selectors association-key and association-datum (each of which are very simple: they take an association, and return the corresponding values inside. What do the contracts look like?)