Occurrences (frequency count) - exercise 3 ch. 3 in "ansi common lisp"

Question

Looking for hints on style and clarity re. below. While I'm not saying speed is irrelevant, it's less of a priority than style & avoiding bad habits at this point. Focus is on clean use of fundamentals of the language.

Summary of task:

Take a list and return a list indicating the number of times each (eql) element appears, sorted from most common element to least common."

Example run with required output:

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

My solution:

(defun occurrences (lst)
  "Takes a list and returns a list indicating the number of times each (eql)
   element appears, sorted from most common element to least common."
  (occurrences2 lst (mapcar #'(lambda (x) (cons x 0))
                            (remove-dups lst))))

(defun occurrences2 (lst res)
  "Update res, an alist which already contains all needed entries with all
   values set to zero, with frequencies of occurrence as found in lst"
  (if (null lst)
      res ; todo: add a sort here on cdr of each element
      (occurrences2 (cdr lst)
                    (mapcar #'(lambda (x)
                            (if (eql (car x) (car lst))
                                (cons (car x) (+ (cdr x) 1))
                                x))
                         res))))

(defun remove-dups (lst)
  (if (null lst)
      nil
      (adjoin (car lst) (remove-dups (cdr lst)))))

Answer 1

Use primitive functions and operators as much as possible

You are defining remove-dups, and in this function you use the primitive adjoin, which adds an element to a list if not already present. But in Common Lisp the primitive function remove-duplicates is also available, that returns a list without duplicates.

Instead of (+ expression 1) use the primitive 1+ function: (1+ expression).

To iterate over a list there are convenient primitives iterative constructs, like dolist and loop (see below).

Alists

If you want to use alists, it can be more clean to use the primitive operators already defined on them, like acons, pairlis, assoc. For instance, the program could be simplified in this way:

(defun occurrences (lst)
  (let* ((elements (remove-duplicates lst))
         (alist (pairlis elements (make-list (length elements) :initial-element 0))))
    (loop for x in lst
          do (incf (cdr (assoc x alist))))
    alist))

Note that the counters inside the alist are incremented with incf; in fact another suggestion of mine is “don’t by shy to use modifying primitives”, when you are modifying things locally to some function and are sure no undesirable side-effects arise.

Hash tables

Another suggestion is: use the data structures for the task at hand. In Common Lisp there are hash tables, which are ideal for problems like yours. For instance:

(defun occurrences (lst)
  (let ((table (make-hash-table)))
    (loop for x in lst
          do (incf (gethash x table 0)))
    (loop for k being the hash-key of table
          using (hash-value v)
          collect (cons k v))))

This is of course the most efficient solution of all, since it is of O(n), and it scans only once the input list. At the end you could sort the elements returned by their car, and remember always that all the primitive functions that need to do comparisons use by default eql but can be called with an extra keyword parameter :test to chose another comparison predicate, as for instance equal to compare complex values as lists. This applies to remove-duplicates, assoc and make-hash-table.