Processing Lists of Arbitrary Length

Next: Designing Functions for Self-Referential Up: Compound DataPart 2: Previous: Data Definitions for Lists

Processing Lists of Arbitrary Length

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.

Exercises 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

Next: Designing Functions for Self-Referential Up: Compound DataPart 2: Previous: Data Definitions for Lists

PLT