Lab 5 Lists

Purpose: The purpose of this lab is to get some more practice with recursive functions, specifically with recursion over lists of structures.

Textbook references: Chapter 9: Designing with Self-Referential Data Definitions

Code Review

Today we will code review a portion of assignment 4. Feel free to ask questions about the code as we go through it. This is an excellent opportunity to figure out what we were looking for.

For Science

In this lab we will design (yet another) world program.A scientific simulation firm needs to simulate the effects of gravity on an arbitrarily large number of falling balls. Your job is to create a BSL simulation where the scientists can spawn new falling balls by pressing the space bar. They will fall to the ground for a bit until they go off the screen. The app should be in a 500 x 500 window. Once the balls go off screen the scientists no longer care about them.

Step 1: What stays the same?

Exercise 1 Define constants to represent the things that are not changing in the world. This can include graphical constants (images you will need throughout the program) but can also include non-graphical constants.

Step 2: What changes?

Exercise 2 Develop a data definition for a Ball. A Ball should have a color, a position in x and y, and a velocity in x and y (pixels per clock tick).

Exercise 3 Write the template for functions that take in a Ball.

Exercise 4 Define a few examples of Balls to use in your program.

Exercise 5 Develop a data definition for a ListOfBalls (LoB). You should use cons and '() in your data definition, and you should reference the data definition for Ball that you created above.

Exercise 6 Write the template for functions that take in a LoB. Remember that since an LoB references the Ball data definition, your template will have to reference the Ball template.

Exercise 7 Define a few examples of LoBs to use in your program.

Step 3: Which handlers do we need?

Exercise 8 Write down the signatures and purpose statements for the handler functions you need. This is your "wishlist" of functions that you will need to create.

Step 4: Design your handlers

Exercise 9 Design the handlers you decided on in the last step. Remember to follow all the steps of the function design recipe. These steps will help you ensure that your functions all work together the way you expect. As a reminder, gravitational acceleration is approximately 9.8 m/s2. You will want to use the random function to help you generate a new random ball each time the space bar is pressed. The function choose-color from the previous lab will be helpful as well.

Step 5: Put it all together!

Exercise 10 Design a function that uses big-bang to create your program, inserting the functions you defined above into the appropriate clauses.

Additional Practice: Natural Numbers

A recursive data structure we use very often in programming is the collection of natural numbers:

; A Nat, or natural number, is one of:

;  - 0

;  - (add1 Nat)

;

; The predicate for 0 is: zero?

;

; The predicate for (add1 n): positive?

; The selector for (add1 n): sub1

Exercise 11 What is the template for Nat?

Exercise 12 Think about the relationship between the following functions and constants:

empty – 0

empty? – zero?

cons? – positive?

cons – add1

rest – sub1

first – ???

Does anything relate to the list function first? If so, what? If not, why not?

In the following exercises we will redefine some built-in arithmetic functions to get practice writing recursive functions over Nats, so don’t simply reuse the built-in functions.

Exercise 13 Design a function nat-even? that returns true if the given Nat is even. Use only sub1, zero?, nat-even? itself, and not. Do not use even?, odd?, modulo, etc. And yes, zero is an even number.

Exercise 14 Design a function double that doubles the given Nat. Again, you may only use add1 and sub1, and of course double.

Exercise 15 Design a function down-from that takes a Nat n and returns the list of Nats counting down from n. For example,

> (down-from 3)

(cons 3 (cons 2 (cons 1 (cons 0 '()))))

Exercise 17 Design a function nat+ that takes two Nats and computes their sum. Use recursion instead of the built-in + function.

Exercise 18 Design a function nat* that takes two Nats and computes their product. Again, use recursion instead of the built-in * function, though consider making use of nat+.

Exercise 19 Design a function nat-factorial that takes a Nat and computes the factorial of that number. The factorial of a natural number n is given by the product of all natural numbers less than or equal to n (excluding zero). Use your nat* function.

Exercise 20 Challenge: Design a function nat-square that squares the given Nat, but don’t use nat*! You may use add1, sub1, double, nat+, and of course nat-square.