These exercises are in addition to those in Graham. Several come from Wilensky's Common LispCraft.

Lisp #1: HAS-NUMBER-P (Wilensky 8.7)

Define (has-number-p s-exp) to return true if the s-expression is or contains a number.

> (has-number-p 1)
> (has-number-p 'a)
> (has-number-p '(a (b (c d) ((3)))))

Implement this using a simple conditional, recursion, and SOME. Letting SOME do some of the work is more efficient than a pure CAR-CDR recursive solution.

Lisp #2: KEY-IF (Wilensky 13.2)

Define the macro key-if to have the form

(KEY-IF test
  :THEN exp1 exp2 ...
  :ELSE exp3 exp4 ...)

This does about the same thing as:

(COND (test exp exp ...)
      (T else-exp else-exp ...))

Almost everything is optional in key-if except the test. Here are some legal forms and their results:

> (key-if (> 3 1) :then 'ok)
> (key-if (< 5 3) :else 'ok)
> (key-if (> 3 1) :else 'oops)
> (key-if (> 3 1) :then)
> (key-if (> 3 1) :else 'oops :then 'ok)
> (key-if (> 3 1) :else 'oops :then (print 'hi) 'ok)

Lisp #3: MAKE-BALANCE (Wilensky, 12)

Define (make-balance initial-balance) to return a function that takes 0 or 1 arguments. If that function is called with 0 arguments, it returns the current balance. If called with 1 argument, which should be a number, it adds that number to the current balance, and returns the new balance.

> (setq bal (make-balance 100))
<a closure object>
> (funcall bal 10)
> (funcall bal -50)
> (funcall bal)

Lisp #4: DELETE-CAR (Wilensky, 15)

Define (delete-car list) to modify and return list with the first element of list deleted.

> (setq l (list 'a 'b 'c))
(A B C)
> (delete-car l)
(B C)
> L
(B C)

Note: it's impossible to destructively delete the only item in a list and turn it into NIL, but delete-car should at least return NIL in that case.

Lisp #5: COLLECT-NUMBERS (Wilensky, 15)

Define (collect-numbers s-exp) to return a list of all the numbers in the s-expression s-exp. s-exp may be an atom, a list, or a list of s-expressions.

> (collect-numbers 1)
> (collect-numbers 'a)
> (collect-numbers '(1 (b (2 c) ((3)))))
(1 2 3)

Implement this using a simple conditional, recursion, and MAPCAN. Letting MAPCAN do some of the work is more efficient than a pure CAR-CDR recursive solution. Don't worry about duplicate numbers in the result.

Lisp #6: TCONC (Wilensky, 15.7)

Adding elements to the end of a list is usually inefficient in Lisp:

A classic solution is to create a data structure called a tconc structure (for "tail concatenate"), which holds two pointers to the same list:

With this data structure, you can add new elements to the end of the list with just a few quick operations, no matter how long the list is, and you can still get the whole list whenever you need it.

Therefore, your job is to:

Note that you can get the internal list at any time with (tconc tconc-structure).

> (setq tc (make-tconc))
<tconc structure>
> (tconc tc 1)
> (tconc tc 2 3)
(1 2 3)
> (tconc tc)
(1 2 3)

Each successive call to tconc should be efficient, no matter how long the internal list has grown. One test of your tconc structure is that it always obeys the following rule:

(eq (last head-pointer) tail-pointer)

Lisp #7: LIST-OF

[ Inspired by Guy Lapalme's article in Lisp Pointers, Apr-Jun 91 ]

list-of is a macro that simplifies collecting lists of values of expressions. Though this description is long, and the macro is powerful, it's actually quite simple and can be implemented with relatively little code.

The general syntax is

(LIST-OF exp generator-or-filter generator-or-filter ...)

It's easiest to explain by starting with simple examples.

> (list-of (1+ x) (x :in '(1 2 3)))
(2 3 4)

exp is (1+ x) and (x :in '(1 2 3)) is a generator. A generator is anything that has the form (variable :in list). This generator generates three values for x, namely 1, 2, and 3. list-of returns a list of the value of (1+ x) for those three values of x.

> (list-of (1+ x) (x :in '(1 2 3)) (oddp x))
(2 4)

The exp and generator are as before, but now I've added the filter (oddp x). A filter is any expression that doesn't look like a generator. The filter says "keep only those values of x that are odd." Hence, list-of only collects values for (1+ x) equal to 1 and 3.

That's it. Any number of generators and filters can be given. They are applied from left to right. If there are two generators, the second repeats itself for every value created by the first, e.g.,

> (setq l '(a b))
(A B)
> (list-of (list x y) (x :in l) (y :in ))
((A A) (A B) (B A) (B B))

Likewise, the filters apply in order.

> (setq l '(1 2 3 4))
(1 2 3 4)
> (list-of (list x y) (x :in l) (oddp x) (y :in l) (evenp y))
((1 2) (1 4) (3 2) (3 4))

This collects (list x y) for every x in l that is odd and every y in l that is even. Notice that

> (list-of (list x y) (x :in l) (y :in l) (oddp x) (evenp y))
((1 2) (1 4) (3 2) (3 4))

returns the same answer, but does more work. Trace oddp to see the difference.

One special case that follows naturally:

Note: It'd be more direct to write "the list of x in l that are odd" as

(list-of (x :in l) (oddp x))

rather than

(list-of x (x :in l) (oddp x))

Define list-of so that if no initial expression to collect is given, it uses the variable of the first generator.

Our final examples are primarily for hard-core computer science types. You can skip them if you wish. Neither are particularly efficient, but they show the power of list-of.

To define a function that gets all the permutations of a list:

(defun perms (l)
  (if (endp l)
      (list nil)
      (list-of (cons a p)
         (a :in l)
         (p :in (perms (remove a l :count 1))))))

The list-of collects "(cons a p) for every a in l and every p in the permutations of l with a removed."

To define a simple unoptimized version of Quicksort:

(defun qsort (l)
  (if (endp l)
      (let ((a (car l)) (r (cdr l)))
        (append (qsort (list-of (x :in r) (< x a)))
                (list a)
                (qsort (list-of (x :in r) (>= x a)))))))

This splits l into those elements that are less than the car of l, and those that are greater, sorts each sublist recursively, and joins the results.

Comments? Send mail to Chris Riesbeck.