CS 1102 (A12): Lab 3

To get your participation credit, make sure you
(This work will not be graded---full credit just for submitting.)

Lab Motivation and Goals

By the end of this lab, you should be able to:
• Use `map` and `filter`, Racket's loops
• Write your own iterators over trees

You need to use Intermediate Student with Lambda language level for this lab!

Exercises with Map and Filter

Put your name in a comment at the top of the Definitions area.

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.

Write each of the following functions using `filter` and/or `map`, or argue why it cannot be written using these (in which case you do not need to write the function).

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

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

3. Write a function `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).

4. Write a function `total-stock` that consumes an inventory and produces the total number of copies of CDs that are in stock.

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

6. Write a function `blues-sale` that consumes an inventory and produces an inventory in which all blues CDs are discounted by 10\%.

7. Write a function `carry-cd?` that consumes an inventory, a CD title and artist name, and produces a boolean indicating whether that item is in the inventory (whether in or out of stock).

Everybody should be able to finish up to this point.

Exercises with Iterators on Trees

For these exercises, we will work with the following data definition for binary trees (notice that the contract for `node` appears inside the contract for `bintree`):

```   ;; A bintree[alpha] is either
;;  - false, or
;;  - (make-node alpha bintree bintree)
(define-struct node (item left right))
```
1. Write the template for functions over bintrees. You can check for false using `boolean?`.

2. Write a function `sign-tree` that consumes a bintree[number] (i.e., a bintree where the items at each node are numbers) and returns a bintree[symbol] with the same structure as the input tree, but with each number replaced with one of the symbols 'positive, 'negative, or 'zero, as appropriate.

3. Write a function `flip-tree` that consumes a bintree[posn] and returns a bintree[posn]. The returned tree should have the same structure as the input tree, but each posn should have its x- and y-coordinates flipped, i.e., `(make-posn 3 4)` would become `(make-posn 4 3)`.

Recall that (define-struct posn (x y)) is built into DrRacket.

4. The functions `sign-tree` and `flip-tree` have a similar structure. Write a function `tree-map` that takes a bintree and a function and applies the function to each node in the tree. Show how to implement `sign-tree` and `flip-tree` using `tree-map`. Be sure to include a correct contract for `tree-map`.

5. Write a function `tree-andmap` that consumes a function of type (alpha -> boolean) and a bintree[alpha] and returns a boolean indicating whether the given function returned true at every node. Can you implement `tree-andmap` using a simple call to `tree-map`? By "a simple call", I mean can you just fill in the ... in the code below to implement this function? If not, why not?

```(define (tree-andmap func abt)
(tree-map ...))
```

Note: to check whether a value is `false`, you can use

`(and (boolean? value) (not value))`

Using `tree-andmap`, implement `pos-tree?` that consumes a bintree[number] and determines whether all numbers in the tree are positive.