Re: ANSI Common Lisp, Ch 3, Ex 3


"Jason" <jemeade@xxxxxxxxx> wrote in message news:1141272452.925621.101240@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I'm learning Lisp just for fun using Paul Graham's book, "ANSI Common
Lisp". I'm determined to master each chapter before progressing to the
next. Having said that, on page 56 there is the following problem:

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

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

Well, this "simple" task has been driving me crazy! I must have spent
at least 10 hours working on it. Having said that, I SOLVED IT!!! :)

Great!

Here's my solution:

(setq input '(a b a d a c d c a))

Ok, general consensus is to use the macro SETF over
the special form SETQ, since SETF is more general.

Also, using SET[*] at top level requires undefined
behaviour (although in every implementation I've seen
it works) so it's better to use DEFVAR or DEFPARAMETER
instead.

Lastly, top-level variables are special, they behave
differently than variables declared in a LET, so
it's good practice to give them special names the
standard being to surround them with asterisks.

(DEFVAR *INPUT* '(a b a d a c d c a))

(defun occurences (input-list)
(let ((sorted-list (sort (copy-sequence input-list) 'string<))
(a-list nil))
(setq a-list (occurences-make-alist () sorted-list))
(occurences-sort-alist a-list)))

STRING< is a bad idea, it's defined to work on strings.
Try (OCCURENCES '(1 2 3 1 2 3 1 2 3 4)). Well done on
the COPY-SEQUENCE, you've been paying attention.

(defun occurences-sort-alist (a-list)
(sort a-list 'occurences-greater))

As another practice note: I prefer #' to '.
Makes it easier to spot the reference to
a function rather than just a quoted symbol.
OTOH, I no longer use #'(LAMBDA ...) just (LAMBDA ...)

(defun occurences-greater (node-1 node-2)
(> (cdr node-1) (cdr node-2)))

Others have pointed out that SORT takes an optional
key argument.

(SORT A-LIST #'> :KEY #'CDR)

(defun occurences-make-alist (a-list sorted-list)
(let ((node nil)
(remainder nil))
(if (not (null sorted-list))
(progn
(setq node (occurences-get-token-cons sorted-list))
(setq remainder (occurences-remainder node sorted-list))
(setq a-list (append a-list node (occurences-make-alist a-list
remainder)))))
a-list))

Just a performance note, if you are faced with a choice
of making a list bigger by using APPEND to add an element
to the end of the list or using CONS on the front, CONS
is almost always the winner because APPEND has to go all
the way through the list to find the end. If order is
important you can always REVERSE or NREVERSE the list
when you're done.

(defun occurences-remainder (node sorted-list)
(if (null node)
sorted-list
(subseq sorted-list (cdr (car node)))))

(defun occurences-get-token-cons (sorted-list)
(if (null sorted-list)
nil
(progn
(let ((tok (car sorted-list)) (count 1))
(setq count (occurences-get-token-count tok count (cdr sorted-list)))
(list (cons tok count))))))

(defun occurences-get-token-count (token count input-list)
(if (eql token (car input-list))
(setq count (+ count (occurences-get-token-count token count (cdr
input-list)))))
count)

(occurences input)

;;; END

And, it works! :)

Ok, my version :)

(defun occurences(list)
(let ((counts (make-hash-table :test #'eql)))
(dolist (item list) (incf (gethash item counts 0)))
(sort (loop for key being the hash-keys
in counts using (hash-value count)
collect (cons key count))
#'> :key #'cdr)))

If you haven't yet, download a copy of the hyperspec, you
can find one at www.lispworks.com , it's a wonderful resource.

--
Geoff


.

Relevant Pages

  • Re: NIL is not of type CONS
    ... not a cons *because* cons cells are based on logic. ... Either immutable cons cels or proper cons cells ... training people to use lists on a simpler kind of list than the full ...
    (comp.lang.lisp)
  • Re: the sort function in lisp (destructive)
    ... As for SORT Robert Maas posted a small hack that would preserve the head ... cons after calling the implementation's SORT in SORT-KEEPING-HEAD-CELL ... then splice the user's head cell back in after sorting. ...
    (comp.lang.lisp)
  • Re: NIL is not of type CONS
    ... Pascal's and your suggestions of using 'list instead of 'cons ... head is still bothering me that the degenerate case (NIL) should be ... or (member nil) or most simply null ... assigning subtypes apparently is not always possible. ...
    (comp.lang.lisp)
  • Re: Lisp is a Write-Only like Perl or Forth
    ... you descent the trie to be unique. ... still fresh in my head. ... In CL an association list can contain NIL, ... (cons nil pure-alist) ...
    (comp.lang.lisp)
  • Re: NIL is not of type CONS
    ... legacy code I found on the web so I assumed the code was stable and ... In fact, the type NIL is a subtype of every other type, even itself! ... I suspect what you want is for the type NULL to be a subtype of CONS ...
    (comp.lang.lisp)