Home Assignments Lecture Blog Resources Project Discussion Group

91.301 Organization of Programming Languages
Prof. F. Martin

Out: Feb 18, 2011
Due: Feb 23, 2011

Problem Set 3.5: More with Map, Filter, and Accumulate/Reduce

Scheme Settings

You should define nil as follows in your evaluation buffer: (define nil '())

What to turn in

  • Keep your answers in a file named ps3.5-ans.rkt.
  • Put your name at the top of the file in a comment block.
  • Put the code for each problem sequentially in the definitions buffer.
  • Put the problem number in a comment before the code for that problem (use a semi-colon to make a line a comment). Underneath the code for each problem, cut and paste the appropriate sample runs. You can put semi-colons in front of the sample runs, which will comment them out and allow you to load the entire buffer in another session.
  • If you have any hand-written content, turn it in at the beginning of class on the due date. Submit code electronically.
  • Submit your answer buffer using the submit command on the cluster: submit fredm 301-ps3.5 ps3.5-ans.rkt


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 define 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.