5.4.1 Procedures that examine lists
All of the example procedures in this section take a single List as
input and produce a scalar value that depends on the elements of the
List as output. These procedures have base cases where the List is
empty, and recursive cases that apply the recursive procedure to the
cdr
of the input List.
How many elements are in a given
List?^{1} Our standard recursive problem solving
technique is to “Think of the simplest version of the problem, something
you can already solve.” For this procedure, the simplest version of the
problem is when the input is the empty list, null
. We know the length
of the empty list is 0
. So, the base case test is (null? p)
and the
output for the base case is 0
.
For the recursive case, we need to consider the structure of all lists
other than null
. Recall from our definition that a List is either
null
or (cons 0)
. The base case handles the null
list; the
recursive case must handle a List that is a Pair of an element and a
List. The length of this List is one more than the length of the List
that is the cdr
of the Pair.
Here are a few example applications of our listlength
procedure:
0
> (listlength (cons 0 null))
1
> (listlength (list 1 2 3 4))
4
First, we define a procedure that takes a List of numbers as input
and produces as output the sum of the numbers in the input List. As
usual, the base case is when the input is null
: the sum of an empty
list is 0
. For the recursive case, we need to add the value of the
first number in the List, to the sum of the rest of the numbers in the
List.
(if (null? p) 0 (+ (car p) (listsum (cdr p)))))
We can define listproduct similarly, using *
in place of
+
. The base case result cannot be 0
, though, since then the final
result would always be 0
since any number multiplied by 0
is 0
. We
follow the mathematical convention that the product of the empty list is
1
.
(if (null? p) 1 (* (car p) (listproduct (cdr p)))))
Exercise 5.11. Define a procedure islist?
that takes one input
and outputs true if the input is a List, and false otherwise. Your
procedure should behave identically to the builtin list?
procedure,
but you should not use list?
in your definition.
Exercise 5.12. Define a procedure listmax
that takes a List of
nonnegative numbers as its input and produces as its result the value
of the greatest element in the List (or 0
if there are no elements in
the input List). For example, (listmax (list 1 1 2 0))
should
evaluate to 2
.

Scheme provides a builtin procedure
length
that takes a List as its input and outputs the number of elements in the List. Here, we will define our ownlistlength
procedure that does this (without using the builtinlength
procedure). As with many other examples and exercises in this chapter, it is instructive to define our own versions of some of the builtin list procedures. ↩