ACL Chapter 3

Chris Riesbeck of Northwestern has some criticisms on Graham's coding style. Some of the examples he cites were unclear to me as well at first read.

On to ACL chapter 3 exercises:

1. Show the following lists in box notation:

I did them, but I just am not good enough with LaTeX to show the box notations.

2. Write a version of union that preserves the order of the elements in the original lists:

> (new-union '(a b c) '(b a d))
(A B C D)

(defun new-union (list1 list2)
  (let ((lst list2))
    (dolist (obj list1)
      (setf lst (remove obj lst)))
    (append list1 lst)))

3. Define a function that takes a list and returns a list indicating the number of times each (eql) element appears, sorted from most common element to least common:

> (occurrences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1))

(defun occurrences (lst)
  (let ((freq-list nil)
        (uniq-list (remove-duplicates (copy-list lst) :test #'eql)))
    (dolist (elem uniq-list)
      (push (cons elem (count elem lst)) freq-list))
    (sort (copy-list freq-list) #'> :key #'cdr)))

4. Why does (member '(a) '((a) (b))) return nil?

member, by default, compares objects using eql, which returns true only if its arguments are the same object. While there appear to be (a) in both lists, each is a distinct object and eql would return nil (equal, however, would return T).

5. Suppose the function pos+ takes a list and returns a list of each element plus its position:

> (pos+ '(7 5 1 4))
(7 6 3 7)

Define this function using (a) recursion, (b) iteration, (c) mapcar.

(defun pos+ (lst) ;recursion
  (pos+recourse lst 0))

(defun pos+recourse (lst pos)
  (if lst       
      (cons (+ (car lst) pos) (pos+recourse (cdr lst) (+ pos 1)))))

(defun pos+ (lst) ;iteration
  (let ((pos -1)
 (output-lst nil))
    (dolist (elem lst)
      (push (+ elem (incf pos)) output-lst))
    (reverse output-lst)))
    
(defun pos+ (lst) ;mapcar
  (let ((pos -1))
    (mapcar #'(lambda (x) (+ x (incf pos))) lst)))

6. After years of deliberation, a government commission has decided that lists should be represented by using the cdr to point to the first element and the car to point to the rest of the list. Define the government versions of the following functions:
(a) cons
(b) list
(c) length (for lists)
(d) member (for lists; no keywords)

(defun govt-cons (obj1 obj2)
  (let ((lst '(nil . nil)))
    (setf (cdr lst) obj1)
    (setf (car lst) obj2)
    lst))

(defun govt-list (&rest lst)
  lst)

(defun govt-length (lst)
  (if (null lst)
      0
      (+ (govt-length (car lst)) 1)))

(defun govt-member (obj lst)
  (if lst
      (if (eql (cdr lst) obj)
   lst
   (govt-member obj (car lst)))))

7. Modify the program in Figure 3.6 to use fewer cons cells. (Hint: Use dotted lists.)

Only one word needs to be changed in n-elts:

(defun compress (x)
  (if (consp x)
      (compr (car x) 1 (cdr x))
      x))

(defun compr (elt n lst)
  (if (null lst)
      (list (n-elts elt n))
      (let ((next (car lst)))
 (if (eql next elt)
     (compr elt (+ n 1) (cdr lst))
     (cons (n-elts elt n)
    (compr next 1 (cdr lst)))))))

(defun n-elts (elt n)
  (if (> n 1)
      (cons n elt) ; this is the only change
      elt))

8. Define a function that takes a list and prints it in dot notation:

> (showdots '(a b c))
(A . (B . (C . NIL)))
NIL

(defun showdots (lst)
  (FORMAT T "~A" (showdots-recourse lst)))

(defun showdots-recourse (lst)
  (if (not (null lst))
      (if (atom lst)
   lst
   (format nil "(~A . ~A)"
    (showdots-recourse (car lst))
    (showdots-recourse (cdr lst))))))

9. Write a program to find the longest finite path through a network represented as in Section 3.15. The network may contain cycles.

Answer9

Chapter 3 is done.