Let us now turn our attention to a second recursive function. As with the function lat? it is a predicate function. Unlike lat?, however, it takes two inputs. The function is defined as follows:
(define member?
(λ (a s)
(cond
[(null? s) #f]
[(equal? (first s) a) #t]
[else (member? a (rest s))])))
Exercise 62
Evaluate each of these functional expressions:
(member? ▽Fred ▽())
(member? ▽(Fred Jane) ▽((Fred Jane) Mary))
From the definition above, we see that the first input to the function member? can be any data expression, whereas its second input must be a list. You have just noted that, when the second input is the null list, the function outputs the boolean #f and, when the first data expression in the second input is the same as the first input, the function outputs the boolean #t.
Suppose now that the second input is a non-null list whose first data expression is not the same as the first input. For example, suppose the first input is the atom and and the second input is the list (war and peace). The following trace table illustrates the behavior of the function member? in this case:
(member? and (war and peace))
(member? and (rest (war and peace)))
(member? and (and peace))
#t
Exercise 63
Evaluate the functional expression (member? a s) when
a : (merry); s : (Robin)
a : (merry); s : (Robin Hood)
a : (merry); s : (Robin Hood and his (merry) men)
Carefully describe the behavior of the function member?.
Before we go any further, note that the terminating conditions of the function member? are:
the second input is the null list, and
the first data expression in the second input is the same as the first input.
The fact that the first terminating condition of the function member? involves only the function null? is typical; the same is true in the case of the function lat?. Note also that (member? a (rest s)) is the (only) natural recursion of the function member?, so once again we have a function that recurs on the rest of (one of) its input(s).
As you work through the problem set that follows the next graded exercise, keep in mind the two pointers to writing recursive functions that we listed just now. In other words, when writing a definition for a function you believe to be recursive, ask yourself, "What is the output when the input (or one of the inputs) is the null list?" And, as a first guess, assume that any natural recursions will involve the rest of one or more of the inputs.
