Go to the first, previous, next, last section, table of contents.

Using Predicates (Hunk H)

==================================================================
Hunk H starts here:
==================================================================

Suppose we want to sum a list of numbers. Before trying to write a procedure to do that, we should think about what a list of numbers is. Recall that a list is either the empty list, or a pair whose cdr is a list. A list of numbers, then, is a list whose contents (the cars) are numbers. So a list of numbers is an empty list, or a pair whose car is a number and whose cdr is a list of numbers.

Given this recursive description of a list of numbers, it's pretty easy to come up with a recursive description of the sum of a list of numbers.

The sum of a list of numbers is zero if the list is empty, or the sum of the car of the first pair plus the sum of the rest of the list.

We can write a procedure list-sum to compute that, like this:

Scheme> (define (list-sum lis)
           (if (null? lis)   ;; if empty list?
               0             ;; then sum is zero
               (+ (car lis)  ;; else sum is car plus the
                  (list-sum (cdr lis))))) ;; sum of rest of list
#void

Try typing in this example, or cutting and pasting it from this file into your running Scheme system. (If you're reading this in a web browser, that should be easy--just cut the text from the browser window, and paste it into your Scheme window at the prompt.) Cutting and pasting is a lot easier than typing in the whole thing!

This procedure accepts one argument, lis, which should be a list. It checks to see whether the list is empty, i.e., a null pointer, using the predicate null?. If so, it returns 0 as the sum of the elements in the list.

If the list is not empty, the sum of the elements is the sum of the car value, plus the sum of the elements in the rest of the list. In that case, list-sum takes the car of the list and the list-sum of the rest of the list, adds them together, and returns the result.

Try calling this procedure with some lists of numbers, e.g.,

Scheme>(list-sum '(1 2 3))
6
Scheme>(list-sum '(4 5 6))
15
Scheme>(list-sum (cons 1 (cons 2 (cons 3 '()))))
6

The addition procedure + works with floating-point numbers, not just integers, so we can call list-sum with a list of floats as well as integers. (As in most languages, floating point numbers are written with a period to represent the decimal point. Note that there is no space between the digits and the decimal point, so that Scheme won't confuse this with dot notation for lists.)

Scheme>(list-sum '(1 2.2 3.3))

We can modify list-sum to print out its argument at each call. Then we can watch the recursion:

Scheme> (define (list-sum lis)
           (display "in list-sum, lis is: ")
           (display lis)
           (newline)      ;; write a linebreak 
           (if (null? lis)   ;;  if empty list?
               0             ;; then sum is zero
               (+ (car lis)  ;; else it's car plus the
                  (list-sum (cdr lis))))) ;; sum of rest of list
#void

Go to the first, previous, next, last section, table of contents.