My solutions to the exercises in Chapter 3 of Paul Graham's ANSI Common Lisp. If you have suggestions for how to improve any of these, please email me at user name lispsolutions using the domain name of this web site.

3.1

(a)

(b)

(c)

(d)

3.2

(defun new-union (a b)
       (if (null b)
           a
           (new-union (if (member (car b) a)
                          a
                          (append a (list (car b)))
                      (cdr b))))

3.3

(defun occurrences (l)
       (sort (count-oc l nil) (lambda (a b) (> (cdr a) (cdr b)))))

(defun count-oc (in out)
       (if (null in)
           out
           (let* ((tok (car in)) (add-to-out (assoc tok out)) (new-out (remove add-to-out out)))
                 (count-oc (cdr in)
                           (append (list (if (null add-to-out)
                                             (cons tok 1)
                                             (cons tok (+ 1 (cdr add-to-out)))))
                                    new-out)))))

3.4

The default comparison for #'member is #'eql. While '(a) and '(a) are #'equal, they are not #'eql.

3.5

(a)

(defun pos+r (ll) (pos+r-w ll 0))

(defun pos+r-w (ll nn)
       (if (null ll) 
           nil
           (cons (+ nn (car ll)) (pos+r-w (cdr ll) (+ 1 nn)))))

(b)

(defun pos+i (ll)
       (let ((nn 0) (out nil))
            (dolist (elem ll out) (setq out (cons (+ nn elem) out)) (setq nn (+ 1 nn)))))

(c)

(defun pos+m (ll)
       (let ((nn -1))
            (mapcar #'(lambda (elem) (setq nn (+ 1 nn)) (+ nn elem)) ll)))

3.6

(a)

(defun gcons (obj1 obj2) (cons obj2 obj1))

(b)

According to the errata, this can't be done without using the 'rest' parameter, which isn't introduced for another 50 pages.

(c)

3.8

(defun showdots (ll)
       (if (null ll)
           (format t "nil")
           (progn
               (format t "(~A ." (car ll))
               (showdots (cdr ll))
               (format t ")"))))