Comp210: Principles of Computing and Programming
Fall 2004 -- Homework #8   

Read Sections 19-24 in the H.T.D.P. book in preparation for the exam.

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

Remember: Contract, purpose, header and test cases are always required!

For visitors, you need the following documentation:

  1. Contract for the base case and inductive case functions -- since the contracts are the same, you only need one contract.
  2. Purposes for both the base case and inductive case functions -- you need two here, because the two cases do different things.

Some problems on this homework use the teachpack draw.ss and a few extra bits, some of which you did in previous homeworks:

Download the extra code here: hw08.scm

  1. (15 pts total) Write the following using map or foldr, whichever is more appropriate (but no explicit recursion):

    1. (5 pts) make-circles : list-of-number --> list-of-shape, which makes a circle out of every number in the input list, using circle-tool.

    2. (5 pts) translate-shapes : list-of-shape, posn --> list-of-shape. Translate each element of the list by the specified amount. The posn specifies the distance each shape is to be translated in the x and y directions. For instance, if the given posn is (-2, 5) then a shape located at (23, 15) gets moved to (21, 20).

    3. (5 pts) max-list, which takes in a list and returns the largest element (what does "largest" mean?--does it matter? Write the function for a list-of-nums first, then think about it more generally).
      Note: rather than say this function only takes in non-empty lists, we'll allow empty lists, and use negative infinity (#i-inf.0) as the sentinel value for empty lists of numbers.
      (This is a convenient value for max-list's code, but may or may not be a reasonable answer for different problems: If you are looking for the wealth of the richest person named Rumpelstilzkin, and you get the answer "infinitely in debt", does this mean there is no such name person, or were there so-named people who lost a wager to the tune of "more money than anybody can ever name"? How can you handle this?

  2. (10 pts total) Counting elements

    1. (5 pts) Write a visitor to count all the elements in a list using reverse accumulation.

    2. (5 pts) Write a visitor to count all the elements in a list using forward accumulation. Hint: if an accumulator-style function uses a helper function, what does an accumulator-style visitor use?

  3. (25 pts) Filtering

    1. (10 pts) Write a filter visitor that removes all the negative numbers from a list-of-numbers.

    2. (5 pts) Write a curried function, called make-comparer, that takes a number, let's call it "N" and returns a function that returns true if it's input is less than N.
      That is, make-comparer: num --> (num --> boolean)

    3. (10 pts) Rewrite your filter visitor such that it uses its base & inductive case functions' input parameter as a comparison function. The comparison function takes in a single number and returns true or false. Prove that by using your results from the this and the last problem, you can now write a single line of code that will filter out (remove) all the numbers in a list-of-num that are less than any given number.

  4. (10 pts) Write a foldr for natural numbers. Your function, called foldrn, should have the following contract:
    foldrn: (function: natnum any1 --> any1) any1 natnum --> any1

    Test cases (add more of your own): 
        (= 42 (foldrn + 42 0))

    (= 15 (foldrn + 0 5))

    (equal? (list 10 9 8 7 6 5 4 3 2 1) 

            (foldrn (lambda (n rr)

                       (cons n rr))

                    empty

                    10))
  5. (15 pts) Without visitors, implement map in terms of foldr. Hints: a) use a lambda and utilize it's closure to eliminate the passing of a crucial input parameter. b) this function does not need the design template.

  6. (15 pts) Using visitors, implement a map visitor in terms of a foldr visitor (see Lecture 22). Hint: Look at the previous problem and ask yourself why it didn't need the design template. The visitor pattern enforces the design template however, so what does the results of the previous problem say about the relationship between the base and inductive cases?

  7. (15 pts) Write a visitor called lastList that takes a list as an input parameter. This visitor, when executed, will remove all the elements of the input list that correspond to elements of the host list (the list the visitor is being execute on), returning the remainder of the input list. For instance, if the host list has 3 elements and the input list has 5 elements, the result is the last 2 elements of the input list.
    1. If the host list has nH elements and the input list has nI elements, where nH < nI, then a list with the last (nI-nH) elements of the input list should be returned.
    2. If the host list and the input list are the same length, then the empty list should be returned.
    3. If the host list is empty, the entire input list is to be returned.
    4. If the host list is longer than the input list, an empty list should be returned.
    5. No cond or local are needed! You will need to make a call to another non-recursive visitor internally, but that can defined right where you use it.
    6. If you don't use an input parameter, just pass null as its value.

      Note that some of the above conditions will get handled automatically when the others are satisfied.

      The visitor should satisfy these test cases: 
      "lastList test cases:"

(equal? (list 1 2 3) (execute empty lastList (list 1 2 3)))

(equal? (list 3) (execute (list 'a 'b ) lastList (list 1 2 3)))

(equal? (list 2 'howdy 3 "yahoo y'all!") 

        (execute (list 'a 42 'b ) lastList (list 1 'z  'x 2 'howdy 3 "yahoo y'all!")))

(equal? empty (execute (list 'a 'b 'c 'd) lastList (list 1 2 3)))

  8. (15 pts extra) Write fold-left as a visitor. Use the same FoldInp structure as used in class (see Lecture 22) to hold the base case value and the inductive case function.

  9. (15 pts extra) Rewrite the sort function function from the last homework as a visitor that takes a Sorter structure as an input parameter.

105 points total + 30 points extra

 

Last Revised Sunday, 17-Oct-2004 02:17:33 CDT

©2004 Stephen Wong and Dung Nguyen