# Occurrences (frequency count) - exercise 3 ch. 3 in “ansi common lisp”

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.

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)))))


## migrated from stackoverflow.comMar 18 at 14:52

This question came from our site for professional and enthusiast programmers.

• I think this should be on codereview.se rather than stack overflow. – Dan Robertson Mar 18 at 9:50
• ok - should i delete it from here then? – mwal Mar 18 at 12:19
• If you are going to post it on another stack exchange site, then you do need to delete it here first. Always check the help centre to see what's on topic – Yvette Colomb Mar 18 at 14:49
• Welcome, to get the best out of CodeReview, please add an summery of the task you are trying to solve, and don't omit anything "(works, omitting the sort)". – Ludisposed Mar 18 at 14:57

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.

• Nice comparison of alist & hashing approaches. Also of note: 1) Although the original problem only requires eql elements, alists automatically allow any lisp object as key, whereas hashing requires a priori specification of the key test (worst case equalp); 2) In line with not being shy about modifying primitives, the alist approach might be simplified and speeded up by incrementally constructing and destructively modifying the resulting alist by using something like (let ((pair (assoc x alist))) (if pair (rplacd pair (incf (cdr pair))) (push (cons x 1) alist)); – davypough Mar 25 at 18:06
• 3) You can generalize the alist solution to accept any sequence of objects as input by using the :iterate library, which allows a driver like (for x in-sequence lst). – davypough Mar 25 at 18:06
• Thanks, @davypough, very interesting comments! – Renzo Mar 25 at 18:10

What I would do here in terms of design pattern is use a hash-table to capture the number of occurrences of each element and then increment it. I know that during chapter three the loop macro hasn't even been covered yet, although it is fine. I know that many Lispers prefer iterators such as do or do list, considering those macros more closely resemble the Common Lisp syntax. Here is an example of a design that can solve the problem:

(defun occurrences(lst)
(let((ht(make-hash-table)))
(let((holder nil))
(dolist(x lst)
(if(not(member x holder :test #'eq))
(progn
(push x holder)
(setf (gethash x ht) 1))
(setf (gethash x ht)(+ 1 (gethash x ht)))))
(let((holder2 nil))
(dolist(tr holder)
(push (cons tr (gethash tr ht))holder2))
(sort holder2 #'> :key #'cdr)))))


And here we test it:

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


Here we simply create a hash-table and then a holder (list) for the values in the hash-table. If you wanted to, you could create an if or cond statement that says if that key exists increment 1 to the value, or if it doesn't exist set the value to 1+current-value. But instead I thought it'd be similar to simply create an empty list and push the elements to the list to test if we've already seen that element before. If the element is not a member of the list, we can push it to our holder list, and then we can create a key-value pair in our hash-table (with the key being the element and the value being the number of times it's occurred. If it does exists, we simply reset the value of that key to 1+ the previous value. We then create a second holder that we will use to push the key value pairs to. We then use sort in order to sort the list by the cdr of each of the assoc-lists we now have in the holder2 list. That is what will return.

I used this design pattern because I believe that this is all Graham has covered up to chapter 3 in the book. If I recall, the Loop macro isn't covered until an optional chapter later on, and many Lispers do not use the Loop macro at all since it's syntax isn't very Lispy (by design). The idea of a hash-table makes sense here as well since you are only counting individual elements and then incrementing how many times they occur. Sort is also useful here since you have to sort them by the number of occurrences.

• It would be great if you would use standard Lisp coding conventions: use spaces after/before parentheses where useful, don't name variables like in Scheme (LIST vs LST). Very important: indent your code correctly. This would greatly improve the readability of your code. – Rainer Joswig Mar 19 at 8:50
• It's literally indented. I use emacs. There's literally no convention in which you name a list (lst) by default, especially if you have multiple lists in the same scope... So maybe what you're saying is going over my head or I'm missing something? This is literally indented within emacs. I always use the IDE. I didn't use like notepad – Simeon Ikudabo Mar 19 at 14:52
• That can't be: example the DOLIST in the third line should be differently indented. The line after the first DOLIST is also not correctly indented. Correctly indented formatted version of your code: gist.github.com/lispm/adddb10bea51539db1b162d52eb1c323 – Rainer Joswig Mar 19 at 14:54
• The dolist in the third line is within a let statement, so it has to be indented within it. That looks accurate to me, and that's specifically what it looks like in emacs. Theoretically, it sounds like you don't like the IDE, which is fine. – Simeon Ikudabo Mar 19 at 15:18
• The IF in the fifth line and its whole block is wrongly indented. The DOLIST in the 11th line is wrong indented incl the PUSH. See your code above. See my gist I linked for a correctly indented version of your code. If your Emacs indents it that way, then you might check that you use spaces and not tabs for indentation. Stackoverflow does not use tabs for indentation, IIRC. So you need to paste code without tabs, but with spaces, so that indentation looks correct in Stackoverflow. – Rainer Joswig Mar 19 at 15:21