CS 5010: Problem Set 05: Working with Higher-Order Functions

Out: Monday, February 15, 2016

Due: Monday, February 22, 2016 at 5pm (corrected from the "February 21" in an earlier version)

Revised: Thursday, February 18, to say all of a train's stops are in the same time zone. (That isn't realistic, but it makes the problem set easier.)

The goal of this problem set is to give you practice using higher-order functions like map, filter, foldr, etc.

You must use the HtDP Intermediate Student Language + Lambda to solve the problems. You are to use HOFs wherever it is appropriate. These will replace almost all the uses of the List template.

For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line

(require "extras.rkt")
at the top of your file with the other requires. Then, for each problem, put in lines that say
(provide function)
for each deliverable function, as you have done on previous problem sets. This will allow our testing framework to import your file and do automated testing on it.

Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, code, and tests. Be sure to follow our coding conventions. This will make the TA's job much easier.

Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS05.

  1. (trains). For this problem, you will deliver a file named trains.rkt that implements a data base of train schedules, using higher-order functions wherever possible and appropriate.

    You will need to design a StationStop data type that names a train station and tells what time a train arrives at and departs that station. You will also need to design TrainTime and Schedule data types.

    Your trains.rkt file must provide the following 15 functions:

    ;;; make-schedule : String ListOfStationStop -> Schedule
    ;;; GIVEN: the name of a train and its list of station stops
    ;;; WHERE: all station stops are in the same time zone
    ;;; RETURNS: the schedule for that train
    ;;; EXAMPLE:
    ;;;     (schedule-name (make-schedule "Out of Service" empty))
    ;;;     => "Out of Service"
    ;;; schedule-name : Schedule -> String
    ;;; GIVEN: a train schedule
    ;;; RETURNS: the name of the train that runs on that schedule
    ;;; schedule-stops : Schedule -> ListOfStationStop
    ;;; GIVEN: a train schedule
    ;;; RETURNS: its list of station stops
    ;;; make-stop : TrainTime TrainTime String -> StationStop
    ;;; GIVEN: arrival and departure times, and the name of a station
    ;;; RETURNS: a station stop that incorporates that information
    ;;; EXAMPLE:
    ;;;     (station-name (make-stop (make-train-time 11 55 "P")
    ;;;                              (make-train-time 12 03 "A")
    ;;;                              "Pittsfield"))
    ;;;     => "Pittsfield"
    ;;; make-brief-stop : TrainTime String -> StationStop
    ;;; GIVEN: an arrival or departure time, and the name of a station
    ;;; RETURNS: a station stop for which the arrival and departure times
    ;;;     are the same
    ;;; EXAMPLE:
    ;;;     (arrival-time (make-brief-stop (make-train-time 3 41 "A") "Elko"))
    ;;;   = (departure-time (make-brief-stop (make-train-time 3 41 "A") "Elko"))
    ;;;   = (make-train-time 3 41 "A")
    ;;; arrival-time : StationStop -> TrainTime
    ;;; departure-time : StationStop -> TrainTime
    ;;; GIVEN: a station stop
    ;;; RETURNS: the arrival or departure time for that station stop
    ;;; EXAMPLES:
    ;;;     (arrival-time (make-stop t1 t2 stn)) => t1
    ;;;     (departure-time (make-stop t1 t2 stn)) => t2
    ;;; station-name : StationStop -> String
    ;;; GIVEN: a station stop
    ;;; RETURNS: the name of the train station for that stop
    ;;; make-train-time : Integer Integer String -> TrainTime
    ;;; GIVEN: the hours, minutes, and am/pm indicator for an arrival or departure
    ;;; WHERE: the first argument is in the range [1,12] and indicates hours
    ;;;        the second argument is in the range [0,59] and indicates minutes
    ;;;        the third argument is one of "A" or "P", indicating am or pm
    ;;; RETURNS: the time of an arrival or departure, in some unspecified time zone
    ;;; train-time-hours : TrainTime -> Integer
    ;;; train-time-minutes : TrainTime -> Integer
    ;;; train-time-am/pm : TrainTime -> String
    ;;; GIVEN: an arrival or departure time
    ;;; RETURNS: the hours, minutes, or am/pm indicator for that time
    ;;; EXAMPLES:
    ;;;     (train-time-hours   (make-train-time 1 10 "A")) => 1
    ;;;     (train-time-minutes (make-train-time 1 10 "A")) => 10
    ;;;     (train-time-am/pm   (make-train-time 1 10 "A")) => "A"
    ;;; stops-at? : Schedule String-> Boolean
    ;;; GIVEN: a train schedule and the name of a train station
    ;;; RETURNS: true iff the train stops at that station
    ;;; minutes-between : Schedule String String -> Integer
    ;;; GIVEN: a train schedule and the names of two stations
    ;;; WHERE: both stations are on the train's schedule,
    ;;;     but either of the two stations may come first on that schedule
    ;;; RETURNS: how long the train takes to get from one station to the other,
    ;;;     in minutes
    ;;; longest-stops : Schedule -> ListOfString
    ;;; GIVEN: a train schedule
    ;;; RETURNS: a list of names for the stations that have the longest delays
    ;;;     between arrival and departure; if one stop has a longer delay
    ;;;     than all other stops, then the list will contain only one name
    ;;; EXAMPLES:
    (define downeaster
       (list (make-brief-stop (make-train-time 5 20 "A") "Portland, ME")
             (make-brief-stop (make-train-time 5 42 "A") "Saco, ME")
             (make-brief-stop (make-train-time 5 59 "A") "Wells, ME")
             (make-brief-stop (make-train-time 6 17 "A") "Dover, NH")
             (make-brief-stop (make-train-time 6 25 "A") "Durham, NH")
             (make-brief-stop (make-train-time 6 39 "A") "Exeter, NH")
             (make-brief-stop (make-train-time 7 00 "A") "Haverhill, MA")
             (make-brief-stop (make-train-time 7 29 "A") "Woburn, MA")
             (make-brief-stop (make-train-time 7 50 "A") "Boston, MA"))))
    (define acela-express
       "Acela Express 2163"
       (list (make-brief-stop (make-train-time 11 10 "A") "Boston, MA")
             (make-brief-stop (make-train-time 11 46 "A") "Providence, RI")
             (make-brief-stop (make-train-time  1 13 "P") "New Haven, CT")
             (make-stop       (make-train-time  2 45 "P")
                              (make-train-time  3 00 "P")
                              "New York, NY")
             (make-brief-stop (make-train-time  3 15 "P") "Newark, NJ")
             (make-brief-stop (make-train-time  4 10 "P") "Philadelphia, PA")
             (make-brief-stop (make-train-time  5 13 "P") "Baltimore, MD")
             (make-brief-stop (make-train-time  5 53 "P") "Washington, DC"))))
    (define coast-starlight
       "Coast Starlight"
       (list (make-brief-stop (make-train-time  9 35 "A") "Seattle, WA")
             (make-brief-stop (make-train-time  1 50 "P") "Portland, OR")
             (make-brief-stop (make-train-time  6 35 "A") "Sacramento, CA")
             (make-stop       (make-train-time  8 35 "A")
                              (make-train-time  8 50 "A")
                              "Oakland, CA")
             (make-brief-stop (make-train-time  1 38 "P") "Paso Robles, CA")
             (make-brief-stop (make-train-time  9 00 "P") "Los Angeles, CA"))))
    (stops-at? downeaster "Haverhill, MA")                            ; => true
    (stops-at? downeaster "New York, NY")                             ; => false
    (minutes-between acela-express "Boston, MA" "Philadelphia, PA")   ; => 300
    (minutes-between coast-starlight "Seattle, WA" "Los Angeles, CA") ; => 2125
    (longest-stops acela-express)                    ; => (list "New York, NY")

    As elsewhere in this problem set, use HOFs whenever possible and appropriate.

  2. (screensaver-5). Rewrite screensaver-4 to use higher-order functions whenever possible instead of using recursions down a list. Provide the same functions as for screensaver-4. Name your file screensaver-5.rkt .

Last modified: Thu Feb 18 2016