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

Lab 6 Abstraction

home work!

Purpose In this lab we will practice recognizing similarities in function definitions and in data definitions and how to avoid them. This lab also practices the use of existing list-processing functions. Use Intermediate Student Language.

image

Abstraction

When we solve problems, we sometimes find that the solution to one problem looks a lot like the solution to another one. Check out the following functions and data definition. From now on we will leave out the definition for lists, and use the [List-of X] notation.

; A [List-of Number] is one of
;  empty
;  (cons Number [List-of Number])
 
; lon-add2 : [List-of Number] -> [List-of Number]
; Add two (2) to each element of the given list of numbers
(define (lon-add2 lon)
  (cond [(empty? lon) empty]
        [else (cons (+ (first lon) 2)
                    (lon-add2 (rest lon)))]))
 
; lon-add5 : [List-of Number] -> [List-of Number]
; Add five (5) to each element of the given list of numbers
(define (lon-add5 lon)
  (cond [(empty? lon) empty]
        [else (cons (+ (first lon) 5)
                    (lon-add5 (rest lon)))]))

Is it clear what each function does? Since these functions are almost identical you are hopefully asking "Why would you do that?!".

Exercise 1 Design a function named lon-add-n that abstracts both of the functions above by taking an extra argument, which is the number to be added to each element.

Exercise 2 Rewrite both lon-add2 and lon-add5 using your more general function. Write a few tests for each to be sure they work as expected.

Switch roles Try another:
; A [List-of String] is one of
;  empty
;  (cons String [List-of String])

Exercise 3 Design a function named starts-with-cat that consumes a [List-of String] and constructs a list of those strings that start with "cat". For example,

> (starts-with-cat (list "oboe" "cataract" "ox" "catharsis"))

(list "cataract" "catharsis")

Exercise 4 Design Write a function named starts-with-dog that consumes a [List-of String] and constructs a list of those strings that start with "dog".

Exercise 5 Design a function named starts-with that abstracts both of the functions above, taking an extra argument, which is the substring to be found in each element. Note to avoid "index out of range" errors you might want to ensure the prefix is shorter than the string you are checking against.

Rewrite both starts-with-cat and starts-with-dog using your more general function. Write a few tests for each to be sure they work as expected.

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
; 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].

Your Professors feel charitable and want to give everyone a one-point bump to their final grade. To do that, they follow 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)
  (cond
    [(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 they decide that is too generous and they want to lower the grades back to the original grades:

; tough-love : [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)))]))
 
; 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)))

Your professors 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))

Exercise 6 Explain why we decided to use map as opposed 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 7 Finish the redesign of all-we-need-is-love and tough-love by filling in the ...’s.

image

30 min

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

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

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

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

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

image

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 14 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 15 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!

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.