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.
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
reduce) as much as reasonable.
all-titlesthat consumes an inventory and produces a list of all titles in the inventory.
titles-in-stockthat consumes an inventory and produces a list of all titles in the inventory with at least 1 copy in stock.
restockthat 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).
titles-bythat consumes an artist name and inventory and produces a list of titles of CDs by that artist.
copies-in-stockthat 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.
blues-salethat consumes an inventory and produces an inventory in which all blues CDs are discounted by 10%.
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))
tree-manipthat will count the number of leaves in the tree, evaluating to 7 for
(tree-manip test-tree<param1> <param2> <param3>). (Figure out the three parameters.)
tree-manipthat will add the values of the leaves in the tree, evaluating to 28 for
tree-manipthat will triple each of the values in
test-tree, evaluating to
(3 (6 (9 (12) 15) 18) 21).
3. Using flip, negate, and compose.
compose, as they are defined on this page.
consfunction and a flipped
odd?in terms of
4. SICP exercise 2.38 (pp. 121), introducing
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))