Lab 8: Functions are Values Too

Remember

Quiz


Boston Marathon

Spring is almost here, and in Boston, Spring means Boston Marathon. Over 10000 runners come to run one of the oldest races. The organizers have a daunting task to keep track of all the runners, their times, classify them into categories, and report in a timely way their progress and the final results.

The organizers need to keep track of the name of the runner, runner's age, whether the runner is male or female. Each runner gets a bib with a number, and an electronic chip (with a different number) that is attached to the shoelaces and records the runner's time as the runner passes the starting line, the five mile checkpoints, and, of course the finish line.


Keeping track of the Runners

The following data definitions describe (a simplified) the way the organizers keep track of the runners.

;; BOSTON MARATHON

;; name of the runner, runner's age, male or female, bib, run-time
;; A Runner is (make-runner String Number Boolean Number)
(define-struct runner (name age male bib rtime))

;; Examples of data:
;; Name age male? bib time
(define br (make-runner "Bill Rogers" 51 true 23 143))
(define fs (make-runner "Frank Shorter" 48 true 29 153))
(define kk (make-runner "Komo Kenyata" 25 true 13 131))
(define jb (make-runner "Joan Benoit" 51 false 65 165))
(define as (make-runner "Anne Smith" 32 false 95 198))


;; the whole list of runners
(define marathon (list br fs kk jb as))
   

Selecting the Runners

The marathon organizers also have to report the results for the runners in different categories -- males under 40, males under 50, females under 40, females under 50, etc.

The following function produces a list of all male runners:

;; produce a list of all female runners
;; all-female: [Listof Runner] -> [Listof Runner]
(define (all-female rlist)
  (cond
    [(empty? rlist) empty]
    [(cons? rlist)
     (cond
       [(equal? (runner-male (first rlist)) false) 
        (cons (first rlist) (all-female (rest rlist)))]
       [else 
        (all-female (rest rlist))])]))

;; examples
(check-expect (all-female marathon) (list jb as))

>The following function produces a list of all runners older than 40 years:

;; produce a list of all runners older than 40 
;; over-40: [Listof Runner] -> [Listof Runner]
(define (over-40 rlist)
  (cond
    [(empty? rlist) empty]
    [(cons? rlist)
     (cond
       [(> (runner-age (first rlist)) 40) 
        (cons (first rlist) (over-40 (rest rlist)))]
       [else 
        (over-40 (rest rlist))])]))

;; examples
(check-expect (over-40 marathon) (list br fs jb))
Exercise 1: Design a function male-masters that consumes the list of runners and produces a list of only male runners older than 40 years.

Exercise 2: Abstract over these two functions and design a function that produces a new list from the given list, that contains only those item that satisfy a given predicate function.

Exercise 3: Now design a function that selects all male runners that finished running in less than 2 hours and 30 minutes and all females that finished under 3 hours -- they qualify for the next year's race.


Sorting the Runners

Of course, if the organizers produce the lists of runners in some random order, nobody can make sense of any information the lists contain. The organizers need to report the winners, the Boston Globe publishes the results sorted by the time when the runners crossed the finish line, the runners may want to see the list sorted by their names, or by the bib numbers. Let's see if we can help them design the necessary programs.

Exercise 4: Design a function called sort-bibs that sorts the runners list by the bib numbers.

Exercise 5: Design the function sort-age that sorts the runners list by their ages.

Exercise 6: Design the function sort-names that sorts the runners list by the names of the runners. (Do not worry that they will be sorted by their first names.)


Getting Tired of Sorting

You just wrote three sorting functions. We know we will need many more sorting functions. Remember the new commandment: Thou shalt nor repeat code! But looking at the first two sorting functions we see that they are very similar.

Compare the three sort functions. Highlight the differences. You see that the difference is in the insert function, where we compare the first item of the list with the item we wish to insert.

Exercise 7: Design a function (a predicate) for each of the three sorting problems that consumes the two elements of the list and produces true when the first item comes before the second in our system of ordering the list items.

Exercise 8: Now design an insert method that inserts a new item into a sorted list using a given predicate function to determine the ordering.

Exercise 9: Finish the design abstraction of the sorting so it works for any list.

Exercise 10: Now use your new sorting function to sort the runners by their running time.


Generating Reports

You now want to make lists that may not contain all the information you have about each runner. A company that sells running gear would like just a list of names and ages. The statisticians only want the bib numbers and the running time. They also want another list that has running times and whether the runner was male or female, as well as the runner's age.

Exercise 11: Design three functions: name-age, bib-time, time-mf-age each producing one of the desired lists. Represent the information about each runner as new struct.

Exercise 12: Abstract over the three functions. Use your result to produce a list of runners names and their gender shown as "Frank Shorter male" or "Joan Benoit female".