TCEA State 1998 Slides


Example: List Membership

Consider the function member: given an item and a list, it checks whether the item is in the list. (For example, the list could be of party invitees, and the student may want to check whether he invited a friend.) Here are the steps we expect our students to take when constructing a solution.

First, construct a data definition. We don't know anything interesting about items, so we'll leave those alone. What's the structure of a list of items?

A list of items is

Now let's start to write the function. From the problem statement, we see that the function takes two arguments. Following Scheme syntax, we will write down a template for the function definition, leaving the body unspecified: 

(define (member x l)
  ...)
where x is an item and l is a list of items.

The data definition of a list of items tells us that it is conditionally defined. Hence, the Scheme program will probably also have to be conditionally defined. Let's extend the template accordingly: 

(define (member x l)
  (cond
    ((empty? l) ...)
    (else       ...)))
We've now introduced the keyword cond, which is used for conditional definitions. Each branch of the cond consists of a question-and-answer pair, wrapped in parentheses. Thus the first question asks whether the list is empty, while the second is the keyword else, used for the fall-through case. (From the data definition, we know that it must be a join'ed, or non-empty, list in the second condition.)

What more can we get out of the data definition? Clearly there is no more information to be had about the empty list. But in the join'ed case, we know that there's a first item, and the rest of the list. The selectors first and rest extract these pieces. 

(define (member x l)
  (cond
    ((empty? l) ...)
    (else       ... (first l) ... (rest l) ...)))
We write the selectors to remind ourselves that we may need to use these data later, but leave the ellipses in since the function is not yet complete.

There's one last bit of information we can squeeze out of the data definition. The rest of l is a list of items, which is the same sort of thing that l is. Hence, we might find member handy later on down the line for processing the rest of l. On a blackboard we would indicate this with an arrow. Here, we'll just wrap the appropriate portion of l in the template of a call to member to remind ourselves of this. 

(define (member x l)
  (cond
    ((empty? l) ...)
    (else       ... (first l) ... (member ... (rest l)) ...)))

Okay, now we're ready to actually start studying the problem statement closely. What should the function produce if there are no items in the list? Clearly, whatever x refers to, it can't be in the list. So we can fill that slot in: 

(define (member x l)
  (cond
    ((empty? l) false)
    (else       ... (first l) ... (member ... (rest l)) ...)))

Suppose the list is non-empty; then there's at least one item in it, ie, (first l). This may or may not be the item we're looking for. Since there's a choice, we need to introduce a condition: 

(define (member x l)
  (cond
    ((empty? l) false)
    (else       (cond
                  ((equal? x (first l)) ... (member ... (rest l)) ...)
                  (else                 ... (member ... (rest l)) ...)))))
Note that this time, the choice is driven by some detail of the problem, not by the data definition.

If the first item of the list is our desired entry, then we're done: the item is in the list. 

(define (member x l)
  (cond
    ((empty? l) false)
    (else       (cond
                  ((equal? x (first l)) true)
                  (else                 ... (member ... (rest l)) ...)))))
Note that we ignored the (rest l), and its surrounding suggestion to use member recursively.

Suppose the first item isn't the one we're looking for. It may or may not be in the rest of the list; our answer is whatever we get from finding whether the item is in the rest of the list. But we have a function that does exactly that: member. Invoking member on the same item, and the rest of the list, will give us the desired answer. 

(define (member x l)
  (cond
    ((empty? l) false)
    (else       (cond
                  ((equal? x (first l)) true)
                  (else                 (member x (rest l)))))))
So our hints did come in handy for solving the problem!

PLT / scheme@cs.rice.edu

Last modified at 23:24:08 CST on Sunday, February 08, 1998