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

Basic Programming Examples (Hunk P)

[ 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.

An Error Signaling Routine

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 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 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.")


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