Re: count symbols in a list

B. Pym wrote:

Erik Naggum wrote:
 

 I want to write a function that takes a list of symbols k and and lisp
 expression l and counts the number of times each symbol in k occurs in
 the lisp expression. It should return an alist binding each symbol to its
 count.  I want to do this without flattening the list before I go through
 it looking for symbols.

 
  Look for two things in this code: How it is formatted, and how it does
  its work.  (The way you have formatted your code annoys people.)  Explain
  to me why this works and gives the right answer when you have ascertained
  that it does.  Explain why it is efficient in both time and space.
 
(defun count-member (symbols tree)
  (let* ((counts (loop for symbol in symbols collect (cons symbol 0)))

 
Why didn't he use the simpler "mapcar" instead of "loop"?
Example:
 
(mapcar (lambda(s) (cons s 0)) '(a b c))
  ===>
((A . 0) (B . 0) (C . 0))
 
 

         (lists (list tree))
         (tail lists))
    (dolist (list lists)
      (dolist (element list)
        (cond ((consp element)
               (setf tail (setf (cdr tail) (list element))))
              ((member element symbols :test #'eq)
               (incf (cdr (assoc element counts :test #'eq)))))))
    counts))

 
 
Testing:
 
* (count-member '(w x y z) '(a x (b y y (z) z)))
 
((W . 0) (X . 1) (Y . 0) (Z . 0))
 
It only counts the top-level symbols!
 

Looking at the code, it seems that he tried to avoid recursion
by continually modifying the list over which he was iterating.
Let's try it that way.

Gauche Scheme

;; Using list-copy to remove immutability.
(define (count-member symbols tree)
  (let ((counts (map (cut  cons <> 0) symbols))
        (tree (list-copy tree)))
    (dolist (x tree)
      (cond ((pair? x)
             (set! tree (append! tree (list-copy x))))
            (#t (let1 found (assoc x counts)
                  (if found (inc! (cdr found)))))))
    counts))

(count-member '(w x y z) '(a x (b y y (z) z)))
  ===>
((w . 0) (x . 1) (y . 2) (z . 2))