Let's now fill in the function methodically, based on what we know at each stage. So far, all we know is that in-list? accepts an item and a shopping list. Items aren't very interesting (other than cake, of course), but we know something about shopping lists: they can either be empty, or they can have something put in them. Let us reflect this knowledge:
| in-list? (i, sl) | = |
|
Notice, further, that sl' is another shopping list.
Okay, this much followed purely from the form of the inputs. Now let's look at our examples. When given the item "cheese" and the empty list, in-list? returned false. Should it always do this? Yes: if there's nothing in the list, nothing will ever be found in it.
| in-list? (i, sl) | = |
|
Now let's look at the other case. We know that the list has some item i' in it. This item may or may not be the one we're looking for; we may want to do different things depending on which is the case.
| in-list? (i, sl) | = |
|
Now suppose i and i' are the same. Then we know that i is in the shopping list, and we need search no more. From the examples we wrote earlier, we see that the result of the function should be true.
| in-list? (i, sl) | = |
|
There's just one blank spot left. What if i' is not the item i we're looking for? There's still the rest of the list, sl', to look in. How can we do this? It would be nice if we had a function that checked whether an item was in a shopping list. But we do: that's exactly the function we're defining! So we pass the item we're looking for, i, and the rest of the shopping list, sl', to in-list?:
| in-list? (i,sl) | = |
|
Voilà! We've filled in all the blanks. Now we should work through the examples we wrote earlier and make sure the function produces the results we expected. Once we've done this, we can write the rest of our shopping list functions.
Is this a program?
PLT / scheme@cs.rice.edu
Last modified at 10:48:29 CST on Monday, November 10, 1997