Martin Pomije wrote:
> I've dabbled with Lisp before, and I've worked my way through most of
> S&ICP, but I have decided to try a more systematic approach by working
> through Paul Graham's ANSI Common Lisp book.
> This is my code followed by my test cases for Exercise 3 on p. 56 of
> that book.
> <QOUTE>
> 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.
>>(occurences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))
> </QUOTE>
> ;;;; Ex. 3
> ;;; Takes a list of items and returns ab association list that
> indicates how
> ;;; many times each item occured, sorted with the maximum count at the
> ;;; head of the association list.
> (defun occurences (list)
> (if (consp list)
> (build-occurences () list)
> nil))
(defun occurrences (list &optional alist)
...)
and avoid the helper build-occurrences.
2. You could also just do:
(when (consp list)
...)
and get nil anyway if it is not consp.
> ;;;Steps through each item of the list and updates the alist
> ;;;with that item.
> (defun build-occurences (alist list)
> (if (null list)
> alist ; processed all items in list, so we're done.
> (build-occurences (update-count-alist (car list) alist) (cdr
> list))))
(if list ;; nil/not-nil ok as boolean
(occurrences ....)
alist)
> ;;; Updates the alist with the with respect to the symbol.
> (defun update-count-alist (symbol alist)
> (let ((first (car alist)))
> (if (null first)
> (list (cons symbol 1))
> (if (eql (car first) symbol)
> ;; the first item is a match
> (cons (cons symbol (+ (cdr first) 1))
> (cdr alist))
> ;; first item is not a match and alist has at least one record
> (scan-count-alist symbol alist)))))
> ;;; Steps through alist to update symbol assoc record.
> ;;; Assumes that the first item of the alist does not match symbol.
> ;;; Assumes alist has at least 1 assoc record.
> (defun scan-count-alist (symbol alist)
> (do* ((scan-position alist (cdr scan-position))
> (second (cadr scan-position) (cadr scan-position)))
> ((null second) ; scanned through alist, no occurences of item
> found
> (progn
> (setf (cdr scan-position) (cons (cons symbol 1) nil)) ; add
> record to the end
> alist))
> (if (eql (car second) symbol)
> (progn
> ;; delete old record for symbol
> (setf (cdr scan-position) (cddr scan-position))
> ;; insert updated record for symbol
> (return
> ;; alist should have at least 1 record because of the do*
> exit test
> (insert-count-alist (+ (cdr second) 1) symbol alist))))))
> ;;; Updates alist by inserting an assoc record for symbol.
> ;;; Assumes alist has at least 1 item.
> (defun insert-count-alist (count symbol alist)
> (if (>= count (cdar alist))
> (cons (cons symbol count) alist)
> (do* ((scan-point alist (cdr scan-point))
> (insertion-point (cdr scan-point) (cdr scan-point)))
> ((null insertion-point) ; assoc record needs to go at the end
> of the list
> (progn
> (setf (cdr scan-point) (cons (cons symbol count) nil))
> alist))
> (if (>= count (cdar insertion-point))
> (progn
> (setf (cdr scan-point)
> (cons (cons symbol count) insertion-point))
> (return alist))))))
is what I would recommend:
1. sort the list when you are done. destructively. write your own if
SORT is mentioned after page 56.
2. don't use recursion, iterate over the occurrences building up an
unsorted alist as you go, sort at the end by destructively relinking the
cons cells of the alist (a neat learning exercise itself).
Don't forget, once you have the matching alist entry, you can:
(incf (cdr entry))
But I realize you were maintaining the sort as you went by deleting the
prior entry and inserting a new entry with an incremented count. You
have done a lot of work here, and as long as you can write all this
code, go ahead and work out how to:
(let ((entry (find-entry new alist))
(if entry
(progn (incf (cdr entry))
(setf alist (maybe-move-up entry alist)))
(cons ... alist)
where you muck about with cars and cdrs and build some cons cell fluency.
3. as with sort, OK, assoc does not come before p56, but that does not
mean you cannot factor out the "find matching alist entry" functionality
in a roll-your-own assoc of some ilk and simplify the mainline.
kenny
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
