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.

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 Now doubting your TAs’ mental capabilities, the professor has asked the TAs to design a function to check that they’ve correctly added points on the last homework. The poor TAs, crippled by fear, need your help!

Design a function that sums the elements in 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

Structures without fields look strange but this is what is happening with make-empty-lon as well as the built in Racket version empty. The key idea is you can use empty-lon? to identify an empty-lon, which is 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 are there in the data definition?

• What are the tests needed to distinguish them?

• Do we need selectors in any of the cases?

• Does the data definition involve self-references?

Exercise 2 Design the sum function. It should operate just like hrlon-sum but accept 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 Follow the design recipe, starting with 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 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.

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. We do this because you may need to use the canvas size values more than once.

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

Domain knowledge 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 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.

Exercise 15 Design the function draw-lob that draws a list of balls on to an empty canvas.

Hint If you are using overlay instead of place-image then be sure to have a transparent background, by passing the "transparent" color into the empty-scene function. It can also be useful to first design the draw-ball function.

Exercise 16 Design the function on-screen-balls that filters out all that balls that are off of the 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 can now comment out the on-mouse clause with #; to 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.