Writing GNU Emacs Extensions

Recursive List Functions

Traditional Lisp textbooks use a variety of short programming exercises to illustrate the behavior of lists and cons cells. Let's just take a moment now to look at two of the better-known examples, then move on.

Our goal in this exercise is to define a function called flatten that, given a list, undoes any nesting of sublists, causing all elements to be at the top level. For example:

(flatten '(a ((b) c) d)) ⇒ (a b c d)

The solution calls for recursion, flattening the car and the cdr separately, then recombining them in a way that preserves flatness. Suppose the input to flatten is the list

((a (b)) (c d))

The car is (a (b)) which when flattened yields (a b). The cdr is ((c d)) which when flattened becomes (c d). The function append can be used to combine (a b) with (c d) and preserve flatness, yielding (a b c d). So at the heart of flatten is this code:

(append (flatten (car lst))
        (flatten (cdr lst)))

(I've chosen lst as the name for flatten's parameter. I prefer not to use list, which is the name of a Lisp function.) Now, flatten is only meant to work on lists, so (flatten (car lst)) is an error if (car lst) is not a list. We must therefore elaborate as follows:

(if (listp (car lst))
    (append (flatten (car lst))
            (flatten (cdr lst))))

This if has no "else" clause. What if (car lst) is not a list? For example, suppose lst were

(a ((b) c))

The car, a, is not a list. In this case, we will simply need to flatten the cdr, (((b) c)), to get (b c); then cons the car back ...