6
\$\begingroup\$

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)))))
\$\endgroup\$
  • 3
    \$\begingroup\$ I think this should be on codereview.se rather than stack overflow. \$\endgroup\$ – Dan Robertson Mar 18 '19 at 9:50
  • \$\begingroup\$ ok - should i delete it from here then? \$\endgroup\$ – mwal Mar 18 '19 at 12:19
  • \$\begingroup\$ 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 \$\endgroup\$ – user90823 Mar 18 '19 at 14:49
  • \$\begingroup\$ 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)". \$\endgroup\$ – Ludisposed Mar 18 '19 at 14:57
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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)); \$\endgroup\$ – davypough Mar 25 '19 at 18:06
  • \$\begingroup\$ 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). \$\endgroup\$ – davypough Mar 25 '19 at 18:06
  • \$\begingroup\$ Thanks, @davypough, very interesting comments! \$\endgroup\$ – Renzo Mar 25 '19 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.