You should read through the end of Section 2.2 in order to be fully prepared for this lab.

Part A: Exercises

Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.

For the drawing component of these exercises, you may use any drawing program you like, as long as the final drawings are output in PostScript format (.ps file extensions). We recommend the xfig or the dia programs, both of which are installed on the CS cluster computers. Submit the drawings as separate files to CS1man.

1. [25] Draw box and pointer diagrams for the following Scheme expressions. Assume that nil has been defined to be the empty list, i.e. (define nil (list)).

   1. (cons 1 2)

   2. (list 1 2)

   3. (cons 1 (cons 2 nil))

   4. (list 1 (list 2 (list)))

      You can use the word nil for the empty list (the thing returned by (list)), or you can represent it by a single box with a line drawn diagonally through it.

   5. (cons 1 (list 2 3))

   6. (list 1 (cons 2 3))

   7. (list (list 1 2 3) (list 4 5 6) 7 (list 8 9 10) 11 12)

2. [25] Give a Scheme expression which will build each of the structures shown in the box and pointer diagrams:

   1. 

      ---

   2. 

      ---

   3. 

      ---

   4. 

      ---

   5. 

      ---

   6. 

      ---

3. [15] What's wrong with these expressions? Describe why each of them will result in an error.

   1. (cdr (list))

   2. (cdr (cdr (cdr (list 1 2))))

   3. (car (car (list 1 2)))

   4. (define (buggy-sum lst) 
        (+ (car lst) (buggy-sum (cdr lst))))
      (buggy-sum (list 1 2 3))
            

   5. (+ 1 2 3 (list 1 2 3))

   After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs".

Part B: Working with lists

1. [15] Explain the function of the following procedure which operates on lists:

      (define (fh x)
        (define (fh-aux l aux)
           (cond ((null? l) (list))
                 ((null? (cdr l)) (list))
                 (else (cons (car aux) (fh-aux (cdr (cdr l)) (cdr aux))))))
        (fh-aux x x))
   

2. Write the following procedures which involve lists:

   1. [15] A procedure that counts the negative elements in a list and returns the count.

   2. [10] A procedure that takes in an integer, n, and creates a list containing the first n powers of 2 starting with 2⁰=1.

   3. [25] A procedure that takes in a list of numbers, and returns a list containing the prefix sum of the original list. e.g.
      (prefix-sum (list 1 3 5 2)) ==> (1 4 9 11). The prefix sum is the sum of all of the elements in the list up to that point, so for the list (1 3 5 2) the prefix sum is (1, 1+3, 1+3+5, 1+3+5+2) or (1 4 9 11).

Part C: Book Exercises

Please do the following exercises from the textbook. We've added some clarifications which should make the problems easier to manage.

1. [30] Exercise 2.20 (dotted tail notation). The phrase "even-odd parity" just means evenness or oddness, so that if the first number in the list is even, you should return a list of all the even numbers in the list, and if the first number is odd, you should return a list of all the odd numbers in the list. Note that the function you define will always have to take at least one argument.

   You can use the remainder procedure to determine if a number is even or odd i.e. (remainder x 2) returns 0 if x is even or 1 if x is odd.

2. [30] Exercise 2.21 (using map). Read the section just preceding the exercise to learn how the map higher-order procedure works. map is actually one of the most frequently-used higher-order procedures. Use (list) where the book says to use nil (coding standards have changed since the book was written).

3. [30] Exercise 2.32 (generate all subsets of a set, fill in code and explain). Again, use (list) where the book uses nil.

   Note that the append procedure concatenates two lists, returning a new list containing all the elements of both old lists in order. So, for instance, (append (list 1 2 3 4) (list 5 6 7 8)) gives the result (1 2 3 4 5 6 7 8) without altering either of the first two lists.

   Hint: The code you need to add is very short; it will easily fit on the same line as the map.

4. [30] Exercise 2.34 (evaluate polynomials).

   Note that the accumulate procedure is defined as:

   (define (accumulate op initial sequence)
     (if (null? sequence)
         initial
         (op (car sequence)
             (accumulate op initial (cdr sequence)))))
   

   and is discussed at length in section 2.2.3 of SICP.

   To solve this problem, it may be helpful to take an example (e.g. (horner-eval 2 (list 1 3 0 5 0 1)), figure out what computation you want to be performed, and then write the code so that it performs it. Note that the coefficients in the list are in reverse order, so the first 1 is the x^0 coefficient and the last 1 is the x^5 coefficient. Again, the amount of code you have to add here is extremely small. Hint: Think carefully about what the arguments of the lambda expression refer to.

5. [45] Exercise 2.37 (matrix calculations; dot product, transpose). Note that you'll need to read exercise Exercise 2.36 to familiarize yourself with accumulate-n. A working definition of accumulate-n is:

   (define (accumulate-n op init seqs)
     (if (null? (car seqs))  ; sequences are empty
         (list)  ; we prefer this to nil, since nil isn't predefined in DrScheme
         (cons (accumulate   op init (map car seqs))
               (accumulate-n op init (map cdr seqs)))))
   

   None of the code fragments you need to fill in in any of the functions in this exercise are more than a line long. Feel free to use the earlier functions in the definitions of the later functions.

Part D: Good Code, Bad Code

There is no part D in this week's lab (and there was much rejoicing).