COMP 210 Homework #8

Fall 2002

Due Mon. Oct. 28. at the start of class

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 shapes.ss , a few extra bits, some of which you did in previous homeworks:

• posns,
• translate-shape: shape, num, num --> shape ,
• draw-shape: shape --> true,
• draw-shapes: list-of-shape --> true ,
• circle-tool : number --> circle
  
  Do not re-write these provided functions!

Download the extra code here: hw08.scm

1. (25 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.
      
      
   3. (10 pts) draw-many-shapes: num num --> true. Draws a given number of rows of a given number of the same shapes in each row. The rows should alternate circles and squares -- i.e. one row of circles followed by one row of squares followed by one row of circles, etc. . The size of the shapes should increase from left to right.
      
      
   4. (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. (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.
   
   
5. (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?
   
   
6. (15 pts extra) Write fold-left as a visitor.
   
   
7. (15 pts extra) Rewrite the sort function function from the last homework as a visitor that takes a Sorter structure as an input parameter.

90 points total + 30 points extra