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.
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:
(listsquare (cdr p)))))
We generalize this by making the procedure which is applied to each
element an input. The procedure listmap
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}
(cdr p)))))
We can use listmap
to define squareall
:
Exercise 5.17. Define a procedure listincrement
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,
(listincrement 1 2 3)
evaluates to (2 3 4)
.
Exercise 5.18. Use listmap
and listsum
to define
listlength
: (define (listlength p) (listsum (listmap p)))
Consider defining a procedure that takes as input a List of
numbers, and evaluates to a List of all the nonnegative numbers in the
input. For example, (listfilternegative (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.
0) (cons (car p) (listfilternegative (cdr p))) (listfilternegative
(cdr p)))))
Similarly to listmap
, 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}
(car p) (listfilter test (cdr p))) (listfilter test (cdr p)))))
Using the listfilter
procedure, we can define listfilternegative
as:
0)) p))
We could also define the listfilter
procedure using the
listaccumulate
procedure from Section 5.4.1:
(test el) (cons el rest) rest)) null p))
Exercise 5.19. Define a procedure listfiltereven
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 listremove
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, (listremove (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
listuniqueelements
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.
The listappend
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 nonempty, 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.
(if (null? p) q (cons (car p) (listappend (cdr p) q))))
The listreverse
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,
(listreverse (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 nonempty
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
listappend
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))
.
(cdr p)) (list (car p)))))
Exercise 5.22. Define the listreverse
procedure using
listaccumulate
.
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:
(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 listreverse
with
revintsto
:
Equivalently, we can use the fcompose
procedure from Section 4.2:
Alternatively, we could use listappend
to put the high number
directly at the end of the List. Since the second operand to
listappend
must be a List, we use (list n)
to make a singleton List
containing the value as we did for listreverse
.
(if (= n 0) null (listappend (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 runningtimes of different procedures in Part II.
Exercise 5.70. Define factorial
using intsto
.

Scheme provides a builtin
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. ↩ 
Scheme provides a builtin function
filter
that behaves like ourlistfilter
procedure. ↩ 
There is a builtin procedure
append
that does this. The builtinappend
takes any number of Lists as inputs, and appends them all into one List. ↩ 
The builtin procedure
reverse
does this. ↩