Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.scheme > #6482

Re: count symbols in a list

Cross-posted to 2 groups.

Show all headers | View raw

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

Back to comp.lang.scheme | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: count symbols in a list "B. Pym" <Nobody447095@here-nor-there.org> - 2025-07-06 17:14 +0000
  Re: count symbols in a list "B. Pym" <Nobody447095@here-nor-there.org> - 2025-07-06 19:30 +0000
    Re: count symbols in a list "B. Pym" <Nobody447095@here-nor-there.org> - 2025-07-06 19:55 +0000
  Re: count symbols in a list "B. Pym" <Nobody447095@here-nor-there.org> - 2025-07-06 21:22 +0000
    Re: count symbols in a list "B. Pym" <Nobody447095@here-nor-there.org> - 2025-07-07 01:19 +0000
      Re: count symbols in a list "B. Pym" <Nobody447095@here-nor-there.org> - 2025-07-07 12:44 +0000

csiph-web