Lab 4 Lists
Purpose: The purpose of this lab is to give you some hands-on experience with list-processing functions and programs. When you walk out of this lab, you should understand a variety of list-based data definitions and how to design functions for these.
Textbook references: Chapter 8: Lists, Chapter 9: Designing with Self-Referential Data Definitions, Chapter 10.2: Structures in Lists
Hand-Rolled Lists
Goals: Practice defining and processing self-referential data.
Sample Problem Develop a data definion for hand-rolled lists of numbers (abbreviated HRLoN).
(define-struct empty-lon ()) (define-struct cons-lon (left right)) ; A HRLoN (Hand-rolled List of Numbers) is one of: ; - (make-empty-lon) ; - (make-cons-lon Number HRLoN)
Sample Problem Create three examples of HRLoNs.
; Examples (define HRLON1 (make-empty-lon)) (define HRLON2 (make-cons-lon 1 HRLON1)) (define HRLON3 (make-cons-lon 7 HRLON2))
Sample Problem Develop a template for HRLoNs.
; hrlon-temp : HRLoN -> ??? (define (hrlon-temp ahrlon) (cond [(empty-lon? ahrlon) ...] [(cons-lon? ahrlon) ... (cons-lon-left ahrlon) ... ... (hrlon-temp (cons-lon-right ahrlon)) ...]))
Sample Problem Design the function hrlon-sum which sums up all the numbers in a hand-rolled list of numbers.
; hrlon-sum : HRLoN -> Number ; Sums up all the numbers in the list (define (hrlon-sum ahrlon) (cond [(empty-lon? ahrlon) 0] [(cons-lon? ahrlon) (+ (cons-lon-left ahrlon) (hrlon-sum (cons-lon-right ahrlon)))])) (check-expect (hrlon-sum HRLON1) 0) (check-expect (hrlon-sum HRLON2) 1) (check-expect (hrlon-sum HRLON3) 8)
Lists
Goals: Practice defining and processing lists.
Exercise 1 Good news, everyone. We just got word from upstairs that all the components of lists are working again! Now this Hand-rolled List of Numbers thing seems a bit unnecessary. Develop a new data-definition for a List of Numbers, using cons and '().
Exercise 2 Develop a template for your new type of data.
Exercise 3 Design the sum function. It should operate just like hrlon-sum but accept your new type of data as input rather than HRLoNs.
Exercise 4 Design the function average that consumes a list of numbers and returns the average of those numbers.
Exercise 5 Design the function keep-evens, which takes a list of numbers and only keeps the even numbers in the list. even? will likely help.
Exercise 6 Design the function sum-all that consumes a list of lists of numbers and returns the sum of all the numbers from all of the lists.
Hint: Follow the design recipe, starting with a data definition for a list of lists of numbers. What of the preceding problems might be helpful here?
Lists in the World
Goals: Practice defining and processing lists. Practice using lists in a 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 clicking the mouse. 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.
(require 2htdp/image) (require 2htdp/universe) ; main : Ball -> LoB (define (main b) (big-bang (cons b '()) ; <- the world state is a LoB [to-draw draw-lob] [on-tick go] [on-mouse new-ball])) ; go : LoB -> LoB ; Move balls, apply gravity, and then filter out those balls that are off screen (define (go lob) (on-screen-balls (apply-gravity (move-all lob))))
As you can see, the scientists kind of followed the design recipe for world programs. But you know how scientists are. So they leave it to you to finish the job.
Exercise 7 Develop a data definition for a Ball. A Ball should have a position in x and y and a velocity in x and y (pixels per clock tick). What is a velocity? What is a speed? (Reminder: You’ve seen this definition before in prior assignments or labs...)
Exercise 8 Develop a data definition for a LoB, pronounced “list of balls”.
Exercise 9 Develop templates for both data definitions. The template for LoB should refer to the template for Ball. Why?
Don’t forget to switch roles with your partner after each function you design so that you both get experience writing functions for lists.
Exercise 10 Design the function draw-ball which takes a Ball and an Image and draws the ball at the correct location onto the image.
Exercise 11 Design the function draw-lob which takes a LoB and draws all the balls in the list onto an empty screen of size 500x500. This function should call your draw-ball function from the previous exercise.
Hint: Use global constants for the size of the canvas rather than putting constant values directly into your code. We do this because you may need to use the canvas size values more than once.
Exercise 12 Design the function off-screen?, which determines whether a ball is off the screen.
Exercise 13 Design the function on-screen which takes a LoB and returns a LoB which contains only the balls which are on-screen.
Exercise 14 Design the function gravity which takes a Ball and creates a new one whose y velocity has been increased by gravitational acceleration.
Hint: Gravitational acceleration is 9.8 m/s2. Also, the default tick-rate for a big-bang program is 30 ticks/second. Now, you just need to convert meters into pixels...
Exercise 15 Design the function apply-gravity which takes an LoB and returns an LoB where every ball’s y velocity has been increased by gravitational acceleration.
Exercise 16 Design the function move-ball that consumes a Ball and creates a new one that has been moved according to its velocity. The new ball’s velocity is the same as the one used as input. If you do not recall what it means for an object to be located at (x,y) and to move by a velocity of (dx,dy), ask a tutor or TA. (Reminder: you’ve done this problem before, too...)
Exercise 17 Design the function move-all that moves every ball in a list of balls according to its velocity.
Exercise 18 Design the function new-ball that adds a ball wherever the user clicks the mouse. The new ball will have a random velocity. You will give this function to on-mouse.
Hint: Use the function random.
You should now be able to run your simulation by calling the main function with some Ball.
Exercise 19 Try adding a color to your Ball structure. Change the drawing function to draw each ball with the correct color. Change the new-ball function to create a new ball of a random color.
Hint: Come up with a function that returns a color string given a number. Then you can call that function with a number generated by random.
Exercise 20 Try adding a size to your Ball structure. Change the drawing function to draw each ball with the correct size. Change the new-ball function to create a new ball of a random size. Make sure this size is not too small or you won’t be able to see the balls!
Before You Go...
If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.