Sketchy LISP

An Introduction to Functional Programming in Scheme

1.5 Some Things You Can Do with Lists

Scheme is a language of the LISP family, and LISP is short for LISt Processor, so it is not surprising that Scheme has quite a few procedures for processing lists. The list is a simple yet very flexible data structure that can be used to implement a lot of useful algorithms. In the previous section, the list was described as a sequence of objects delimited by parentheses. While this is true, it is a simplified description. This section will explain lists a little more in depth.

The most basic procedures for processing lists are called cons, car, and cdr. Car and cdr are used to decompose lists and cons is used to construct lists:

  (car '(a b c)) => a
  (cdr '(a b c)) => (b c)
(cons 'a '(b c)) => (a b c)

The following relation exists between these procedures: For any non-empty list x, the subsequent proposition holds:

x  =  (cons (car x) (cdr x))

The car procedure extracts the first member of a list. This member is also called the head of the list. Cdr extracts a sublist containing all but the head of a list. This sublist is called the tail of the list. Cons, finally, assembles a new list by attaching a new head to an existing list.

There are a few important things to notice about these procedures. For example, car always extracts the first member of a flat list, where lists contained in lists count as single members, so:

(car '((a b) c)) => (a b)

The same is valid for cdr:

(cdr '((a b) d)) => (d)

Cons can only add one single member to the head of an existing list. It cannot be used to append lists, because

(cons '(a b) '(c d)) => ((a b) c d)

If you want to append lists, use append:

(append '(a b) '(c d)) => (a b c d)

The tail of a single-element list is the empty list and adding an element to the empty list results in a single-element list:

(cdr '(x)) => ()
(cons 'x '()) => (x)

Neither car nor cdr may be applied to the empty list, because the empty list has neither a head nor a tail:

(car '()) => bottom
(cdr '()) => bottom

Using just the three basic list procedures, you can do a lot of interesting things, already. For instance, an append procedure can easily be written in terms of these:

(define (append2 a b)
  (cond ((null? a) b)
    (else (cons (car a)
                (append2 (cdr a) b)))))

The null? predicate tests whether a list is empty:

(null? '(a b)) => #f
(null? '())    => #t

(Note that the empty list must be quoted in standard Scheme, even if some implementations do not enforce this rule.)

So how does append2 work? Here is an explanation:

(append2 '(a b) '(c d))
-> (append2 (a b) (c d))
-> (cons (car (a b)) (append2 (cdr (a b)) (c d)))
-> (cons a (append2 (b) (c d)))
-> (cons a (cons b (append2 () (c d))))
-> (cons a (cons b (c d)))
-> (cons a (b c d))
=> (a b c d)

Note that Scheme notation does not provide any means of representing intermediate steps involving symbols or literal lists. Therefore, literal objects are outlined using boldface characters in partial reductions. For example,

(cons a (b c d))

should actually be read as

(cons 'a '(b c d))

in illustrations like the sample reduction of append2 above.

You may have noticed that append2 has the same weakness as the fact procedure introduced at the beginning of this book: it adds one recursive call for each element in the first list. Can this procedure, too, be converted into a tail-recursive one? Yes, it can:

(define (append2 a b)
  (letrec
    ((app2
       (lambda (a b)
         (cond ((null? a) b)
           (else (app2 (cdr a)
                       (cons (car a) b)))))))
    (app2 (reverse a) b)))

The embedded app2 procedure, which does the real work, removes one member of a at each iteration and attaches it to b. However, this causes the members of a to be in reverse order when the procedure finishes. This is why the list a is reversed before passing it to app2. This is quite a common technique in Scheme.

This version of append2 is much better than the initial one, but still not as nice as the append procedure that is built into the language. For example, to append three lists, you have to write

(append2 '(a b) (append2 '(c d) '(e f)))

while the built-in procedure lets you append any number of lists:

(append) => ()
(append '(a b)) => (a b)
(append '(a b) '(c d)) => (a b c d)
(append '(a b) '(c d) '(e f)) => (a b c d e f)

And this version of append can still be written in Scheme! How this is done will be explained in a later section, though.