From Newsgroup: comp.lang.scheme

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))
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.scheme

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


--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.scheme

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!

Quite a few other disciples of CL commented on his post,
but not one pointed out that it didn't even begin to work
correctly.

This is a good example of their mentality. They are
all mediocre programmers, but each one assumes that
all disciples of CL are superb programmers.
They routinely and blindly accept and approve and
praise code that is completely worthless.
They are too lazy and stupid and arrogant to test the code.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.scheme

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.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.scheme

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


--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.scheme

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))
--- Synchronet 3.21a-Linux NewsLink 1.2