On this page:
List Traversal Functions
Using Local
Putting it all together..
Before you go..

Lab 6h Loops from Local

home work!

Purpose The purpose of this lab is to practice the use of existing list-processing functions and to explore the power of local function definitions.


List Traversal Functions

30 min

Lists are an important data structure and are vital for nearly every program. So list traversal and manipulation is an important skill to have.

Let’s say that the professors have a list of every student to keep track of their names and their current grade.

(define-struct student (name grade))
; A Student is a (make-student String Number)
; interpretation: (make-student n g) represents a student
;  whose name is n and whose grade is g
; Examples:
(define student1 (make-student "Adrian" 95))
(define student2 (make-student "Brad" 65))
(define student3 (make-student "Charlie" 87))
; student* :: [List-of Student]
(define student* (list student1 student2 student3))

Sample Problem Create templates for functions that process Student and [List-of Student].

Professor Ahmed always feels charitable, so she wants to give everyone a one-point bump to their final grade. To do that, she follows the design recipe:

; [Listof Student] -> [Listof Student]
; increase the grades of all students in the list
(define (all-we-need-is-love students)
    [(empty? students) empty]
    [(cons? students)
     (cons (help-student-out (first students))
           (all-we-need-is-love (rest students)))]))
; Student -> Student
; given student s a boost
(define (help-student-out s)
  (make-student (student-name s) (add1 (student-grade s))))

As you can probably tell, these functions couldn’t possibly have been designed by one experienced program designer. Otherwise you wouldn’t see such vastly differing purpose statements, degree of abstraction, program organization, and so on. If you would like to practice your organization skills, improve these definitions.

But then Professor Felleisen comes by. Since Matthias hates each and every one of you, he decide that he wants to lower your grades:
; [Listof Student] -> [Listof Student]
; return a list of students with their grades decreased by 1 point
(define (tough-love students)
    [(empty? students) empty]
    [(cons? students)
     (cons (adjust-student-grade (first students) -1)
           (tough-love (rest students)))]))
; Student Number -> Student
; Given a student s, adjust their grade by the given number
(define (adjust-student-grade s adjust-amt)
  (make-student (student-name s)
                (+ (student-grade s) adjust-amt)))

Exercise 1 Copy and paste these functions into DrRacket. Since help-student-out and adjust-student-grade are used only in all-we-need-is-love and tough-love respectively, it is quite clear that the programs should use local to bring this idea across to future readers. Re-organize the programs using local.

Professor Van Horn happened to be walking by, and he saw what Professors Felleisen and Ahmed were doing. He reminded them that they were wasting their time and energy using cond, when list traversal functions made doing anything with lists so much easier.

; [Listof Student] -> [Listof Student]
; ... see above ...
(define (all-we-need-is-love.v2 students)
  (local (; Student -> Student
          ; ...
          (define (add-love one-student)
    (map add-love students)))
; [Listof Student] -> [Listof Student]
; ... see above ...
(define (tough-love.v2 students)
  (local (; Student -> Student
          ; ...
          (define (push-em-down one-student)
    (map push-em-down students)))
And lo and belold, Prof. Van Horn’s functions worked just as well as Amal’s and Matthias’s

Exercise 2 Explain how DVH came up wth map via signature matching in the book’s table. Then you explain that you always use local to create the function needed for mapping and use the signature for map to explain the signature for the local functions.

> students

(list (student "Adrian" 95) (student "Brad" 65) (student "Charlie" 87))

> (all-we-need-is-love students)

(list (student "Adrian" 96) (student "Brad" 66) (student "Charlie" 88))

> (all-we-need-is-love.v2 students)

(list (student "Adrian" 96) (student "Brad" 66) (student "Charlie" 88))

> (tough-love students)

(list (student "Adrian" 94) (student "Brad" 64) (student "Charlie" 86))

> (tough-love.v2 students)

(list (student "Adrian" 94) (student "Brad" 64) (student "Charlie" 86))

Exercise 3 Finish DVH’s design.


30 min

See ISL’s built-in list processing functions. (Scroll up for function signatures).

Exercise 4 Use map to create a function called student-names that, given a list of students, generates a list of everyone’s names.

Part of a professor’s job is helping those who are really struggling with the material. What would be really helpful for the professors is if they could generate a list of students in danger of failing (grade < 70).

Exercise 5 Design a function called failing-students, which returns a list of students in danger of failing.

Exercise 6 Now, design a function called failing-students?, which checks if any students are in danger of failing.

Exercise 7 Design a function that produces a list of just the names of the students in danger of failing.

Exercise 8 Design a function that takes a list of students and returns a list of strings in the format "Hello <Student name>. I noticed you’re struggling. You should see a tutor or TA!". This list should only contain strings addressed to students in danger of failing.

Exercise 9 Design a function called class-average, which computes the class average. A couple things to keep in mind: the class average is the sum of everyone’s grades divided by the total number of students. But beware dividing by 0!

Challenge Problem It is a well-known fact all the list traversal functions can actually be written using just foldl. Rewrite tough-love using foldl.


Using Local

Switch partners

30 min Local allows you to do more than just define a single helper function within the context of another function! You can also define constants, multiple functions, or even both! In the case of numroots below, defining the left-side and right-side constants prevents wasteful repeated computation.

; Number Number Number -> Number
; Determine the number of roots in a quadratic equation
(define (numroots a b c)
  (local [(define left-side (* b b))
          (define right-side (* 4 a c))
          (define result (- left-side right-side))]
    (cond [(> result 0) 2]
          [(= result 0) 1]
          [(< result 0) 0])))

You should be very familiar with how your homework is graded by now. There is a maximum number of points, and mistakes cost you a few points here and there. Therefore, a particular assignment can be represented as a sum of a list of numbers, where the maximum point value is first, and subsequent values are point detractions.

; A GradedAssignment is a list of numbers where the first number
; is the total point value for the assignment and all subsequent
; numbers are negative (and sum to less than the first number)
; Examples:
'(100 -3 -1 -5 -2 -4)  ; =>  85 / 100 => 85%
'(145 -10 -6 -3 -8 -1) ; => 117 / 145 => 81%

Exercise 10 Professor Razzaq likes getting a human readable grade for each assignment. Design a function called assignment-stats which, given a GradedAssignment, prints out "This student received: 75% (C)". Don’t calculate the grade twice!

Exercise 11 Design a function which takes a list of names (strings) and a list of GradedAssignments and creates a list of Students. The first GradedAssignment corresponds to the first name, and so on. Hint: these list processing functions can take more than one list!

Putting it all together..

When one of your TAs was finished playing with her extensive collection of rubber duckies, she pulled out the bathtub drain and watched as each duck swirled closer to the drain and eventually disappeared down it. "I could make big-bang do that!" she thought excitedly.

Complete the following exercises without redoing any computations unnecessarily, and use list abstractions.

Exercise 12 Find a picture of a rubber ducky and a menacing whirlpool.

Exercise 13 Your rubber duckies should randomly appear on a constant scene of the whirlpool, gradually circle the drain at a constant speed, and disappear down it. Design a plausible world state for big-bang, some constants that you think will be important, and create a stub main function that takes in the number of duckies as an argument.

Exercise 14 Design a function that takes in a number of duckies n and returns your representation of n duckies. Use build-list.

Exercise 15 Design your on-draw handler, and have it place all the ducks at their proper locations around the whirlpool. Use foldl or foldr.

Your TA remembered enough about fluid dynamics to produce the following function:

; Posn -> Posn
; produces a new posn that is the next point on a
; roundabout path to the CENTER
(define (go-with-the-flow p)
  (local [(define x (posn-x p))
          (define y (posn-y p))
          (define rx (- x (posn-x CENTER)))
          (define ry (- y (posn-y CENTER)))
          (define angle (atan (- rx ry) (- 0 rx ry)))]
    (make-posn (+ x (* SPEED (cos angle)))
               (+ y (* SPEED (sin angle))))))

As you can see, her version defines where the CENTER of the whirlpool is located, and the SPEED at which to move the duckies.

Exercise 16 Design your on-tick handler. It should slowly cause the duckies to circle the drain and stay there (for now). You can adapt go-with-the-flow to work with your setup, or write a new function to move the duckies. Use map.

Exercise 17 Define the function safe-from-drain? and use it to filter out the duckies who have gotten within a specified RANGE of the CENTER. Add this functionality to your on-tick handler.

Exercise 18 Finally, define a function replenish-duckies that ensures there are always n duckies on the scene (you may find that locally defining your on-tick handler is helpful!). For example, if you chose to represent the duckies as a list, replenish-duckes would take in a list of less than n duckies and return a list with n duckies.

If you finish with time to spare, consider some of the following exercises:

Exercise 19 More duckies! Download more pictures of duckies and randomize them as they appear.

Exercise 20 Add an on-mouse handler that lets you save duckies from the drain by clicking on them, or lets you place new duckies on the scene.

Exercise 21 Instead of a picture, you can represent the whirlpool as hundreds of blue dots that are also traveling towards the center, just like ducks. See if you can do this easily by abstracting over your duck functions!


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.