CS 5010: Problem Set 4

Out: Monday, October 6, 2014

Due: Monday, October 13, 2014 at 600pm local time

The goal of this problem set is to help you design functions using higher-order functional composition with lists.

In this problem set, you will redo the two questions from problem set 3 using higher-order function composition (that is map, foldr, filter, etc.) whenever possible. This should be easy, so to keep you on your toes, I've added a few new or changed requirements. These are marked in red.

In fact, I believe that every structural decomposition on lists in these problems can be replaced by a higher-order function composition.

Hint: get your existing program going with HOFC everywhere before starting on the new requirements.

Remember that you must follow the design recipe. Your deliverables include the data analysis (including template), contract and purpose header, examples, design strategy, code, and tests. You must also include your laboratory notebook.

As you did before, download a copy of extras.rkt and put it in the folder with your solutions. Download any other files that are needed for each problem. Put necessary provide and require directives at the top of your file, as you did before.

As usual, the rubric for grading is here.

UPDATE: I've put out a document with some more detailed guidelines for the TAs grading your solutions. I've been over this in detail with the TA's, so they should be following it. You can find it here.

Required Exercises

  1. Design a program called inventory.rkt, containing a set of functions for manipulating the inventory of a bookstore, represented as a list of books. For each book, we must maintain the following information:

    The inventory satisfies the invariant that there are no duplicates: any isbn appears at most once in the inventory.In this problem set, we don't provide any way to add or remove books (ISBNs) from the inventory, although we do model changing the number of copies of an ISBN that are currently in stock.

    You also need to deal with orders. An order is a list of line items. A line item consists of an ISBN and the quantity ordered. The quantity ordered is always a positive integer. Here is an example of an order; each line of the table is a line item. Here is an example of how an order might be displayed as a table.

    45861387 3
    19968208 15
    30581274 10

    Like the inventory, an order will contain no duplicate line items: any isbn will occur at most once in an order.

    Also, for this problem, we introduce the Data Definition MaybeInteger

    ;; A MaybeInteger is one of:
    ;; -- Integer
    ;; -- false

    Design the following functions.

    All functions that return an inventory should return an inventory with the books in the same order they were in the argument.

    Your solution should provide the following functions:

    inventory-potential-profit : Inventory ->  Integer
    GIVEN: an inventory
    RETURNS: the total profit, in USD*100,for all the items in stock (i.e., how much
    the bookstore would profit if it sold every book in the inventory).
    inventory-total-volume : Inventory -> Real
    GIVEN: An inventory
    RETURNS: the total volume needed to store all the books in the inventory.
    price-for-line-item : Inventory LineItem -> MaybeInteger
    GIVEN: an inventory and a line item
    RETURNS: the price for that line item (the quantity times the unit
    price for that item).  Returns false if that isbn does not exist in
    the inventory. 
    fillable-now? : Order Inventory -> Boolean.
    GIVEN: an order and an inventory
    RETURNS: true iff there are enough copies of each book on hand to fill
    the order.  If the order contains a book that is not in the inventory,
    then the order is not fillable.
    days-til-fillable : Order Inventory -> MaybeInteger
    GIVEN: an order and an inventory
    RETURNS: the number of days until the order is fillable, assuming all
    the shipments come in on time.  Returns false if there won't be enough
    copies of some book, even after the next shipment of that book comes
    EXAMPLES: if the order contains one book that is out of stock, with a
    reorder status showing 2 days until delivery, then the order is
    fillable in 2 days.  If the order is for 10 copies of the book, and
    the next order consists of only 5 books, then the function should return false.
    price-for-order : Inventory Order -> NonNegInteger
    RETURNS: the total price for the given order, in USD*100.  The price does not
    depend on whether any particular line item is in stock.  Line items
    for an ISBN that is not in the inventory count as 0.
    inventory-after-order : Inventory Order -> Inventory.
    GIVEN: an inventory and an order
    WHERE: the order is fillable now
    RETURNS: the inventory after the order has been filled.
    increase-prices : Inventory String Real -> Inventory
    GIVEN: an inventory, a publisher, and a percentage,
    RETURNS: an inventory like the original, except that all items by that
    publisher have their unit prices increased by the specified
    percentage. If the increased price is a non-integer, it may be either
    raised to the next integer price, or truncated to the next lowest
    integer price in USD*100.
    EXAMPLE: (increase-prices inventory1 "MIT Press" 10)
    returns an inventory like the original, except that all MIT Press
    books in the inventory have had their prices increased by 10%.
    Also provide the functions:
    make-book  (9 arguments)
    make-line-item (2 arguments)
    The arguments to these functions should appear in the same order as
    they do in the problem statement.
    reorder-present? : ReorderStatus -> Boolean
    RETURNS: true iff the given ReorderStatus shows a pending re-order.
    make-empty-reorder : Any -> ReorderStatus
    Ignores its argument
    RETURNS: a ReorderStatus showing no pending re-order. 
    make-reorder : PosInt PosInt -> ReorderStatus
    GIVEN: a number of days and a number of copies
    RETURNS: a ReorderStatus with the given data.

    Rewrite these functions using map, foldr, filter, etc.

    Every night, the bookstore puts on its shelves the reorders that have come in from the publisher. We assume that all reorders arrive on time. Thus, if we had a book with a reorder due in one day, we assume those books have arrived and will be available for sale the next morning. The due dates for all other reorders should be decremented to represent the fact that we are now one day closer to having them arrive. To keep track of all this, the bookstore uses a function

    inventory-after-deliveries : Inventory -> Inventory
    GIVEN: today's inventory
    RETURNS: an Inventory representing tomorrow's inventory, in which all
    reorders that were due in 1 day are now available, and all other
    reorders have their expected times decreased by 1.  
    Write and provide this function. Use HOFC throughout.

    Before you turn in your solution, make sure it passes the tests in ps04-inventory-qualification.rkt.

  2. (Balls in a Box). Write a program called balls-in-box.rkt that meets the following requirements:

    Your program should provide the following functions:

    run : PosInt PosReal -> World
    GIVEN: a ball speed and a frame rate, in secs/tick.
    EFFECT: runs the world.
    RETURNS: the final state of the world.
    EXAMPLE: (run 8 .25) creates and runs a world in
    which each ball travels at 8 pixels per tick and
    each tick is 0.25 secs.
    initial-world : PosInt  -> World
    GIVEN: a ball speed
    RETURNS: a world with no balls, but with the
    property that any balls created in that world
    will travel at the given speed.
    world-after-tick : World -> World
    RETURNS: the world that should follow the given world after a tick.
    world-after-key-event : World KeyEvent -> World
    RETURNS: the world that should follow the given world after the given
    key event.
    world-after-mouse-event : World Integer Integer MouseEvent -> World
    RETURNS: the world that should follow the given world after the given
    mouse event.
    world-balls : World -> ListOf<Ball>
    GIVEN: a world,
    RETURNS: the list of balls that are in the box.
    ball-x-pos : Ball -> Integer Real
    ball-y-pos : Ball -> Integer Real
    GIVEN: a ball
    RETURNS: the x or y position of its center
    ball-selected? : Ball -> Boolean
    GIVEN: a ball
    RETURNS: true if and only if it is currently selected

    Note: if any of these functions are implemented as selectors on structs, then you don't need to provide the design recipe deliverables for them.

    If any function is just a renaming of a selector, for example

    (define-struct ball (x y ...))
    (define (ball-x-pos b)
      (ball-x b))
    then you need to deliver a contract and purpose statement, but you don't need examples, strategy, or tests.

    As in the preceding question, you should solve this problem by replacing every structural decomposition on a list by an appropriate map, foldr, filter, etc.

    Before you turn in your solution, make sure it passes the tests in ps04-balls-in-box-qualification.rkt. As before, download this file, save it in your set04 directory, and run it to qualify your program for grading. Be sure to commit this file to your repository so we know that you've done this correctly.

Last modified: Sat Oct 11 16:52:20 Eastern Daylight Time 2014