Counting occurences
in [Lisp]
|
Prev: Black-Jewish History FAQ - Is The Secret Relationship between blacks and jews a “hate literature”?
Next: which library to generate xml with namespaces?
From: RG on 17 Jun 2010 18:48 In article <87vfr3Ft2dU1(a)mid.individual.net>, Eric Wolf <eric(a)boese-wolf.eu> wrote: > Hello there! > > I'm starting to learn lisp and doing the exercises of Ansi Common Lisp > authored by Paul Graham. > > So my solution to counting occurences in a list and outputting a > list of dotted pairs (symbol . count) sorted by count is > > (defun occurences-helper (lst result) > (if (null lst) > result > (progn > (let ((symb (car lst))) > (let ((test (assoc symb result))) > (if test > (setf (cdr test) (+ (cdr test) 1)) > (setf result (cons (cons symb 1) result))))) > (occurences-helper (cdr lst) result)))) > > (defun occurences (lst) > (sort > (occurences-helper lst ()) > #'(lambda (x y) > (> > (cdr x) > (cdr y)))) > ) > > > And I thought: "Hmm that doesn't look elegant" but I'm not used to > recursion and functional programming and that stuff so I didn't > came up with a better version. > > Maybe some experienced lisp hacker may provide a different one? > > Yours sincerely, > > Eric IMHO a better way to approach this, particular for beginners, is to use abstract associative maps rather than association lists. A CL implementation of abstract associative maps can be found here: http://www.flownet.com/ron/lisp/dictionary.lisp You'll also need the rg-utils.lisp file. Once you have abstract associative maps, you can make an occurrence counter trivially: (require :dictionary) (defclass counter (dictionary) ()) (defmethod add ((c counter) item) (setf (ref c item) (1+ (ref c item 0)))) (defun count-items (list) (let ((c (make-instance 'counter))) (dolist (item list) (add c item)) c)) ? (count-items '(one two two three three three)) #<COUNTER HASH-TABLE { ONE 1 TWO 2 THREE 3 }> Sorting the output is left as an exercise. rg
From: Zach Beane on 17 Jun 2010 19:04 RG <rNOSPAMon(a)flownet.com> writes: > (defmethod add ((c counter) item) > (setf (ref c item) (1+ (ref c item 0)))) Does (incf (ref c item 0)) work? Zach
From: RG on 17 Jun 2010 19:14 In article <87fx0ls1lm.fsf(a)hangup.portland.xach.com>, Zach Beane <xach(a)xach.com> wrote: > RG <rNOSPAMon(a)flownet.com> writes: > > > (defmethod add ((c counter) item) > > (setf (ref c item) (1+ (ref c item 0)))) > > Does (incf (ref c item 0)) work? > > Zach No. REF is a macro that expands into a call to the generic function REF1 if no default argument is specified, or REFD if a default is specified. If you look at the code for the HISTOGRAM class you'll see that the call to REFD is actually there explicitly. (I took it out when I posted here in the hopes of making it less confusing.) There is no SETF method for REFD, only for REF1. I could add a setf method for REFD, but the overall goal of this code is to make pedagogy a top priority, and I am waffling over whether having a SETF method for REFD makes things clearer or more confusing. On the one hand, it would allow code like this to be written even more concisely, but on the other hand SETFing REFD doesn't really make semantic sense. Actually, outside opinions on this would be welcome. rg
From: Zach Beane on 17 Jun 2010 19:36 RG <rNOSPAMon(a)flownet.com> writes: > In article <87fx0ls1lm.fsf(a)hangup.portland.xach.com>, > Zach Beane <xach(a)xach.com> wrote: > >> RG <rNOSPAMon(a)flownet.com> writes: >> >> > (defmethod add ((c counter) item) >> > (setf (ref c item) (1+ (ref c item 0)))) >> >> Does (incf (ref c item 0)) work? >> >> Zach > > No. That is a crappy design. Zach
From: RG on 17 Jun 2010 19:50
In article <87bpb9s03t.fsf(a)hangup.portland.xach.com>, Zach Beane <xach(a)xach.com> wrote: > RG <rNOSPAMon(a)flownet.com> writes: > > > In article <87fx0ls1lm.fsf(a)hangup.portland.xach.com>, > > Zach Beane <xach(a)xach.com> wrote: > > > >> RG <rNOSPAMon(a)flownet.com> writes: > >> > >> > (defmethod add ((c counter) item) > >> > (setf (ref c item) (1+ (ref c item 0)))) > >> > >> Does (incf (ref c item 0)) work? > >> > >> Zach > > > > No. > > That is a crappy design. Thank you for that very constructive criticism. If that is the feature that will make the difference between you using this library and not it's really easy to change. rg |