[ From here on, the text is not structured as a type-along tutorial interleaved with Chapter 2. However, it's a good idea to experiment with the examples interactively in a running Scheme system . ] In this section, I'll give a few simple examples of Scheme programming, mostly using recursion to manipulate lists without side effects. (Later, I'll revisit some of these examples, and show how to implement them more efficiently, using tail recursion, but still without side effects.)
I'll show how to implement simple versions of some standard Scheme procedures; this may help you understand what those procedures do, and how to use them. (Later, I'll return to some of these examples and show how to implement more general versions.) I'll also give some examples that aren't standard Scheme procedures, but illustrate common idioms.
Some of these examples use higher-order procedures--procedures which operate on procedures--and toward the end of the section, I'll discuss currying, a technique for creating specialized versions of procedures in a particular context.
You should get used to thinking recursively, and avoiding side effects most of the time. It's often easier to write things recursively than using normal loops and side effects.
It's often useful to put error-checking code in your procedures, to make sure that their arguments satisfy whatever preconditions they need to operate correctly.
In a dynamically-typed language, this is often good for making sure
that you detect errors where pass values to a procedure that can't
handle arguments of those types. Usually when you do that, you'll
find out soon enough, because you'll perform an illegal operation
(like taking the
car of a number), and Scheme will detect the
error and tell you.
Scheme doesn't yet have a standard error signaling routine, but we
will use one that many systems provide, called
error takes any number of arguments,
displays them to
tell the user what went wrong, and signals an error. (In most interactive
Scheme systems, you'll get a break prompt like the one you get when
Scheme itself detects an error.)
[ If your system doesn't have
error, you'll get an error signaled
anyway, in the form of an unbound variable exception when you try
[ moved example code for length, append, reverse from here to an earlier section ]
for-each are used to apply a procedure to
elements of lists. They're good for coding repetitive operations
over sets of objects.
map takes a procedure and applies it to the elements of a
list (or corresponding elements of a set of lists), returning a list
For example, if we want to double
the elements of a list, we can use
map and the
procedure we defined earlier:
Scheme>(map double '(1 2 3)) (2 4 6)
If the procedure we're calling takes more than one argument, we
can pass two lists of arguments to
map. For example, if we want
to add corresponding elements of two lists, and get back a corresponding
list of their sums, we can do this:
Scheme>(map + '(1 2 3) '(4 5 6)) (5 7 9)
Right now, we'll just write a simplified version of
takes one list of values and applies a one-argument procedure to them.
(define (map proc lis) (cond ((null? lis) '()) ((pair? lis) (cons (proc (car lis)) (map proc (cdr lis))))))
map may construct a list of results front-to-back, or
back-to-front, depending on the order of the evaluation of the arguments
cons. That is, it may apply the
on the way down during recursion, or on the way back up. (This is allowed
by the Scheme standard--the order of the results in the resulting list
corresponds to the ordering of the argument list(s), but the dynamic order
of applications is not specified.)
for-each applies a procedure to each element of
a list, or to corresponding elements of a set of lists. Unlike
for-each discards the values returned by all of the applications
except the last, and returns the last value. (The applications are
also guaranteed to occur in front-to-back list order.) This is sort of like
begin expression does, except that the "subexpressions"
are not textually written out--they're applications of a first-class
procedure to list items.
for-each is used to execute expressions in
sequence, for effect rather than value, except that the last value
may be useful.
Here's a simplified version of
for-each, which we'll call
for-each1. It takes exactly one procedure, assumed to be
a procedure of one argument, and one list. It applies the procedure
to each of the elements of the list in turn, and returns the result
of the last application.
(define (for-each1 proc lis) (cond ((null? (cdr lis)) ; one-element list? (proc (car lis))) (else (proc (car lis)) (for-each1 proc (cdr lis)))))
Notice that this is a little different from our usual recursive list
traversal, where the first thing we do is check whether the list is
for-each makes no sense for an empty list, since it
must return the value of the last application.
for-each must take a list of one or more items, the
base case for the recursion is when we hit a one-element
list, rather than an empty list. The recursive case is when
we have a list that's got more than one element. Anything else
is an error due to bad input.
We can characterize this kind of data structure recursively, almost the same way as the normal definition of a proper list:
A list-of-one-or-more-elements is
The code for
for-each1 directly reflects this
characterization of the data it's expected to handle. The
base case comes first, and then the recursive case.
for-each1 encounters a nonlist or an
empty list, it will signal an error immediately, because both
branches assume that they're operating on a pair, and attept
to take the car of it, which is an error for anything but
a pair. If
for-each1 encounters an improper list, it will
likewise signal an error at the first
cdr that doesn't refer
As usual, this is what we want--the recursive structure of the data structure we're operating on is reflected directly in the structure of the recursive code, and unexpected data cause errors to be signaled immediately.
assoc, and friends
The standard Scheme procedures
assoc are used
for searching lists. I'll show how they can be implemented in
Scheme, even though every Scheme system includes them.
Each of these procedures has two alternative versions, which use
different equality tests (
eqv?) when searching
for an item in list.
member searches a list for an item, and returns the remainder
of the list starting at the point where that item is found. (That is,
it returns the pair whose
car refers to the item.) It returns
#f if the item is not in the list.
(member 3 '(1 4 3 2)) returns
(member 'foo '(bar baz quux)) returns
Lists are often used as an implementation of sets, and
nicely as a test of set membership. If an item is not found, it returns
#f, and if it is, it returns a pair. Since a pair is a true
value, the result of
member can be used like a boolean
in a conditional.
Since member returns the "rest" of a list, starting with the point where the item is found, it can also be particularly useful with ordered lists, by skipping past all of the elements up to some desired point, and returning the rest.
(define (member thing lis) (if (null? lis) #f (if (equal? (car lis) thing) lis (member thing (cdr lis)))))
member uses the
equal? test (data structure
equivalence) when searching. This makes sense in situations where
you want same-structured data structures to count as "the same."
(For example, if you're searching a list of lists, and you want
a sublist that has the same structure as the target list to count
as "the same.") Note that if the elements of the list are
circular data structures,
member may loop infinitely.
If you want to search for a particular object, you should use
memq?, which is like
member except that it uses the
eq? test, and may be much faster.
If the list may include numbers, and you want copies of the same number
to count as "the same", you should use
assoc is used to search a special kind of nested list called an
association list. Association lists are often used to represent
An association list is a list of lists. Each sublist represents an association between a key and a list of values. The car of the list is taken as the key field, but the whole list of values is returned.
(Typically, an association list is used as a simple table to map
keys to single values. In that case, you must remember to take the
cadr of the sublist that
Some example uses:
Scheme>(assoc 'julie '((paul august 22) (julie feb 9) (veronique march 28))) (julie feb 9) Scheme>(assoc 'key2 '((key1 val1) (key2 val2) (key0 val0))) (key2 val2) Scheme>(cadr (assoc 'key2 '((key1 val1) (key2 val2) (key0 val0)))) val2 Scheme>(assoc '(feb 9) '(((aug 1) maggie phil) ((feb 9) jim heloise) ((jan 6) declan))) ((feb 9) jim heloise)
And the code:
(define (assoc thing alist) (if (null? alist) #f (if (equal? (car (car alist)) thing) (car alist) (assoc thing (cdr alist)))))
Notice that the basic pattern of recursion here is the same as for
traversing other proper lists. The
assoc uses the
equal? test when searching
a list. This is what you want if (and only if) you want same-structured
data structures to count as "the same."
assq is like
assoc, but uses the
eq? test. This
is the most commonly-used routine for searching association lists,
because symbols are commonly used as keys for association lists. (The name
assq suggests "associate using the
If the keys may be numbers,
assv? should probably be used instead.
= numbers the same, but otherwise tests object identity,
eq?. (The name
assv suggests "associate using the