From: Levi Conley
Subject: Simple NEWBIE stuff...
Date: 
Message-ID: <ff18f689.0111021325.c6ab04c@posting.google.com>
Looking for an expert to pick apart the following code snippet and
"give me some good lernin!" :)

Harsh, constructive criticism with regard to style, logic, and syntax
is perfectly welcome.

The following is an initial attempt to solve a problem in P. Graham's
Ansi Common Lisp book (this is not HW!):

Corman Lisp 1.5  Copyright � 2001 Roger Corman. All rights reserved.
(defun occurrences (lst)
   (let ((occlist ()))
      (dolist (obj lst)
         (let* ((itm (assoc obj occlist)) (cnt (first (rest itm))))
            (if (equal itm NIL)
		(setf occlist (cons (cons obj '(1)) occlist))
		(setf (first (rest itm)) (+ cnt 1)))
            (format t "itm= ~A " itm)))
      (format t "~%")
      occlist))
OCCURRENCES
(occurrences '(a a b b c c))
itm= NIL itm= (A 2) itm= NIL itm= (B 3) itm= NIL itm= (C 4) 
((C 4) (B 4) (A 4))


What's supposed to happen is each different element of the input list
is added up and a new list (occlist) constructed with this info.  It
looks to me as though the local variable cnt is not being reset each
time through dolist, and I do not understand why.

Also, any hints on how to sort the final occlist based on number of
occurrences would be appreciated.

Thanks

From: Tim Moore
Subject: Re: Simple NEWBIE stuff...
Date: 
Message-ID: <9rv47q$d5o$0@216.39.145.192>
In article <···························@posting.google.com>, "Levi Conley"
<···············@cs.com> wrote:


> Looking for an expert to pick apart the following code snippet and "give
> me some good lernin!" :)
> Harsh, constructive criticism with regard to style, logic, and syntax is
> perfectly welcome.
> The following is an initial attempt to solve a problem in P. Graham's
> Ansi Common Lisp book (this is not HW!):  Corman Lisp 1.5  Copyright �
> 2001 Roger Corman. All rights reserved. (defun occurrences (lst)
>    (let ((occlist ()))
>       (dolist (obj lst)
>          (let* ((itm (assoc obj occlist)) (cnt (first (rest itm))))
>             (if (equal itm NIL)
> 		(setf occlist (cons (cons obj '(1)) occlist)) (setf (first (rest itm))
This line is your problem... see below.
> 		(+ cnt 1)))
>             (format t "itm= ~A " itm)))
>       (format t "~%")
>       occlist))
> OCCURRENCES
> (occurrences '(a a b b c c))
> itm= NIL itm= (A 2) itm= NIL itm= (B 3) itm= NIL itm= (C 4) ((C 4) (B 4)
> (A 4))
> What's supposed to happen is each different element of the input list is
> added up and a new list (occlist) constructed with this info.  It looks
> to me as though the local variable cnt is not being reset each time
> through dolist, and I do not understand why.  Also, any hints on how to
> sort the final occlist based on number of occurrences would be
> appreciated.

You're creating the sublist that holds the count from the same quoted
list, and that's shared among all the elements.   That's why the final
count is 4 everywhere.

If you're going to use alists, use alists :)  An alist element is
typically a single cons cell, not a list.  Then you can use some
convenience function like ACONS.

This is what I'd do:
(defun occurrences (list)
  (let ((occlist nil))
    (dolist (obj list)
      (let ((item (assoc obj occlist)))
	(if item
	    (incf (cdr item))
	  (setq occlist (acons obj 1 occlist)))))
    occlist))
cl-user(1): (occurrences '(a a b b cc))
((cc . 1) (b . 2) (a . 2))

Actually, I'd probably explore using a hash table instead of an alist.

Tim
From: Kenny Tilton
Subject: Re: Simple NEWBIE stuff...
Date: 
Message-ID: <3BE34E70.D946ED31@nyc.rr.com>
Levi Conley wrote:
> 
> Looking for an expert to pick apart the following code snippet and
> "give me some good lernin!" :)
> 
> Harsh, constructive criticism with regard to style, logic, and syntax
> is perfectly welcome.
> 
> The following is an initial attempt to solve a problem in P. Graham's
> Ansi Common Lisp book (this is not HW!):
> 
> Corman Lisp 1.5  Copyright � 2001 Roger Corman. All rights reserved.
> (defun occurrences (lst)
>    (let ((occlist ()))

this could be just: (let (occlist)...no big deal, and some might find
your version more readable

>       (dolist (obj lst)
>          (let* ((itm (assoc obj occlist)) (cnt (first (rest itm))))
>             (if (equal itm NIL)

that could be (if (null itm)... or (if (not itm)... or switch consequent
paths and go with (if itm ...

>                 (setf occlist (cons (cons obj '(1)) occlist))

that could be: (push (cons obj 1) occlist)

note that this is two suggestions (1) use push and (2) store the count
in the cdr directly, not as a list.

>                 (setf (first (rest itm)) (+ cnt 1)))

that could be: (incf (cdr item)) [given the change to (cons obj 1) vs
(cons obj (list 1))

>             (format t "itm= ~A " itm)))
>       (format t "~%")

shucks, just return the value and test it in the debugger/listener
window, that will echo the result

>       occlist))

you can return the value with (dolist (obj lst occlist)...

also, if you are going to abbreviate list as lst be consistent about it
and use occlst:

(defun occurrences (lst &aux occlst)
   (dolist (obj lst occlst)
      (let ((itm (assoc obj occlst)))
          (if itm
              (incf (cdr itm))
              (push (cons obj 1) occlst)))))

> 
> Also, any hints on how to sort the final occlist based on number of
> occurrences would be appreciated.

Hint: use sort. :)

BTW, could you have used #'count?

(defun occurrences (lst)
  (maplist #'(lambda (cell)
               (rplaca cell (cons (car cell)
                                  (count (car cell) lst))))
           (remove-duplicates lst)))

kenny
clinisys
From: Bernhard Pfahringer
Subject: Re: Simple NEWBIE stuff...
Date: 
Message-ID: <9s4jvm$l6b$1@hummel.cs.waikato.ac.nz>
In article <···························@posting.google.com>,
Levi Conley <···············@cs.com> wrote:
>
>What's supposed to happen is each different element of the input list
>is added up and a new list (occlist) constructed with this info.  It
>looks to me as though the local variable cnt is not being reset each
>time through dolist, and I do not understand why.
>
>Also, any hints on how to sort the final occlist based on number of
>occurrences would be appreciated.
>

A loop-based solution:

(defun occurences (items)
  (let ((ht (make-hash-table :test #'equal)))
    (loop for item in items
	  do (incf (gethash item ht 0)))
    (sort (loop for key being the hash-keys of ht
		using (hash-value value)
		collect (cons key value))
	  #'< :key #'rest)))

Bernhard
-- 
---------------------------------------------------------------------
Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard                  +64 7 838 4041
---------------------------------------------------------------------
From: Steve Long
Subject: Re: Simple NEWBIE stuff...
Date: 
Message-ID: <3BE7919D.97B27424@isomedia.com>
You can use Bernard's basic loop to make this work on vectors (loop
across ...) as well, but lose the hash table (unless creating a new slot
in a table is less expensive than a new item in a list in your Lisp
system), pass the equality test function as a keyword argument defaulted
to #'eql, and an extraction function defaulting to #'identity. This will
make the function more generic. If you want to sort within the function,
pass #'< (default) or #'> as an arg as well. Sort with the general form
(sort VAL-AND-QTY-PAIRS SORT-DIR :key #'second).

sl

Bernhard Pfahringer wrote:

> In article <···························@posting.google.com>,
> Levi Conley <···············@cs.com> wrote:
> >
> >What's supposed to happen is each different element of the input list
> >is added up and a new list (occlist) constructed with this info.  It
> >looks to me as though the local variable cnt is not being reset each
> >time through dolist, and I do not understand why.
> >
> >Also, any hints on how to sort the final occlist based on number of
> >occurrences would be appreciated.
> >
>
> A loop-based solution:
>
> (defun occurences (items)
>   (let ((ht (make-hash-table :test #'equal)))
>     (loop for item in items
>           do (incf (gethash item ht 0)))
>     (sort (loop for key being the hash-keys of ht
>                 using (hash-value value)
>                 collect (cons key value))
>           #'< :key #'rest)))
>
> Bernhard
> --
> ---------------------------------------------------------------------
> Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
> http://www.cs.waikato.ac.nz/~bernhard                  +64 7 838 4041
> ---------------------------------------------------------------------