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 17:14:56 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <104eaue$2am2p$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Sun, 06 Jul 2025 19:14:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="6946e6d5bd1474bb6d64b1a7e7254585";
	logging-data="2447449"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19qIIPql+X7EupnD+QompLc"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:ktokJFlq0XAmK2MAsSbT+4sNy68=

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!


It's easier when one uses a Lispy language instead of CL.

Gauche Scheme

(define (count-member symbols tree)
  (let1 counts (map (cut  cons <> 0) symbols)
    (define (tally tree)
      (dolist (x tree)
        (if (pair? x)
          (tally x)
          (let1 found (assoc x counts)
            (when found (inc! (cdr found)))))))
    (tally tree)
    counts))

(count-member '(w x y z) '(a x (b y y (z) z)))

  ===>
((w . 0) (x . 1) (y . 2) (z . 2))