Section 9

Compound Data, Part 2: Lists

Structures are one way to represent compound information. They are useful when we know how many pieces of data we wish to combine. In many cases, however, we don't know how many things we wish to enumerate, and in that case we form a list. A list can be of arbitrary length, that is, it contains a finite, but undetermined number of pieces of data.

Forming lists is something that all of us do. Before we go grocery shopping, we often write down a list of items that we want to purchase. When we plan out a day in the morning, we write down a list of things to do. During December, many children prepare Christmas wish lists. To plan a party, we list the people we want to invite. In short, arranging information in the form of lists is a ubiquitous part of our life, and we should learn to represent lists as Scheme data. In this section, we first learn to create lists and then move on to developing functions that consume lists.

9.1  Lists

When we form a list, we always start out with the empty list. In Scheme,

empty

represents the empty list. From here, we can construct a longer list with the operation cons. Here is a simple example:

(cons 'Mercury empty) 

In this example, we constructed a list from the empty list and the symbol 'Mercury. Figure 25 presents this list in the same pictorial manner we used for structures. The box for cons has two fields: first and rest. In this specific example the first field contains 'Mercury and the rest field contains empty.

Once we have a list with one item on it, we can construct lists with two items by using cons again:

(cons 'Venus (cons 'Mercury empty))

The middle row of figure 25 shows how we should imagine the second list. It is also a box of two fields, but this time the rest field contains a box. Indeed, it contains the box from the top row of the same figure.

Finally, we construct a list with three items:

(cons 'Earth (cons 'Venus (cons 'Mercury empty)))

The last row of figure 25 illustrates the list with three items. Its rest field contains a box that contains a box again. So, as we create lists we put boxes into boxes into boxes, etc. While this may appear strange at first glance, it is just like a set of Chinese gift boxes or a set of nested drinking cups, which we sometimes get for our early birthdays. The only difference is that Scheme programs can nest lists much deeper than any artist could nest physical boxes.

Exercise 9.1.1.   Create Scheme lists that represent

1. the list of all planets in our solar system;

2. the following meal: steak, pommes-frites, beans, bread, water, juice, brie-cheese, and ice-cream; and

3. the list of basic colors.

Sketch box representations of these lists, similar to those in figure 25.    Solution

We can also make lists of numbers. As before, empty is the list without any items. Here is a list with 10 numbers:

(cons 0
  (cons 1
    (cons 2
      (cons 3
        (cons 4
          (cons 5
            (cons 6
              (cons 7
                (cons 8
                  (cons 9 empty))))))))))

To build it requires 10 list constructions and one empty list.

In general a list does not have to contain values of one kind, but may contain arbitrary values:

(cons 'RobbyRound
  (cons 3 
    (cons true
      empty)))

Here the first item is a symbol, the second one is a number, and the last one a boolean. We could think of this list as the representation of a personnel record that includes the name of the employee, the number of years spent at the company, and whether the employee has health insurance through the company plan.

Now suppose we are given a list of numbers. One thing we might wish to do is add up the numbers on the list. To make this more concrete, let us assume that we are only interested in lists of three numbers:

A list-of-3-numbers is

We write down the contract, purpose, header, and examples as before:

;; add-up-3 : list-of-3-numbers  ->  number
;; to add up the three numbers in a-list-of-3-numbers
;; examples and tests: 
;;   (= (add-up-3 (cons 2 (cons 1 (cons 3 empty)))) 6)
;;   (= (add-up-3 (cons 0 (cons 1 (cons 0 empty)))) 1)
(define (add-up-3 a-list-of-3-numbers) ...)

To define the body, however, presents a problem. A constructed list is like a structure. Hence we should layout a template with selector expressions next. Unfortunately, we don't know how to select items from a list.

In analogy to structure selectors, Scheme implements operations for extracting the fields from a constructed list: first and rest.²⁹ The first operation extracts the item that we used to construct a list; the rest operation extracts the list field.

To describe how first, rest, and cons are related, we can use equations that are similar to the equations that govern addition and subtraction and structure creation and field extraction:

  (first (cons 10 empty))
= 10

  (rest (cons 10 empty))
= empty

  (first (rest (cons 10 (cons 22 empty))))
= (first (cons 22 empty))
= 22

The last one demonstrates how to evaluate nested expressions. The key is to think of (cons a-value a-list) as a value. And, as always, we start with the evaluation of the innermost parenthesized expressions that can be reduced, just as in arithmetic. In the above calculations, the expressions that are about to be reduced next are underlined.

Using first and rest we can now write down a template for add-up-3:

;; add-up-3 : list-of-3-numbers  ->  number
;; to add up the three numbers in a-list-of-3-numbers
(define (add-up-3 a-list-of-3-numbers) 
  ... (first a-list-of-3-numbers) ... 
  ... (first (rest a-list-of-3-numbers)) ...
  ... (first (rest (rest a-list-of-3-numbers))) ... )

The three expressions remind us that the input, called a-list-of-3-numbers, contains three components and how to extract them.

Exercise 9.1.2.   Let l be the list

(cons 10 (cons 20 (cons 5 empty)))

What are the values of the following expressions?

1. (rest l)

2. (first (rest l))

3. (rest (rest l))

4. (first (rest (rest l)))

5. (rest (rest (rest l)))    Solution

Exercise 9.1.3.   Finish the development of add-up-3, that is, define the body and test the complete function on some examples.

A list of three numbers is one possible representation for 3-dimensional points. The distance of a 3-dimensional point to the origin of the coordinate grid is computed in the same manner as that of 2-dimensional point: by squaring the numbers, adding them up, and taking the square root.

Use the template for add-up-3 to develop distance-to-0-for-3, which computes the distance of a 3-dimensional point to the origin.    Solution

Exercise 9.1.4.   Provide a data definition for lists of two symbols. Then develop the function contains-2-doll?, which consumes a list of two symbols and determines whether one of them is 'doll.    Solution

On the Precise Relationship between Cons and Structures: The discussion of cons, first, and rest suggests that cons creates a structure and first and rest are ordinary selectors:

(define-struct pair (left right))

(define (our-cons a-value a-list) (make-pair a-value a-list))

(define (our-first a-pair) (pair-left a-pair))

(define (our-rest a-pair) (pair-right a-pair))

(define (our-cons? x) (pair? x))

Although these definitions are a good first approximation, they are inaccurate in one important point. DrScheme's version of cons is really a checked version of make-pair. Specifically, the cons operation ensures that the right field is always a list, that is, constructed or empty. This suggests the following refinement:

(define (our-cons a-value a-list)
  (cond
    [(empty? a-list) (make-pair a-value a-list)]
    [(our-cons? a-list) (make-pair a-value a-list)]
    [else (error 'our-cons "list as second argument expected")]))

The definitions for our-first, our-rest, and our-cons? remain the same. Finally, we must also promise not to use make-pair directly so that we don't accidentally build a bad list. 

9.2  Data Definitions for Lists of Arbitrary Length

first, rest

Suppose we wish to represent the inventory of a toy store that sells such things as dolls, make-up sets, clowns, bows, arrows, and soccer balls. To make an inventory, a store owner would start with an empty sheet of paper and slowly write down the names of the toys on the various shelves.

Representing a list of toys in Scheme is straightforward. We can simply use Scheme's symbols for toys and then construct lists from them. Here are a few short samples:

empty
(cons 'ball empty)
(cons 'arrow (cons 'ball empty))
(cons 'clown empty)
(cons 'bow (cons 'arrow empty))
(cons 'clown (cons 'doll (cons 'arrow (cons 'ball empty))))

For a real store, the list will contain many more items, and the list will grow and shrink over time. In any case, we cannot say in advance how many items these inventory lists will contain. Hence, if we wish to develop a function that consumes such lists, we cannot simply say that the input is a list with either one, two, three, or four items. We must be prepared to think about lists of arbitrary length.

In other words, we need a data definition that precisely describes the class of lists that contain an arbitrary number of symbols. Unfortunately, the data definitions we have seen so far can only describe classes of data where each item is of a fixed size, such as a structure with a specific number of components or a list with a specific number of items. So how can we describe a class of lists of arbitrary size?

Looking back we see that all our examples fall into one of two categories. The store owner starts with an empty list and constructs longer and longer lists. The construction proceeds by constructing together a toy and another list of toys. Here is a data definition that reflects this process:

A list-of-symbols is either

1. the empty list, empty, or

2. (cons s los) where s is a symbol and los is a list of symbols.

This definition is unlike any of the definitions we have seen so far or that we encounter in high school English or mathematics. Those definitions explain a new idea in terms of old, well-understood concepts. In contrast, this definition refers to itself in the item labeled 2, which implies that it explains what a list of symbols is in terms of lists of symbols. We call such definitions SELF-REFERENTIAL or RECURSIVE.

At first glance, a definition that explains or specifies something in terms of itself does not seem to make much sense. This first impression, however, is wrong. A recursive definition, such as the one above, makes sense as long as we can construct some elements from it; the definition is correct if we can construct all intended elements.³⁰

Let's check whether our specific data definition makes sense and contains all the elements we are interested in. From the first clause we immediately know that empty is a list of symbols. From the second clause we know that we can create larger lists with cons from a symbol and a list of symbols. Thus (cons 'ball empty) is a list of symbols because we just determined that empty is one and we know that 'doll is a symbol. There is nothing special about 'doll. Any other symbol could serve equally well to form a number of one-item lists of symbols:

(cons 'make-up-set empty)
(cons 'water-gun empty)
...

Once we have lists that contain one symbol, we can use the same method to build lists with two items:

(cons 'Barbie (cons 'robot empty))
(cons 'make-up-set (cons 'water-gun empty))
(cons 'ball (cons 'arrow empty))
...

From here, it is easy to see how we can form lists that contain an arbitrary number of symbols. More important still for our problem, all possible inventories are adequately described by our data definition.

Exercise 9.2.1.   Show that all the inventory lists discussed at the beginning of this section belong to the class list-of-symbols.    Solution

Exercise 9.2.2.   Do all lists of two symbols also belong to the class list-of-symbols? Provide a concise argument.    Solution

Exercise 9.2.3.   Provide a data definition for the class of list of booleans. The class contains all arbitrarily large lists of booleans.    Solution

9.3  Processing Lists of Arbitrary Length

Unnatural Recursions

A real store will want to have a large inventory on-line, that is, put into a computer, so that an employee can quickly determine whether a toy is available or not. For simplicity, assume that we need contains-doll?, a function that checks whether the store has a 'doll. Translated into Scheme terminology, the function determines whether 'doll occurs on some list of symbols.

Because we already have a rigorous definition of contains-doll?'s input, we turn to the contract, header, and purpose statement:

;; contains-doll? : list-of-symbols  ->  boolean
;; to determine whether the symbol 'doll occurs on a-list-of-symbols
(define (contains-doll? a-list-of-symbols) ...)

Following the general design recipe, we next make up some examples that illustrate contains-doll? purpose. First, we clearly need to determine the output for the simplest input: empty. Since the list does not contain any symbol, it certainly does not contain 'doll, and the answer should be false:

(boolean=? (contains-doll? empty) 
           false)

Next, we consider lists with a single item. Here are two examples:

(boolean=? (contains-doll? (cons 'ball empty)) 
           false)

(boolean=? (contains-doll? (cons 'doll empty))
           true)

In the first case, the answer is false because the single item on the list is not 'doll; in the second case, the item is 'doll, and the answer is true. Finally, here are two more general examples, with lists of several items:

(boolean=? (contains-doll? (cons 'bow (cons 'ax (cons 'ball empty))))
           false)

(boolean=? (contains-doll? (cons 'arrow (cons 'doll (cons 'ball empty))))
           true)

Again, the answer in the first case must be false because the list does not contain 'doll, and in the second case it must be true because 'doll is one of the items on the list provided to the function.

The next step is to design a function template that matches the data definition. Since the data definition for lists of symbols has two clauses, the function's body must be a cond-expression. The cond-expression determines which of the two kinds of lists the function received: the empty list or a constructed list:

(define (contains-doll? a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) ...]
    [(cons? a-list-of-symbols) ...]))

Instead of (cons? a-list-of-symbols), we can use else in the second clause.

We can add one more hint to the template by studying each clause of the cond-expression in turn. Specifically, recall that the design recipe suggests annotating each clause with selector expressions if the corresponding class of inputs consists of compounds. In our case, we know that empty does not have compounds, so there are no components. Otherwise the list is constructed from a symbol and another list of symbols, and we remind ourselves of this fact by adding (first a-list-of-symbols) and (rest a-list-of-symbols) to the template:

(define (contains-doll? a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) ...]
    [else ... (first a-list-of-symbols) ... (rest a-list-of-symbols) ...]))

Now that we have a template based on our design recipes for mixed and compound data, we turn to the definition of the function's body, dealing with each cond-clause separately. If (empty? a-list-of-symbols) is true, the input is the empty list, in which case the function must produce the result false. In the second case, (cons? a-list-of-symbols) is true. The annotations in the template remind us that there is a first symbol and the rest of the list. So let us consider an example that falls into this category:

(cons 'arrow 
  (cons ...
      ... empty)))

The function, just like a human being, must clearly compare the first item with 'doll. In this example, the first symbol is 'arrow and not 'doll, so the comparison will yield false. If we had considered some other example instead, say,

(cons 'doll
  (cons ...
      ... empty)))

the function would determine that the first item on the input is 'doll, and would therefore respond with true. All of this implies that the second line in the cond-expression should contain another cond-expression:

(define (contains-doll? a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) false]
    [else (cond
            [(symbol=? (first a-list-of-symbols) 'doll) 
             true]
            [else
             ... (rest a-list-of-symbols) ...])]))

Furthermore, if the comparison of (first a-list-of-symbols) yields true, the function is done and produces true, too.

If the comparison yields false, we are left with another list of symbols: (rest a-list-of-symbols). Clearly, we can't know the final answer in this case, because depending on what ``...'' represents, the function must produce true or false. Put differently, if the first item is not 'doll, we need some way to check whether the rest of the list contains 'doll.

Fortunately, we have just such a function: contains-doll?, which according to its purpose statement determines whether a list contains 'doll. The purpose statement implies that if l is a list of symbols, (contains-doll? l) tells us whether l contains the symbol 'doll. Similarly, (contains-doll? (rest l)) determines whether the rest of l contains 'doll. And in the same vein, (contains-doll? (rest a-list-of-symbols)) determines whether or not 'doll is in (rest a-list-of-symbols), which is precisely what we need to know now.

Here is the complete definition of the function:

(define (contains-doll? a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) false]
    [else (cond
            [(symbol=? (first a-list-of-symbols) 'doll) true]
            [else (contains-doll? (rest a-list-of-symbols))])]))

It consumes a list of symbols and determines whether or not it is empty. If it is, the result is false. Otherwise, the list is not empty and the result of the function depends on the first item of the list. If the first item is 'doll, the result is true; if not, the function's result is the result of searching the rest of the input list -- whatever it is.

Exercise 9.3.1.   Use DrScheme to test the definition of contains-doll? on our examples:

empty
(cons 'ball empty)
(cons 'arrow (cons 'doll empty))
(cons 'bow (cons 'arrow (cons 'ball empty)))

   Solution

Exercise 9.3.2.   Another way of formulating the second cond-clause in the function contains-doll? is to understand

(contains-doll? (rest a-list-of-symbols))

as a condition that evaluates to either true or false, and to combine it appropriately with the condition

(symbol=? (first a-list-of-symbols) 'doll)

Reformulate the definition of contains-doll? according to this observation.    Solution

Exercise 9.3.3.   Develop the function contains?, which consumes a symbol and a list of symbols and determines whether or not the symbol occurs in the list.    Solution

9.4  Designing Functions for Self-Referential Data Definitions

At first glance, self-referential data definitions seem to be far more complex than those for compound or mixed data. But, as the example in the preceding subsection shows, our design recipes still work. Nevertheless, in this section we discuss a new design recipe that works better for self-referential data definitions. As implied by the preceding section, the new recipe generalizes those for compound and mixed data. The new parts concern the process of discovering when a self-referential data definition is needed, deriving a template, and defining the function body:

Data Analysis and Design:

If a problem statement discusses compound information of arbitrary size, we need a recursive or self-referential data definition. At this point, we have only seen one such class, list-of-symbols, but it is easy to imagine other, yet similar classes of lists. We will get to know many other examples in this and the following part.³¹

For a recursive data definition to be valid, it must satisfy two conditions. First, it must contain at least two clauses. Second, at least one of the clauses must not refer back to the definition. It is good practice to identify the self-references explicitly with arrows from the references in the data definition back to its beginning.

Our running example for this section are functions that consume lists of symbols:

Template:

A self-referential data definition specifies a mixed class of data, and one of the clauses should specify a subclass of compound data. Hence the design of the template can proceed according to the recipes in sections 6.5 and 7.2. Specifically, we formulate a cond-expression with as many cond-clauses as there are clauses in the data definition, match each recognizing condition to the corresponding clause in the data definition, and write down appropriate selector expressions in all cond-lines that process compound values.

In addition, we inspect each selector expression. For each that extracts a value of the same class of data as the input, we draw an arrow back to the function parameter. At the end, we must have as many arrows as we have in the data definition.

Let's return to the running example. The template for a list-processing function contains a cond-expression with two clauses and one arrow:

For simplicity, this book will use a textual alternative to arrows. Instead of drawing an arrow, the templates contain self-applications of the function to the selector expression(s):

(define (fun-for-los a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) ...]
    [else ... (first a-list-of-symbols) ...
      ... (fun-for-los (rest a-list-of-symbols)) ...]))

We refer to these self-applications as NATURAL RECURSIONS.

Body:

For the design of the body we start with those cond-lines that do not contain natural recursions. They are called BASE CASES. The corresponding answers are typically easy to formulate or are already given by the examples.

Then we deal with the self-referential cases. We start by reminding ourselves what each of the expressions in the template line computes. For the recursive application we assume that the function already works as specified in our purpose statement. The rest is then a matter of combining the various values.

Suppose we wish to define the function how-many, which determines how many symbols are on a list of symbols. Assuming we have followed the design recipe, we have the following:

;; how-many : list-of-symbols  ->  number
;; to determine how many symbols are on a-list-of-symbols
(define (how-many a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) ...]
    [else ... (first a-list-of-symbols) ... 
      ... (how-many (rest a-list-of-symbols)) ...]))

The answer for the base case is 0 because the empty list contains nothing. The two expressions in the second clause compute the first item and the number of symbols on the (rest a-list-of-symbols). To compute how many symbols there are on all of a-list-of-symbols, we just need to add 1 to the value of the latter expression:

(define (how-many a-list-of-symbols)
  (cond
    [(empty? a-list-of-symbols) 0]
    [else (+ (how-many (rest a-list-of-symbols)) 1)]))

Combining Values:

In many cases, the combination step can be expressed with Scheme's primitives, for example, +, and, or cons. If the problem statement suggests that we ask questions about the first item, we may need a nested cond-statement. Finally, in some cases, we may have to define auxiliary functions.

Figure 26 summarizes this discussion in the usual format; those design steps that we didn't discuss are performed as before. The following section discusses several examples in detail.

Phase Goal                  Activity Data   Analysis   and Design to formulate a data definition develop a data definition for mixed data with at least two alternatives one alternative must not refer to the definition explicitly identify all self-references in the data definition Contract Purpose and Header to name the function; to specify its classes of   input data and its   class of output data; to describe its purpose; to formulate a header name the function, the classes of input data, the class of output data, and specify its purpose:  ;; name : in1 in2 ...--> out  ;; to compute ... from x1 ...  (define (name x1 x2 ...) ...) Examples          to characterize the input- output relationship via examples create examples of the input-output relationship make sure there is at least one example per subclass Template to formulate an outline develop a cond-expression with one clause per alternative add selector expressions to each clause annotate the body with natural recursions TEST: the self-references in this template and the data definition match! Body                  to define the function formulate a Scheme expression for each simple cond-line explain for all other cond-clauses what each natural recursion computes according to the purpose statement Test                 to discover mistakes   (``typos'' and logic) apply the function to the inputs of the examples check that the outputs are as predicted Figure 26:  Designing a function for self-referential data  (Refines the recipes in figures 4 (pg. 5), 12 (pg. 9), and 18 (pg. 10))

9.5  More on Processing Simple Lists

Let us now look at another aspect of inventory management: the cost of an inventory. In addition to a list of the available toys, a store owner should also maintain a list of the cost of each item. The cost list permits the owner to determine how much the current inventory is worth or, given the inventory at the beginning of the year and that of the end of the year, how much profit the store makes.

A list of costs is most easily represented as a list. For example:

empty
(cons 1.22 empty)
(cons 2.59 empty)
(cons 1.22 (cons 2.59 empty))
(cons 17.05 (cons 1.22 (cons 2.59 empty)))

Again, for a real store, we cannot place an arbitrary limit on the size of such a list, and functions that process such cost lists must be prepared to consume lists of arbitrary size.

Suppose the toy store needs a function that computes the value of an inventory from the cost of the individual toys. We call this function sum. Before we can define sum, we must figure out how to describe all possible lists of numbers that the function may consume. In short, we need a data definition that precisely defines what an arbitrarily large list of numbers is. We can obtain this definition by replacing ``symbol'' with ``number'' in the definition of lists of symbols:

A list-of-numbers is either

1. the empty list, empty, or

2. (cons n lon) where n is a number and lon is a list of numbers.

Given that this data definition is self-referential again, we must first confirm that it actually defines some lists and that it defines all those inventories that we wish to represent. All of the examples above are lists of numbers. The first one, empty, is included explicitly. The second and third are constructed by adding the numbers 1.22 and 2.59, respectively, to the empty list. The others are lists of numbers for similar reasons.

As always, we start the development of the function with a contract, header, and purpose statement:

;; sum : list-of-numbers  ->  number
;; to compute the sum of the numbers on a-list-of-nums
(define (sum a-list-of-nums) ...)

Then we continue with function examples:

(= (sum empty) 
   0)

(= (sum (cons 1.00 empty))
   1.0)

(= (sum (cons 17.05 (cons 1.22 (cons 2.59 empty))))
   20.86)

If sum is applied to empty, the store has no inventory and the result should be 0. If the input is (cons 1.00 empty), the inventory contains only one toy, and the cost of the toy is the cost of the inventory. Hence the result is 1.00. Finally, for (cons 17.05 (cons 1.22 (cons 2.59 empty))), sum should yield

For the design of sum's template, we follow the design recipe, step by step. First, we add the cond-expression:

(define (sum a-list-of-nums)
  (cond
    [(empty? a-list-of-nums) ...]
    [(cons? a-list-of-nums) ...]))

The second clause indicates with a comment that it deals with constructed lists. Second, we add the appropriate selector expressions for each clause:

(define (sum a-list-of-nums)
  (cond
    [(empty? a-list-of-nums) ...]
    [(cons? a-list-of-nums)
     ... (first a-list-of-nums) ... (rest a-list-of-nums) ...]))

Finally, we add the natural recursion of sum that reflects the self-reference in the data definition:

(define (sum a-list-of-nums)
  (cond
    [(empty? a-list-of-nums) ...]
    [else ... (first a-list-of-nums) ... (sum (rest a-list-of-nums)) ...]))

The final template reflects almost every aspect of the data definition: the two clauses, the construction in the second clauses, and the self-reference of the second clauses. The only part of the data definition that the function template does not reflect is that the first item of a constructed input is a number.

Now that we have a template, let us define the answers for the cond-expression on a clause-by-clause basis. In the first clause, the input is empty, which means that the store has no inventory. We already agreed that in this case the inventory is worth nothing, which means the corresponding answer is 0. In the second clause of the template, we find two expressions:

1. (first a-list-of-nums), which extracts the cost of the first toy; and

2. (sum (rest a-list-of-nums)), which, according to the purpose statement of sum, computes the sum of (rest a-list-of-nums).

From these two reminders of what the expressions already compute for us, we see that the expression

(+ (first a-list-of-nums) (sum (rest a-list-of-nums)))

computes the answer in the second cond-clause.

Here is the complete definition of sum:

(define (sum a-list-of-nums)
  (cond
    [(empty? a-list-of-nums) 0]
    [else (+ (first a-list-of-nums) (sum (rest a-list-of-nums)))]))

A comparison of this definition with the template and the data definition shows that the step from the data definition to the template is the major step in the function development process. Once we have derived the template from a solid understanding of the set of possible inputs, we can focus on the creative part: combining values. For simple examples, this step is easy; for others, it requires rigorous thinking.

We will see in future sections that this relationship between the shape of the data definition and the function is not a coincidence. Defining the class of data that a function consumes always determines to a large extent the shape of the function.

Exercise 9.5.1.   Use DrScheme to test the definition of sum on the following sample lists of numbers:

empty 
(cons 1.00 empty)
(cons 17.05 (cons 1.22 (cons 2.59 empty)))

Compare the results with our specifications. Then apply sum to the following examples:

empty
(cons 2.59 empty)
(cons 1.22 (cons 2.59 empty))

First determine what the result should be; then use DrScheme to evaluate the expressions.    Solution

Exercise 9.5.2.   Develop the function how-many-symbols, which consumes a list of symbols and produces the number of items in the list.

Develop the function how-many-numbers, which counts how many numbers are in a list of numbers. How do how-many-symbols and how-many-numbers differ?    Solution

Exercise 9.5.3.   Develop the function dollar-store?, which consumes a list of prices (numbers) and checks whether all of the prices are below 1.

For example, the following expressions should evaluate to true:

(dollar-store? empty)

(not (dollar-store? (cons .75 (cons 1.95 (cons .25 empty)))))

(dollar-store? (cons .15 (cons .05 (cons .25 empty))))

Generalize the function so that it consumes a list of prices (numbers) and a threshold price (number) and checks that all prices in the list are below the threshold.    Solution

Exercise 9.5.4.   Develop the function check-range1?, which consumes a list of temperature measurements (represented as numbers) and checks whether all measurements are between 5^oC and 95^oC.

Generalize the function to check-range?, which consumes a list of temperature measurements and a legal interval and checks whether all measurements are within the legal interval.    Solution

Exercise 9.5.5.   Develop the function convert. It consumes a list of digits and produces the corresponding number. The first digit is the least significant, and so on.

Also develop the function check-guess-for-list. It implements a general version of the number-guessing game of exercise 5.1.3. The function consumes a list of digits, which represents the player's guess, and a number, which represents the randomly chosen and hidden number. Depending on how the converted digits relate to target, check-guess-for-list produces one of the following three answers: 'TooSmall, 'Perfect, or 'TooLarge.

The rest of the game is implemented by guess.ss. To play the game, use the teachpack to guess.ss and evaluate the expression

(guess-with-gui-list 5 check-guess-for-list)

after the functions have been thoroughly developed.    Solution

Exercise 9.5.6.   Develop the function delta, which consumes two price lists, that is, lists of numbers. The first represents the inventory at the beginning of a time period, the second one the inventory at the end. The function outputs the difference in value. If the value of the inventory has increased, the result is positive; if the value has decreased, it is negative.    Solution

Exercise 9.5.7.   Define the function average-price. It consumes a list of toy prices and computes the average price of a toy. The average is the total of all prices divided by the number of toys.

Iterative Refinement: First develop a function that works on non-empty lists. Then produce a checked function (see section 7.5) that signals an error when the function is applied to an empty list.    Solution

Exercise 9.5.8.   Develop the function draw-circles, which consumes a posn p and a list of numbers. Each number of the list represents the radius of some circle. The function draws concentric red circles around p on a canvas, using the operation draw-circle. Its result is true, if it can draw all of them; otherwise an error has occurred and the function does not need to produce a value.

Use the teachpack draw.ss; create the canvas with (start 300 300). Recall that draw.ss provides the structure definition for posn (see section 7.1).    Solution