4 Designing Programs on Lists

Purpose This lab practices your design skills for list-processing programs and functions.

Textbook references: Part II: Arbitrarily Large Data

Prelude

Here are two small points. If you feel you have trouble with either one of them, practice and see a member of the staff to check your results.

Function Design for Arbitrarily Large Data

1 minute

At this point you need to be completely familiar with the design of functions that process arbitrarily large pieces of data. Here are some sample data definitions that introduce such data:

; 1.

; A LOI (list of images) is one of:

; – '()

; – (cons Image LOI)

; Problem Design a function that computes the area of all images on LOI.

; 2.

(define-struct stuff [more data])

; A DeepStuff is one of:

; – #false

; – (make-more DeepStuff String)

; Problem Design a function that concatenates all Strings in a DeepStuff.

; 3.

; A PLIS is one of:

; – '()

; – (cons String (cons String PLIS))

; Problem Design a function that concatenates all Strings in a PLIS.

While we have focused on lists and non-empty lists in this part of the course, the actual goal is to introduce you gradually to the idea of such data. The October part of the course is the more generally practically relevant part of the course.

list

1 minute

(list "a" "b" "c") is (cons "a" (cons "b" (cons "c" '()))).

That’s it.

Program Design: Balloon Party

Goal Review the steps of program design recipe:

• Tease out which pieces of information stay constant across time.

• Develop a data representation for the pieces of information that change.

• Design the main function, after deciding which handler clauses are needed.

• Create a wish list for the handlers, developing the headers up to examples.

Goal Practice designing programs that use list-based data definitions

Background It’s that time of year again; registration for the next season of the NBL (National Balloon League) is right around the corner, and this is the year you and your team finally qualify! In order to prep for the big day, you need to practice. Armed with your knowledge of list-based program design, you have the perfect plan.

You want to develop a balloon-popping game. A bunch of balloons, initially all green (see below), will start in random locations and will float up at a constant speed. Clicking on a balloon pops it. If a balloon floats above the top of the screen, it’s considered safe and can’t be popped. The game ends when the only balloons that remain are safely above the screen.

The simulation program should be launched with the number of balloons to be part of the game, and it should return the number of balloons popped.

Data Representation

10 minutes

Code Review #1

10 minutes

The TAs will pick a pair to explain their data representation. Everyone else will use this data representation to complete the rest of the implementation.

··· Stop! Wait for "shipping instructions" ···

Implementation

50 minutes

Exercise 3 Pick your (next) favorite wish from the list and design the function. Follow the recipe! Repeat until your wish list is empty.

Exercise 4 Challenge: The mayor realized that one color of balloon isn’t very exciting. Extend your program so that each balloon is randomly either green, blue, or red.

Code Review #2

15 minutes

Another group will explain how they worked through the design recipe to complete their implementation.