5.4.2 Generic accumulators

The list-length, list-sum, and list-product procedures all have very similar structures. The base case is when the input is the empty list, and the recursive case involves doing something with the first element of the List and recursively calling the procedure with the rest of the List:

(define (p) (if (null? p) ((car p) ((cdr p)))))

We can define a generic accumulator procedure for lists by making the base case result and accumulator function inputs:

(define (list-accumulate f base p) (if (null? p) base (f (car p)
(list-accumulate f base (cdr p)))))

We can use list-accumulate to define list-sum and list-product:

(define (list-sum p) (list-accumulate + 0 p)) (define (list-product p)
(list-accumulate * 1 p))

Defining the list-length procedure is a bit less natural. The recursive case in the original list-length procedure is (+ 1 (list-length (cdr p))); it does not use the value of the first element of the List. But, list-accumulate is defined to take a procedure that takes two inputs—the first input is the first element of the List; the second input is the result of applying list-accumulate to the rest of the List. We should follow our usual strategy: be optimistic! Being optimistic as in recursive definitions, the value of the second input should be the length of the rest of the List. Hence, we need to pass in a procedure that takes two inputs, ignores the first input, and outputs one more than the value of the second input:

(define (list-length p)
        (list-accumulate (lambda (el length-rest) (+ 1 length-rest)) 0 p))

Exercise 5.13. Use list-accumulate to define list-max (from Exercise 5.12).

Exercise 5.14. $\left[\star \right]$Use list-accumulate to define is-list? (from Exercise 5.11).

Example 5.3: Accessing List Elements

The built-in car procedure provides a way to get the first element of a list, but what if we want to get the third element? We can do this by taking the cdr twice to eliminate the first two elements, and then using car to get the third: (car (cdr (cdr p)))

We want a more general procedure that can access any selected list element. It takes two inputs: a List, and an index Number that identifies the element. If we start counting from 1 (it is often more natural to start from 0), then the base case is when the index is 1 and the output should be the first element of the List: (if (= n 1) (car p) )

For the recursive case, we make progress by eliminating the first element of the list. We also need to adjust the index: since we have removed the first element of the list, the index should be reduced by one. For example, instead of wanting the third element of the original list, we now want the second element of the cdr of the original list.

(define (list-get-element p n) (if (= n 1) (car p) (list-get-element
(cdr p) (- n 1))))

What happens if we apply list-get-element to an index that is larger than the size of the input List (for example, (list-get-element (list 1 2) 3))?

The first recursive call is (list-get-element (list 2) 2). The second recursive call is (list-get-element (list) 1). At this point, n is 1, so the base case is reached and (car p) is evaluated. But, p is the empty list (which is not a Pair), so an error results.

A better version of list-get-element would provide a meaningful error message when the requested element is out of range. We do this by adding an if expression that tests if the input List is null:

(define (list-get-element p n)
        (if (null? p)
                (error "Index out of range")
                (if (= n 1) (car p) (list-get-element (cdr p) (- n 1)))))

The built-in procedure error takes a String as input. The String datatype is a sequence of characters; we can create a String by surrounding characters with double quotes, as in the example. The error procedure terminates program execution with a message that displays the input value.

Checking explicitly for invalid inputs is known as defensive programming. Programming defensively helps avoid tricky to debug errors and makes it easier to understand what went wrong if there is an error.

Exercise 5.15. Define a procedure list-last-element that takes as input a List and outputs the last element of the input List. If the input List is empty, list-last-element should produce an error.

Exercise 5.16. Define a procedure list-ordered? that takes two inputs, a test procedure and a List. It outputs true if all the elements of the List are ordered according to the test procedure. For example, (list-ordered? < (list 1 2 3)) evaluates to true, and (list-ordered? < (list 1 2 3 2)) evaluates to false. Hint: think about what the output should be for the empty list.