[ 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.
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
to call error! ]
[ moved example code for length, append, reverse from here to an earlier section ]
map and for-each
map and for-each are used to apply a procedure to
elements of lists. They're good for coding repetitive operations
over sets of objects.
map
map takes a procedure and applies it to the elements of a
list (or corresponding elements of a set of lists), returning a list
of results.
For example, if we want to double
the elements of a list, we can use map and the double
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 map, which
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))))))
Notice that map may construct a list of results front-to-back, or
back-to-front, depending on the order of the evaluation of the arguments
to cons. That is, it may apply the mapped procedure
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
Like map, for-each applies a procedure to each element of
a list, or to corresponding elements of a set of lists. Unlike map,
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
what a begin expression does, except that the "subexpressions"
are not textually written out--they're applications of a first-class
procedure to list items.
Like begin, 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
empty. for-each makes no sense for an empty list, since it
must return the value of the last application.
Since 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.
If 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
to pair.
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.
member and assoc, and friends
The standard Scheme procedures member and 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 (eq? or eqv?) when searching
for an item in list.
member, memq, and memv
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.
For example, (member 3 '(1 4 3 2)) returns (3 2),
and (member 'foo '(bar baz quux)) returns #f.
Lists are often used as an implementation of sets, and member serves
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)))))
Note that 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 memv.
assoc, assq, and assv
assoc is used to search a special kind of nested list called an
association list. Association lists are often used to represent
small tables.
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 assoc returns.)
Some example uses:
Scheme>(assoc 'julie '((paul august 22) (julie feb 9) (veronique march 28)))
(julie february 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
Like member, 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 eq? test.")
If the keys may be numbers, assv? should probably be used instead.
It considers = numbers the same, but otherwise tests object identity,
like eq?. (The name assv suggests "associate using the
eqv? test.")