PS4

Home Assignments Lecture Blog Resources Project Discussion Group

Problem Set 4: Using Map/Filter/Reduce, and Trees

In this assignment, we use map/filter/reduce for a “practical” application, work with trees, learn about fold, and use fold to solve a list manipulation challenge.

Here is a direct link to the assignment files: improved cddb version
old version

Problems

1. Assume that we want to develop an inventory database for an online CD store. For each CD, the database stores its title, artist, price, how many copies are in stock, and its category of music (such as rock, blues, or country). Write a data definition for CD inventories. When completing the following exercises, please make sure to use map, filter, and accumulate (aka, reduce) as much as reasonable.

1a. Create a constructor procedure with parameters, title, artist, price, category, and units-in-stock, and corresponding accessors to retrieve these fields.

1b. Populate an inventory (i.e., a list) with 10 or so records created from your constructor.

1c. Write a procedure all-titles that consumes an inventory and produces a list of all titles in the inventory.

1d. Write a procedure titles-in-stock that consumes an inventory and produces a list of all titles in the inventory with at least 1 copy in stock.

1e. Write a procedure restock that consumes a CD title, number of new copies of that CD and an inventory and produces an inventory in which the named CD has the given number of additional copies (and all other CDs remain the same).

1f. Write a procedure titles-by that consumes an artist name and inventory and produces a list of titles of CDs by that artist.

1g. Write a procedure copies-in-stock that consumes a CD title, artist name and an inventory and produces the number of copies of that item that are in stock. Return 0 if the named CD isn't in the inventory.

1h. Write a procedure blues-sale that consumes an inventory and produces an inventory in which all blues CDs are discounted by 10%.

1i. Write a procedure carry-cd? that consumes a title and artist name and produces a boolean indicating whether that item is in the inventory (whether in or out of stock).

This problem is courtesy of a lab exercise from WPI's Scheme course.

2. Consider the following procedure for operating on trees:

(define (tree-manip tree init leaf accum) 
  (cond ((null? tree) init) 
        ((not (pair? tree)) (leaf tree)) 
        (else (accum  
               (tree-manip (car tree) init leaf accum) 
               (tree-manip (cdr tree) init leaf accum)))))

Suppose that we provide a test tree, (define test-tree '(1 (2 (3 (4) 5) 6) 7))

2a. Write the parameters to tree-manip that will count the number of leaves in the tree, evaluating to 7 for test-tree; e.g.: (tree-manip test-tree <param1> <param2> <param3>). (Figure out the three parameters.)

2b. Write the parameters to tree-manip that will add the values of the leaves in the tree, evaluating to 28 for test-tree.

2c. Write the parameters to tree-manip that will triple each of the values in test-tree, evaluating to (3 (6 (9 (12) 15) 18) 21).

3. Using flip, negate, and compose.

3a. Define and play with the functions flip, negate, and compose, as they are defined on this page.

3b. Define, for instance, a flipped cons function and a flipped minus function.

3c. Define the function odd? in terms of even? and negate.

4. SICP exercise 2.38 (pp. 121), introducing fold-right and fold-left.

5. Use fold-right to deﬁne the function bucket. It consumes a list of numbers, and returns a list of sublists of adjacent equal numbers. For example:

(bucket '(1 1 2 2 2 3 1 1 1 2 3 3)) –>

'((1 1) (2 2 2) (3) (1 1 1) (2) (3 3))

Thanks to UC Santa Cruz for this one.