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

Out: Monday, October 10, 2016

Due: Monday, October 17, 2016 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. Use the filename q1.rkt.
  2. (The nervous registrar) The Registrar has heard about your excellent work with the absent-minded professors and so he asks you to help him solve the following problem:

    He needed a program to take a list of (student, class) pairs, and produce a list of class rosters, one roster for each class that has at least one student enrolled (detailed specifications below). He hired several teams of Racket programmers who had never taken PDP, and therefore produced solutions that were late and over-budget. Now he needs your help to test their solutions.

    You are to design a tester that will accept any good solution to the registrar's original problem, and reject any incorrect solution. Your solution should be in the form of a file called q2.rkt. Here are more detailed specifications:

    An EnrollmentAssertion is a (make-enrollment Student Class).
    (make-enrollment s c) represents the assertion that student s is
    enrolled in class c.
    A ClassRosterAssertion is a (make-roster Class SetOfStudent).
    (make-roster c ss) represents the assertion 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? (Among other things, this means that
    we don't have to worry about the first name/last name problems that
    Professors Shivers and Felleisen had; the Registrar knows the student
    name exactly)
    Class is unspecified, but you may assume that classes may be
    compared for equality with equal?
    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).
    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. 
    A ProposedSolution is a function with contract
    SetOfEnrollmentAssertion -> SetOfClassRosterAssertion
    that is, it is a function that takes a SetOfEnrollmentAssertion and
    produces a SetOfClassRosterAssertion
    If soln1 is a ProposedSolution, we might have
        (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")))
    This is an example of correct behavior by a ProposedSolution.
    In the output of a correct ProposedSolution, the classes may be in any
    order, and the students in each class may be in any order, but there
    must be no duplication of classes and no duplication of students
    within a class.
    You are to provide the following functions:
    behavior-correct? : ProposedSolution SetOfEnrollmentAssertion -> Boolean
    GIVEN: a ProposedSolution soln-fn and a SetOfEnrollmentAssertion se
    RETURNS: true iff the output of soln-fn on se is an example of correct
    behavior by a ProposedSolution.
    EXAMPLE: See example above
    enrollments-to-rosters: SetOfEnrollmentAssertion -> SetOfClassRoster
    GIVEN: a set of enrollments
    RETURNS: a correct set of class rosters for the given enrollments
    enrollments-to-rosters-bad-1: SetOfEnrollmentAssertion -> SetOfClassRoster
    enrollments-to-rosters-bad-2: SetOfEnrollmentAssertion -> SetOfClassRoster
    enrollments-to-rosters-bad-3: SetOfEnrollmentAssertion -> SetOfClassRoster
    GIVEN: a set of enrollment assertions
    RETURN: an incorrect set of class rosters for the given enrollments.
    The three functions should return DIFFERENT incorrect sets of class

    Test your behavior-correct? function by writing a correct enrollments-to-rosters function and several incorrect ones (the 3 shown above are just a start).

    The problem requires that your solution work for any choice of representation of Student and Class, so long as they are testable for equality using equal?, so you should also test your solution using at least two different data types for Student and Class. You may assume that any ProposedSolution also works for any such choice of data types.

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

    You will find this problem much easier if you follow the slogan "The Structure of the Program Follows the Structure of the Data". To help you with this concept, please turn in a file illustrating the call graph for your program. This file must contain a diagram showing which functions call which, so we (and you) can see the overall structure of your program. You may turn this in as a text file, pdf, jpg, or Racket file. Call your file call-tree with an appropriate suffix, and bring a paper copy to your codewalk.

Last modified: Tue Oct 11 10:28:12 Eastern Daylight Time 2016