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: Kenneth Tilton on 18 Jun 2010 00:17 Eric Wolf 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? One issue here is "recursion obsession". It comes from Graham being more a Schemer than a Lisper. Lispers rejoice in multiple paradigms, and try to use the right one at the right time. In this case, when iterating iterate. But if you want to do recursion: (defun occurences (list) (labels ((occ (list) (fun-stuff (car list) (occ (cdr list)))) (occ list))) ie, no need for an external helper, we have labels and flet. Where is fun-stuff? You mostly have it already, just take what you have and lose all the setfs and progns -- you /are/ reading Graham, aren't you? Not a bad start, btw. kt
From: Scott L. Burson on 18 Jun 2010 01:35 On Jun 17, 3:48 pm, RG <rNOSPA...(a)flownet.com> wrote: > In article <87vfr3Ft2...(a)mid.individual.net>, > Eric Wolf <e...(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 }> With FSet it's even more trivial: (defun count-items (list) (convert 'bag list)) (Sorting is again left as an exercise.) -- Scott
From: Nicolas Neuss on 18 Jun 2010 03:19 "Frode V. Fjeld" <frode(a)netfonds.no> writes: > (defun occurences-helper (list) > (loop with result = nil > for element in list > do (incf (getf result element)) > finally (return result))) Small correction: (getf result element 0) Nicolas
From: Pascal Costanza on 18 Jun 2010 06:53 On 18/06/2010 00:17, Pascal J. Bourguignon wrote: >> (defun occurrences (list) >> (loop with hash-table = (make-hash-table) >> for item in list >> do >> (incf (gethash item hash-table 0)) >> finally >> return (sort (loop for key being each hash-key of hash-table using (hash-value count) >> collect (cons key count)) >> #'> >> :key #'cdr))) >> >> Just as an antidote to Graham's style. > > But this is not ANSI CL, but CLtL1. > FINALLY takes a compound-form+, not an unconditional. By the way, what is the reason that you have to say "finally (return ....)" instead of just "finally return ..."? So in other words, why does FINALLY not take an unconditional in ANSI CL? This is probably the most common mistake I'm tripping over when using LOOP... Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Pascal J. Bourguignon on 18 Jun 2010 09:11
Pascal Costanza <pc(a)p-cos.net> writes: > On 18/06/2010 00:17, Pascal J. Bourguignon wrote: >>> (defun occurrences (list) >>> (loop with hash-table = (make-hash-table) >>> for item in list >>> do >>> (incf (gethash item hash-table 0)) >>> finally >>> return (sort (loop for key being each hash-key of hash-table using (hash-value count) >>> collect (cons key count)) >>> #'> >>> :key #'cdr))) >>> >>> Just as an antidote to Graham's style. >> >> But this is not ANSI CL, but CLtL1. >> FINALLY takes a compound-form+, not an unconditional. > > By the way, what is the reason that you have to say "finally (return > ...)" instead of just "finally return ..."? So in other words, why > does FINALLY not take an unconditional in ANSI CL? This is probably > the most common mistake I'm tripping over when using LOOP... I think it's explained by the + after compound-form: it allows for several forms to be executed in sequence in the finally clause. (loop for i below 10 collect i into result finally (print 'done) (assert (= 10 (length result))) (return (remove-if 'oddp result))) Perhaps also for symetry with the INITIALLY clause. -- __Pascal Bourguignon__ http://www.informatimago.com/ |