5.4.3 Procedures that construct lists

The procedures in this section take values (including Lists) as input, and produce a new List as output. As before, the empty list is typically the base case. Since we are producing a List as output, the result for the base case is also usually null. The recursive case will use cons to construct a List combining the first element with the result of the recursive application on the rest of the List.

Example 5.12: Mapping

One common task for manipulating a List is to produce a new List that is the result of applying some procedure to every element in the input List.

For the base case, applying any procedure to every element of the empty list produces the empty list. For the recursive case, we use cons to construct a List. The first element is the result of applying the mapping procedure to the first element of the input List. The rest of the output List is the result of recursively mapping the rest of the input List.

Here is a procedure that constructs a List that contains the square of every element of the input List:

(define (list-square p) (if (null? p) null (cons (square (car p))
(list-square (cdr p)))))

We generalize this by making the procedure which is applied to each element an input. The procedure list-map takes a procedure as its first input and a List as its second input. It outputs a List whose elements are the results of applying the input procedure to each element of the input List.1

(define (list-map f p) (if (null? p) null (cons (f (car p)) (list-map f
(cdr p)))))

We can use list-map to define square-all:

(define (square-all p) (list-map square p))

Exercise 5.17.  Define a procedure list-increment that takes as input a List of numbers, and produces as output a List containing each element in the input List incremented by one. For example, (list-increment 1 2 3) evaluates to (2 3 4).

Exercise 5.18.  Use list-map and list-sum to define list-length: (define (list-length p) (list-sum (list-map p)))

Example 5.5: Filtering

Consider defining a procedure that takes as input a List of numbers, and evaluates to a List of all the non-negative numbers in the input. For example, (list-filter-negative (list 1 -3 -4 5 -2 0)) evaluates to (1 5 0).

First, consider the base case when the input is the empty list. If we filter the negative numbers from the empty list, the result is an empty list. So, for the base case, the result should be null.

In the recursive case, we need to determine whether or not the first element should be included in the output. If it should be included, we construct a new List consisting of the first element followed by the result of filtering the remaining elements in the List. If it should not be included, we skip the first element and the result is the result of filtering the remaining elements in the List.

(define (list-filter-negative p) (if (null? p) null (if ( \> = (car p)
0) (cons (car p) (list-filter-negative (cdr p))) (list-filter-negative
(cdr p)))))

Similarly to list-map, we can generalize our filter by making the test procedure as an input, so we can use any predicate to determine which elements to include in the output List.2

(define (list-filter test p) (if (null? p) null (if (test (car p)) (cons
(car p) (list-filter test (cdr p))) (list-filter test (cdr p)))))

Using the list-filter procedure, we can define list-filter-negative as:

(define (list-filter-negative p) (list-filter (lambda (x) ( \> = x
0)) p))

We could also define the list-filter procedure using the list-accumulate procedure from Section 5.4.1:

(define (list-filter test p) (list-accumulate (lambda (el rest) (if
(test el) (cons el rest) rest)) null p))

Exercise 5.19. Define a procedure list-filter-even that takes as input a List of numbers and produces as output a List consisting of all the even elements of the input List.

Exercise 5.20.Define a procedure list-remove that takes two inputs: a test procedure and a List. As output, it produces a List that is a copy of the input List with all of the elements for which the test procedure evaluates to true removed. For example, (list-remove (lambda (x) (= x 0)) (list 0 1 2 3)) should evaluates to the List (1 2 3).

Exercise 5.21. $\left[\star \star \right]$Define a procedure list-unique-elements that takes as input a List and produces as output a List containing the unique elements of the input List. The output List should contain the elements in the same order as the input List, but should only contain the first appearance of each value in the input List.

Example 5.6: Append

The list-append procedure takes as input two lists and produces as output a List consisting of the elements of the first List followed by the elements of the second List.3 For the base case, when the first List is empty, the result of appending the lists should just be the second List. When the first List is non-empty, we can produce the result by cons-ing the first element of the first List with the result of appending the rest of the first List and the second List.

(define (list-append p q)
        (if (null? p) q (cons (car p) (list-append (cdr p) q))))
Example 5.7: Reverse

The list-reverse procedure takes a List as input and produces as output a List containing the elements of the input List in reverse order.4 For example, (list-reverse (list 1 2 3)) evaluates to the List (3 2 1). As usual, we consider the base case where the input List is null first. The reverse of the empty list is the empty list. To reverse a non-empty List, we should put the first element of the List at the end of the result of reversing the rest of the List.

The tricky part is putting the first element at the end, since cons only puts elements at the beginning of a List. We can use the list-append procedure defined in the previous example to put a List at the end of another List. To make this work, we need to turn the element at the front of the List into a List containing just that element. We do this using (list (car p)).

(define (list-reverse p) (if (null? p) null (list-append (list-reverse
(cdr p)) (list (car p)))))

Exercise 5.22.  Define the list-reverse procedure using list-accumulate.

Example 5.8: Intsto

For our final example, we define the intsto procedure that constructs a List containing the whole numbers between 1 and the input parameter value. For example, (intsto 5) evaluates to the List (1 2 3 4 5).

This example combines ideas from the previous chapter on creating recursive definitions for problems involving numbers, and from this chapter on lists. Since the input parameter is not a List, the base case is not the usual list base case when the input is null. Instead, we use the input value 0 as the base case. The result for input 0 is the empty list. For higher values, the output is the result of putting the input value at the end of the List of numbers up to the input value minus one.

A first attempt that doesn’t quite work is:

(define (revintsto n)
        (if (= n 0) null (cons n (revintsto (- n 1)))))

The problem with this solution is that it is cons-ing the higher number to the front of the result, instead of at the end. Hence, it produces the List of numbers in descending order: (revintsto 5) evaluates to (5 4 3 2 1).

One solution is to reverse the result by composing list-reverse with revintsto:

(define (intsto n) (list-reverse (revintsto n)))

Equivalently, we can use the fcompose procedure from Section 4.2:

(define intsto (fcompose list-reverse revintsto))

Alternatively, we could use list-append to put the high number directly at the end of the List. Since the second operand to list-append must be a List, we use (list n) to make a singleton List containing the value as we did for list-reverse.

(define (intsto n)
        (if (= n 0) null (list-append (intsto (- n 1)) (list n))))

Although all of these procedures are functionally equivalent (for all valid inputs, each function produces exactly the same output), the amount of computing work (and hence the time they take to execute) varies across the implementations. We consider the problem of estimating the running-times of different procedures in Part II.

Exercise 5.70. Define factorial using intsto.


  1. Scheme provides a built-in map procedure. It behaves like this one when passed a procedure and a single List as inputs, but can also work on more than one List input at a time. 

  2. Scheme provides a built-in function filter that behaves like our list-filter procedure. 

  3. There is a built-in procedure append that does this. The built-in append takes any number of Lists as inputs, and appends them all into one List. 

  4. The built-in procedure reverse does this.