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: Mon, 7 Jul 2025 12:44:04 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 88
Message-ID: <104gfei$2u0dr$1@dont-email.me>
References: <104eaue$2am2p$1@dont-email.me> <104epf6$2ethv$1@dont-email.me> <104f7ad$2ick2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Mon, 07 Jul 2025 14:44:04 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="90eb80e27df105d047d6d87bc8fe395d";
	logging-data="3080635"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+SPyW+x1MVUZXTG00Ktc7+"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:KV2H9M7gKMO3xJKPivnMpXKx7hU=

B. Pym wrote:

> B. Pym wrote:
> 
> > 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!
> > 
> > 
> > The testing was done under SBCL.  Perhaps the function
> > will work correctly under another version of CL.
> > In any case, this is questionable code.
> 
> Here's a version in CL that follows Naggum's lead
> by avoiding recursion.
> When an item in the list that is currently being
> processed is found to be a list, it is pushed
> onto the list of trees.
> 
> (defun count-member (symbols tree)
>   (let ((counts (mapcar (lambda(s) (cons s 0)) symbols))
>         (trees (list tree)))
>     (do () ((null trees)) ;; Until trees is empty.
>       (dolist (x (pop trees))
>         (cond ((consp x) (push x trees))
>               (t (let ((found (assoc x counts)))
>                     (if found (incf (cdr found))))))))
>     counts))
> 
> Under SBCL:
> 
> * (count-member '(w x y z) '(a x (b y y (z) z)))
> 
> ((W . 0) (X . 1) (Y . 2) (Z . 2))
>  

In Gauche Scheme:

(define (count-member symbols tree)
  (let ((counts (map (cut  cons <> 0) symbols))
        (trees (list tree)))
    (do () ((null? trees)) ;; Until trees is empty.
      (dolist (x (pop! trees))
        (cond ((pair? x) (push! trees x)) ;; Arg. order different from CL.
              ((assoc x counts) =>
               (lambda(f) (inc! (cdr f)))))))
    counts))