Lab 4h 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.

Notes

For those of you who programmed before, the lists you see here are so-called linked lists, equipped with basic functions (cons, first, rest, cons?, and empty?), which you could of course write in your favorite language. You also encounter empty, a special piece of data.

For everyone, when an interviewer asks in the future whether you know about linked data structures, the answer is yes, we encountered them in the third week in our first lecture. Conventional approaches to programming introduce such data structures at the end of the second semester or in the third one; you have a leg up here.

Chore Today we are pairing you up with a new homework partner. Find a partner, sit down next to him/her and grab a computer. One of the TAs will come through and write down your Husky email addresses so that we know who is partnered up for the next few problem sets.

You may re-use whatever you did with your previous partner for this problem set but you must turn in the next solution set with your new partner.

TA: The "shoulder" should collect the new partnerships while "head" starts lab lecture.

This lab gives you a chance to get to know your partner, to exchange vital information (phone, twitter, facebook, email) and to make a first appointment (when/where you will meet to work on problem sets).

Hand-Rolled Lists, Again

TAs: work through this part with your students.

Last night, one of your TAs (who will remain nameless) was working on the BSL codebase and accidentally broke some functions and values related to lists. Since there hasn’t been time to fix it yet, we’ll have to create our own version of a list.

Sample Problem Your professors have asked your TAs to come up with a function that averages the scores on the last problem set so that they know how hard to make the next one. We were too busy trying to fix the broken BSL codebase. Design a function that averages an arbitrarily long list of numbers.

Using the design recipe, we will break down the above question into smaller steps: data definition, data examples, templates, design of function.

Sample Problem Develop a data definion for hand-rolled lists of numbers. Here is the one we came up with.

(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)

Create three examples of HRLoNs

Structure type definitions without fields look strange but empty is really just such a thing. The key idea is that you get empty?, and it identifies a unique piece of data in BSL.

Note The idea of using structure type definitions without fields shows how to apply the ideas of this course to object-oriented languages such as Java. There you define classes without fields for a similar purpose.

Sample Problem Develop a template for HRLoNs. Remember that the template follows from the data definition via four questions: how many cases, what are the tests to distinguish them, do we need selectors in any of the cases, and does the data definition involve self-references.

Sample Problem Now you are ready to design the function average. Remember to ask the following questions? What kind of inputs does it consume? What type of data does it output? What does this output mean?

Decide with your partner to have one of you write down the signature and purpose. The other partner should be able to come up with functional examples.

Exercise 1 Good news, everyone. We just got word from upstairs that all the components of lists are working again! Good job Racket devs! 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 empty.

Exercise 2 Now re-write average so that it accepts your new type of data as input rather than HRLoNs.

Exercise 3 Design the function overlay-all, which takes a list of images. It overlays each image onto the next image in the TA: explain how to read the documentation, especially the arrow notation for overlay. list. Giving the function an empty list should produce and empty scene of some size. You can choose how big it should be. Hint Remember to follow the design recipe and come up with a data definition for a list of images.

Switch roles.

Exercise 4 Design the function sum-all that consumes a list of lists of numbers and returns the sum of all the numbers in all of the lists.

Exercise 5 Design the function string-of that takes a positive number(n) and a string, and returns a string that contains the given string repeated n times, separatied by a space.

(string-of 4 "Test") ; ==> "Test Test Test Test"

(string-of 2 "What") ; ==> "What what"

Switch roles.

Exercise 6 Design the function reducing that takes a positive number(n) and a string, and produces a list of strings. Each element of the list is the string returned from string-of with a reduced n. Hint Use the above funtion as a helper.

(reducing 4 "Test")  ; ==> (cons "Test Test Test Test"

;          (cons "Test Test Test"

;                (cons "Test Test"

;                    (cons "Test" empty))))

(reducing 2 "What")  ; ==> (cons "What What" (cons "What" empty))

Exercise 7 Design the function lookup that takes a list of Symbols los, and a number n, and returns the nth symbol of the list.

(lookup (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 0) ; ==> 'a

(lookup (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 2) ; ==> 'c

Switch roles.

Exercise 8 Design the function replace that takes a list of Symbols los, a symbol s, and a number n, and returns same list with nth symbol replaced with S.

(replace (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 'new 2)

; ==> (cons 'a (cons 'b (cons 'new (cons 'd empty))))

(replace (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 'yay 0)

; ==> (cons 'yay (cons 'b (cons 'c (cons 'd empty))))

(replace (cons 'a (cons 'b (cons 'c (cons 'd empty)))) 'end 3)

; ==> (cons 'a (cons 'b (cons 'c (cons 'end empty))))

Fun with Gravity

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 around for a bit until they go off the screen. The app should be in a 500 x 500 window. Once they go off screen the scientists don’t care about them anymore.

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.

Switch roles.

Exercise 9 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).

Domain knowledge What is a velocity? What is a speed? If you don’t recall or if you have never heard, do not hesitate to ask the TA.

Exercise 10 Develop a data definition for a LoB (list of Balls).

Exercise 11 Develop templates for both data definitions. The template for LoB should refer to the template for Ball. Why?

Switch roles after each function you design so that you both get experience writing functions for lists.

Exercise 12 Design the function off-screen?, which determines whether a ball is off the screen. Hint Use global constants for the size of the canvas rather than putting constant values directly into your code. You may need to use them more than once.

Exercise 13 Design the function move 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.

Domain knowledge If you do not recall what it means for an object to be located at (x,y) and to move at a velocity of (dx,dy), ask your TA.

Exercise 14 Design the function gravity that consumes a ball and creates a new one whose y velocity has been increased by gravitational acceleration.

Domain knowledge If you do not recall what "adding gravity" means, ask your TA.

Exercise 15 Design the function draw-lob that draws a list of balls into an empty scene.

Exercise 16 Design the function on-screen that filters out all that balls that are off-screen from a list of balls.

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 apply-gravity that applies the gravity function to every ball in a list of balls.

You could now comment out the on-mouse clause with #; and run the program.

Exercise 19 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.

Extra Problems

Exercise 20 Consider the following problem: Given two lists of strings, return a list of strings that contains all combinations of elements from the first list with elements from the second list.

Let’s call the function all-comb. Here’s an example:

; This call

(all-comb (cons "Student: " (cons "Faculty: " empty))

(cons "Mr." (cons "Ms." empty)))

; Returns

(cons "Student: Mr."

(cons "Student: Ms."

(cons "Faculty: Mr."

(cons "Faculty: Ms." empty))))

How can we design such a function? Well, lets start with a smaller problem. How can we take a string s, and a list-of-strings los, and produce a list that contains the strings from los with s on the front? Call this helper function all-comb-help. Here’s an example of its behavior:

(all-comb-help "A" (cons "B" (cons "C" (cons "D" empty))))

; ==> (cons "AB" (cons "AC" (cons "AD" empty)))

Now... how can you put the helper function to work to solve the entire problem? Ask a TA/Tutor if you need help.

Hint You can use the builtin function append (or define your own for practice), which appends two lists.

Exercise 21 Can you re-write all-comb without using append?

Exercise 22 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. Look at the docs for the color? function. Then you can call that function with a number generated by random.