Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "B. Pym" <Nobody447095@here-nor-there.org>
Newsgroups: comp.lang.lisp,comp.lang.scheme
Subject: Re: count symbols in a list
Date: Sun, 6 Jul 2025 19:30:29 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 68
Message-ID: <104eisk$2d5qt$1@dont-email.me>
References: <104eaue$2am2p$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Sun, 06 Jul 2025 21:30:30 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e9607d0181b6eedff585ea84ac51b55a";
	logging-data="2529117"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+zJ7Sg/p+kpxTyJGfIDjwy"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:98GSwzWSMZ5gExHzKVZ6cpfU+J0=

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