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