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.

Example 5.1: Length

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.

(define (list-length p) (if (null? p) 0 (+ 1 (list-length (cdr p)))))

Here are a few example applications of our list-length procedure:

> (list-length null)
0
> (list-length (cons 0 null))
1
> (list-length (list 1 2 3 4))
4
Example 5.10: List Sums and Products

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.

(define (list-sum p)
(if (null? p) 0 (+ (car p) (list-sum (cdr p)))))

We can define list-product 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.

(define (list-product p)
(if (null? p) 1 (* (car p) (list-product (cdr p)))))

Exercise 5.11.  Define a procedure is-list? that takes one input and outputs true if the input is a List, and false otherwise. Your procedure should behave identically to the built-in list? procedure, but you should not use list? in your definition.

Exercise 5.12.  Define a procedure list-max that takes a List of non-negative 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, (list-max (list 1 1 2 0)) should evaluate to 2.

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