Lists that Contain Structures

The representation of an inventory as a list of symbols or a list of prices is naive. A sales clerk in a toy store needs to know not only the name of the toy, but also its price, and possibly other attributes like warehouse availability, delivery time, or even a picture of the item. Similarly, representing a the personnel's work week as a list of hours is a bad choice. Even the printing of a paycheck requires more information about the employee than the hours worked per week.

Fortunately, the items of lists do not have to be atomic values. Lists may contain whatever values we want, especially structures. Let's try to make our toy store inventory functions more realistic. We start with the structure and the data definition of a class of inventory records:

(define-struct ir (name price))

An inventory-record (short: ir) is a structure: (make-ir s n) where s is a symbol and n is a (positive) number.

Most important, we can define a class of lists that represent inventories much more realistically:

An inventory is either empty or (cons ir inv) where ir is an inventory record and inv is an inventory.

While the shape of the list definition is the same as before, its components are defined in a separate data definition. Since this is our first such data definition, we should make up some examples before we proceed.

The simplest example of an inventory is empty. To create a larger inventory, we must create an inventory record and cons it onto another inventory:

(cons (make-ir 'doll 17.95)
  empty) 

(cons (make-ir 'robot 22.05)
  (cons (make-ir 'doll 17.95) 
    empty)) 

Now we can adapt our inventory-processing functions. First look at sum, the function that consumes an inventory and produces its total value. Here is a restatement of the basic information about the function:

;; sum : inventory -> number
;; to compute the sum of prices on an-inv 
(define (sum an-inv) ...) 

Since the data definition of inventories is basically that of lists, we can again start from the template for list-processing functions:

(define (sum an-inv)
  (cond 
    [(empty? an-inv) ...] 
    [else ... (first an-inv) ... (sum (rest an-inv)) ...])) 

For the definition of the function body, we consider each cond-line in isolation. First, if (empty? an-inv) is true, sum is supposed to produce 0. Hence the answer expression in the first cond-line is obviously 0.

(define (sum an-inv) (cond [(empty? an-inv) 0] [else (+ (ir-price (first an-inv)) (sum (rest an-inv)))])) Figure: Computing the value of an inventory

Second, if (empty? an-inv) is false, in other words, if sum is applied to a constructed inventory, the recipe requires us to understand the purpose of two expressions:

1. (first an-inv), which extracts the first item of the list; and
2. (sum (rest an-inv)), which extracts the rest of an-inv and then computes its cost with sum.

(+ (ir-price (first an-inv))
   (sum (rest an-inv))) 

Exercise 10.2.1

Adapt the function contains-doll? so that it consumes inventories instead of lists of symbols:

;; contains-doll? : inventory -> boolean
;; to determine whether an-inv contains a record for 'doll 
(define (contains-doll? an-inv) ...) 

Also adapt the function contains?, which consumes a symbol and an inventory and determines whether an inventory record with this symbol occurs in the inventory:

;; contains? : symbol inventory -> boolean
;; to determine whether inventory contains a record for asymbol 
(define (contains? asymbol an-inv) ...) 

Item Price Image robot 29.95 robot 29.95 robot 29.95 Figure: A table of toys

Exercise 10.2.2

Provide a data definition and a structure definition for an inventory that includes pictures with each objects. Show how to represent the inventory listing in figure .

Develop the function show-picture. The function consumes a symbol, the name of a toy, and one of the new inventories. It produces the picture of the named toy or false if the desired item is not in the inventory. Pictures of toys are available on the Web. Solution

Exercise 10.2.3

Develop the function price-of, which consumes the name of a toy and an inventory and produces the toy's price. Solution

Exercise 10.2.4

A phone directory combines names with phone numbers. Develop a data definition for phone records and directories. Using this data definition develop the functions

1. whose-number, which determines the name that goes with some given phone number and phone directory, and
2. phone-number, which determines the phone number that goes with some given name and phone directory.

Suppose a business wishes to separate all those items that sell for a dollar or less from all others. The goal might be to sell these items in a separate department of the store. To perform this split, the business also needs a function that can extract these items from its inventory listing, that is, a function that produces a list of structures.

Let us name the function extract1 because it creates an inventory from all those inventory records whose price item is less than or equal to 1.00. The function consumes an inventory and produces one with items of appropriate prices. Thus the contract for extract1 is easy to formulate:

;; extract1 : inventory -> inventory
;; to create an inventory from an-inv for all 
;; those items that cost less than $1 
(define (extract1 an-inv) ...) 

We can reuse our old inventory examples to make examples of extract1's input-output relationship. Unfortunately, for these three examples it must produce the empty inventory, because all prices are above one dollar. For a more interesting input-output example, we need an inventory with more variety:

(cons (make-ir 'dagger .95)
      (cons (make-ir 'Barbie 17.95) 
            (cons (make-ir 'key-chain .55) 
                  (cons (make-ir 'robot 22.05) 
                        empty)))) 

(cons (make-ir 'dagger .95)
      (cons (make-ir 'key-chain .55) 
            empty)) 

The contract also implies that the template for extract1 is identical to that of sum, except for a name change:

(define (extract1 an-inv)
  (cond 
    [(empty? an-inv) ...] 
    [else ... (first an-inv) ... (extract1 (rest an-inv)) ...])) 

;; extract1 : inventory -> inventory ;; to create an inventory from an-inv for all ;; those items that cost less than $1 (define (extract1 an-inv) (cond [(empty? an-inv) empty] [else (cond [(<= (ir-price (first an-inv)) 1.00) (cons (first an-inv) (extract1 (rest an-inv)))] [else (extract1 (rest an-inv))])])) Figure: Extracting dollar items from an inventory

For the definition of the function body, we again analyze each case separately. First, if (empty? an-inv) is true, then the answer is clearly empty, because no item in an empty store costs less than one dollar. Second, if the inventory is not empty, we first determine what the expressions in the matching cond-clause compute. Since extract1 is the first recursive function to produce a list of structures, let us look at our interesting example:

(cons (make-ir 'dagger .95)
      (cons (make-ir 'Barbie 17.95) 
            (cons (make-ir 'key-chain .55) 
                  (cons (make-ir 'robot 22.05) 
                        empty)))) 

(first an-inv) = (make-ir 'dagger .95)

(rest an-inv) = (cons (make-ir 'Barbie 17.95) 
                     (cons (make-ir 'key-chain .55) 
                           (cons (make-ir 'robot 22.05) 
                             empty))) 

(extract1 (rest an-inv)) = (cons (make-ir 'key-chain .55)
                             empty) 

To produce an appropriate inventory for all of an-inv, we must decide what to do with the first item. Its price may be more or less than one dollar, which suggests the following template for the second answer:

... (cond 
      [(<= (ir-price (first an-inv)) 1.00) ...] 
      [else ...]) ... 

Exercise 10.2.5

Define the function extract>1, which consumes an inventory and creates an inventory from those records whose prices are above one dollar. Solution

Exercise 10.2.6

Develop a precise data definition for inventory1, which are inventory listings of one-dollar stores. Using the new data definition, the contract for extract1 can be refined:

;; extract1 : inventory -> inventory1
(define (extract1 an-inv) ...) 

Exercise 10.2.7

Develop the function raise-prices, which consumes an inventory and produces an inventory in which all prices are raised by 5%. Solution

Exercise 10.2.8

Adapt the function recall from exercise  for the new data definition of inventory. The function consumes the name of a toy ty and an inventory and produces an inventory that contains all items of the input with the exception of those labeled ty. Solution

Exercise 10.2.9

Adapt the function name-robot from exercise  for the new data definition of inventory. The function consumes an inventory and produces an inventory with more accurate names. Specifically, it replaces all occurrences of 'robot with 'r2d3.

Generalize name-robot to the function substitute. The new function consumes two symbols, called new and old, and an inventory. It produces a new inventory by substituting all occurrences of old with new and leaving all others alone. Solution