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

Lab 6 List abstractions

home work!

Purpose The purpose of this lab is to practice the use of existing list-processing functions. Use Intermediate Student Language.


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
; where n is a student's first name and
;       g is a Number [0-100] representing a student's grade
; Examples:
(define student1 (make-student "Adrian" 95))
(define student2 (make-student "Brad" 65))
(define student3 (make-student "Charlie" 87))
; student* : [Listof Student]
(define student* (list student1 student2 student3))

Sample Problem Create templates for functions that process Student and [Listof 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:

; all-we-need-is-love : [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)))]))
; help-student-out : 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 Shivers comes by. Since Olin hates each and every one of you, he decide that he wants to lower your grades:
; tough-love : [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)))]))
; adjust-student-grade : 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)))

Professor Lerner happened to be walking by, and he saw what Professors Shivers 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.

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

Exercise 1 Explain why Ben decided to use map as oppose to the other list functions. Then, use the signature for map to explain the signature for the helper 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 2 Finish Ben’s redesign of all-we-need-is-love and tough-love by filling in the ...’s.


30 min

See ISL’s built-in list processing functions..

Exercise 3 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 4 Design a function called failing-students, which returns a list of students in danger of failing.

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

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

Exercise 7 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 8 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 foldr. Rewrite tough-love using foldr.


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 9 After an assignment gets graded, a new Student needs to be created to represent what the student received on the assignment. Design a function called assignment-stats which, given a Student and a GradedAssignment, updates the student’s grade to the new value (the sum of the GradedAssignment).

Exercise 10 Design a function which takes a list of names (strings) and a [Listof GradedAssignment] and creates a [Listof Student]. 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

In past years classes have developed various big-bang programs. This particular program, the turtle interpreter, has quite exemplary code — 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.


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.