COMP 210, Spring 2001
Homework 6 : Accumulators; higher-order functions
Due Oct.10 (wed), at start of class.

Starting with this homework onward, you are NOT required to show the template for your programs (woo-hoo!). Your functions should still follow the template, though. And of course, each function should still have a contract and purpose, and reasonable test cases.

Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

  1. (1pt) What is the value of the final + expression below? 

    (define glurg 30)

;; galumph: number --> number
;; purpose: ??
;;
(define (galumph frufru)
  (+ frufru glurg)) 

(+ (local [;; galumph: natnum --> num
           ;; purpose: ??
           ;;
           (define (galumph n)
              (cond [(zero? n)      glurg]
                    [(positive? n)  (galumph (sub1 n))]))
           (define glurg 20)]

      (galumph 50))     ; The body of the local.
    (galumph 50))       ; Not inside the local.
    You can verify your answer with drscheme and the stepper, of course. (Think to yourself: What exactly is the scope of the glurg inside the local?) Acknowledgement: these functions are all eminently unuseful.

  2. (4pts) Write two versions of the function length, (taking a list (of any values) and returning a number) one following exactly from the template, the other using an accumulator (helper).

    For each of them, give a limited hand-evaluation of finding the length of (list true "tutu" 'z 3). By "limited hand-evaluation", I mean show what things look like just before and after evaluating a (perhaps recursive) call to length, as in the the first, usual example. (You do not need to show how the function-call expands into the body (w/ parameters replaced by arguments).) Be sure to assert a relation between the expressions -- namely, that they (evaluate to) equal values.

  3. (5pts) Recall the definitions of files and directories as used in lab. A pathname is a list of symbols: the names of directories leading to (and including) a file-or-directory. E.g., this file is (list 'home 'comp210 'Homeworks 'hw06.shtml). Write a function find, which takes in root directory and the name of a file, and returns a list of all pathnames ending in that file name. (You may ignore directories with that name, if you want.)
    Hint: This follows directly from templates, and is arguably easier w/o an accumulator. But if you want to use an accumulator, that's okay too.
    You may use the built-in functions reverse, append.

    If you prefer, you may use the alternate data definition for files/directories alluded to in class; if you use this alternate version, clearly state so on your homework (since it impacts what your functions should look like).

    An aside, for fun: this program serves the same purpose as the unix command find dir -name fname (for example, try find /home/comp210/Web/01fall -name index.html). If you want to modify your scheme program to actually access the disk, go to help-desk and look up directory-list and directory-exists?.

  4. (3pts) Write the function unzip which takes in a list, and returns (a list of) two lists: the original list split into two alternating halves. 
    (unzip (list 1 2 3 4 5)) = (list (list 5 3 1) (list 4 2))
    Use an accumulator. (Hint: you can have more than one accumulator parameter.)
    Don't need to answer, since it wasn't yet mentioned in lecture: What is the invariant? But do have a Purpose which explains what your accumulator function returns, in terms of its input.

    (The order of the two lists, or of the elements in each of them, isn't important, but no two adjacent elements of the input should be in the same result list.)

  5. (4pts) Write the function iSort which takes a list of numbers, and returns the list in ascending order.
    Hint Requirement: Follow the template.
    If you need a helper-function, make it local to iSort. (That helper will also follow directly from the template.) No, you can't use the built-in quicksort.

    A counting question; you need only write down the answers to the starred questions:
    If your helper function is given a a list of 3 items, what is the most number of times it calls < (or similar comparison function)? For a list of 4 items? For a list of k items(*)?
    If iSort is given a list of 3 items, think about how many times your helper is called on lists of various sizes; similarly, if it is given a list of 4 items. n items? Finally: if iSort is given a list of n items, what is the most number of times < is called (*)?
    (Hint: From math class, for any natNum z, 1+2+3+...+(z-1)+z = z(z+1)/2.) A visual explanation: You can draw towers of height 1, 2, ..., z and note that you nearly have a triangle of height and base z; more exactly, two such arrangements can be oriented into exactly a z by z+1 rectangle.)

    Now, generalize your function to not just sort ascending, and not just numbers: Have it accept a comparison function. For instance, passing a list of strings and string>? yields a list in reverse alphabetical order.

  6. (3pts) Write map2, which is like map except that it takes in binary functions: E.g., (map2 + (list 3 5 7) (list 1 5 2)) = (list 4 10 9). What is map2's contract? (Anything important to emphasize, to people calling the function?)
    (Do not use the built-in map for this.)