107 F '08
The Recipes
The Style
The Universe
The World
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Set 10
Set 11

Problem Set 7


Due date: 11/06


The goal of this problem set is to help you design structurally recursive and generative recursive functions, dealing with all forms of data. You must learn to pinpoint which design approach each function uses and whether or not using an accumulator-style is useful or not.


HtDP: 31.3.1, 31.3.2, 31.3.3, 31.3.4, 31.3.5, 31.3.6, 31.3.7, 31.3.8, 32.2: all exercises or 32.3: all exercises

Required Problems:

Note: You must annotate each function with the design strategy that you used:

  • domain knowledge (algebra, physics, watching traffic lights)
  • function composition: a function that contains a conditional is not designed via function composition; expressions such as (f w (g x y) z) is about all you may use then;
  • structural design, on the 6th argument
  • structural design, on the 4th and 6th argument (if you choose this option, also document which of the three situations you are working with)
  • generative design;
  • design of abstraction over structural repetition;
  • design of abstraction over gen-rec repetition.
If you use a design "with accumulators", be sure to explain the connection between the local recursion argument, the accumulator, and the initial argument; otherwise you can't get credit. You may also use a design "with existing abstractions" if you use one of the functions from page 313.

  1. Design the function render, which consumes enumerations, nested arbitrarily deep, and renders them:
        (define-struct ul (list))
        (define-struct ol (list))
        ;; Enum is one of: 
        ;; -- (make-ul LOI)
        ;; -- (make-ol LOI)
        ;; LOI is one of: 
        ;; -- (cons Item empty) 
        ;; -- (cons Item LOI)
        ;; Item is one of: 
        ;; -- String 
        ;; -- Enum 
    Here is a somewhat complex illustration of its output:
    deeply nested ordered and unordered lists

    Domain knowledge: We will use Safari's rendering strategy for nested unordered lists. That is, the outermost unordered list uses bullets (•); the first nested level comes with circles (ο); the third level's anchor is square. For all levels below the third one, Safari uses the square. As always, a nested enumeration is offset by one blank line and every item (including nested enumerations) are separated by a blank space from their anchor.

  2. Project: Modify your solution of problem 3.4 so that the ball performs its complete movement in one tick. That is, the ball moves for an entire tick and bounces as many times--off the wall, off the paddle--as possible according to its initial velocity and location.

    The idea is to move the ball to the closest obstacle, to bounce it, and to repeat this process for the remaining fraction of time.

    Domain knowledge: If an object O moves from P to Q at velocity V, it has traveled for a time equal to the distance between those two points divided by the O's speed, which is the magnitude of V. Dually, one tick minus the time traveled for moving from P to Q is the remaining fraction of a tick that remains to move the ball. -- Stop when the fraction of time has gotten too smal. Keep in mind that it is better to compare floating point numbers with < or ≤ than with =.

last updated on Tue Jun 9 22:21:18 EDT 2009generated with PLT Scheme