Count frequencies of symbols in a list
This is the typical situation where a hash table that maps elements to their frequency count is particularly well suited.

(defun occurrences (lst)
  (let ((table (make-hash-table)))                   ; [1]
    (loop for e in lst
          do (incf (gethash e table 0)))             ; [2]
    (sort (loop for k being the hash-key of table    ; [3]
                  using (hash-value v)
                collect (cons k v))                         
          #'&gt;= :key #'cdr)))                         ; [4]



We create the hash table: the key will be an element of the list, the value will be the frequency count. Note that it is not necessary to initialize it because the gethash function provide an initialization of the value for a key not already present in the table.
For each element of the list we increment (incf) the frequency value associated to it. This value is obtained by gethash, and if it is not yet in the table, it is initialized by default to 0 (the last parameter of gethash).
At the end, we use the “loop over hash table” syntax to collect all the pairs (key count) in a list, and we sort the list over the second element.


This solution is simple, very efficient and elegant.

If you want to use only lists, here is a solution that has the same complexity of the sorting algorithm:

(defun occurrences (lst)
  (if (null lst)                                            ; [1]
      nil
      (let ((sorted (sort (copy-list lst) #'string&lt;=)))     ; [2]
        (do ((c 1)                                          ; [3]
             (l (cdr sorted) (cdr l))                       ; [4]
             (el (car sorted) (car l))                      ; [5]
             (res nil))                                     ; [6]
            ((null l)                                       ; [7]
             (sort (cons (cons el c) res) #'&gt;= :key #'cdr)) ; [8]
          (if (eql (car l) el)                              
              (incf c)                                      ; [9]
              (progn
                (push (cons el c) res)                      ; [10]
                (setf c 1)))))))



If the list is empty return nil.
Sort the element by their names (assuming they are atoms), so that equal elements are contiguous.
Start a loop. The variabile c count how many equal elements are found (the frequency).
l is used to scan the sorted list. It starts from the second element of sorted.
el is the current element, while (car l) is the second one.
res is used to accumulate the result.
The iteration stops when l reaches the end of the list.
The result is obtained by adding the last couple (element, frequency) to the result, and sorting it by frequency.
The body of the loop: if the first element is equal to the second one increment the counter and continue to iterate.
Otherwise, a new element is found. So push the old one with its frequency on the result, and reset the counter to 1.