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

Out: Monday, October 12, 2015

Due: Monday, October 19, 2015 at 600pm local time

The goal of this problem set is to help you design functions 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. (The absent-minded professors, part 2). Reimplement the last problem from last week's problem set (class-lists.rkt), but using HOFs wherever possible and appropriate. Be sure to provide make-slip, slip-color, slip-name1 and slip-name2, which I forgot to specify in PS04. Use the filename class-lists.rkt, as you did before.
  2. (screensaver-5). Rewrite screensaver-4 to use higher-order functions whenever possible instead of using recursions down a list. Provide the same functions you did for screensaver-4. Name your file screensaver-5.rkt .

  3. The Registrar has heard about your excellent work with the absent-minded professors and so he asks you to solve the following problem:

    You are given a list of (student, class) pairs. Deliver a file called rosters.rkt that produces the class roster for each class that has at least one student enrolled. Here are more detailed specifications:

    A SetOfX is a list of X's without duplication.  Two SetOfX's are
    considered equal if they have the same members.
    Example: (list (list 1 2) (list 2 1)) is NOT a SetOfSetOfNumber,
    because (list 1 2) and (list 2 1) represent the same set of numbers. 
    An Enrollment is a (make-enrollment Student Class)
    (make-enrollment s c) represents the assertion that student s is
    enrolled in class c.
    A ClassRoster is a (make-roster Class SetOfStudent)
    (make-roster c ss) represents that the students in class c are exactly
    the students in set ss.
    Student is unspecified, but you may assume that students may be
    compared for equality with equal?
    Class is unspecified, but you may assume that classes may be
    compared for equality with equal?
    Two ClassRosters are equal if they have the same class and equal
    sets of students.  
    You are to provide the following functions:
    roster=? : ClassRoster ClassRoster -> Boolean
    RETURNS: true iff the two arguments represent the same roster
    rosterset=? : SetOfClassRoster SetOfClassRoster -> Boolean
    RETURNS: true iff the two arguments represent the same set of rosters
    enrollments-to-rosters: SetOfEnrollment -> SetOfClassRoster
    GIVEN: a set of enrollments
    RETURNS: the set of class rosters for the given enrollments
        (list (make-enrollment "John" "PDP")
              (make-enrollment "Kathryn" "Networks")
              (make-enrollment "Feng" "PDP")
              (make-enrollment "Amy" "PDP")
              (make-enrollment "Amy" "Networks")))
       (make-roster "PDP" (list "John" "Feng" "Amy"))
       (make-roster "Networks" (list "Kathryn" "Amy")))
    In the output, the classes may be in any order, and the students in
    each class may be in any order.

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

    For your tests, you may use any data type for Student and Class. However, your code should not depend on your choice of data type; that is, it should work for any definition of Student and Class (so long as each is testable using equal?, as specified above).

    Be sure that your tests accept any correct answer, not just the one that your function happens to produce. (Hint: don't use check-equal?; instead use check with an appropriate equality test.)

Last modified: Thu Oct 15 10:48:51 Eastern Daylight Time 2015