On this page:
List Traversal Functions
Using Local
Abstraction in Practice
Before you go..

Lab 6 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.

image

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)
  (cond
    [(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)
  (cond
    [(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.

image

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.

image

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!

Abstraction in Practice

While most of you did not finish the turtle interpreter last week, some did and the code is quite exemplary—for a BSL programmer. Now that you have practiced abstraction and the use of existing abstraction on finger exercises, it is time to practice it on an existing program. Find functions in the solution to Lab 5 that share a pattern and abstract over them. Find functions that may benefit from existing list abstractions and use those abstractions.

image

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.