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 18 Jun 2010 12:59 In article <hvg4ou$4pb$1(a)news.eternal-september.org>, Tim Bradshaw <tfb(a)tfeb.org> wrote: > On 2010-06-18 16:22:29 +0100, RG said: > > > You can even make an abstract associative map that automatically chooses > > an underlying implementation based on run-time profiling without > > changing your client code. > > I think there's really two approaches here: > > You can go for the "huge complicated reusable library which does > everything" approach. This is what Java does, and is what you're > proposing. Actually, no, that is not what I'm proposing. Quite the opposite in fact. dictionary.lisp is only 295 LOC including comments and blank lines. Even if you add in rg-utils (only a tiny part of which is used by dictionary.lisp) that's only an addition 970 LOC. That is not "huge" by any stretch of the imagination. As for complicated, the core API for dictionary.lisp consists of only a single call, the REF macro. REF subsumes the functionality of GETHASH, ASSOC, and GETF, so the API for abstract associative maps is actually simpler than the API for the equivalent CL functionality. Finally, the primary goal of dictionary.lisp is pedagogy and prototyping, not hard-core production work. If you want to teach Lisp using only the core language you have no choice but to introduce extraneous detail, like hash tables or alists or plists. If you have abstract associative maps you expose students to the proper separation of API and implementation from the very beginning, which I think will make them better programmers in the long run. rg
From: Scott L. Burson on 18 Jun 2010 14:15 On Jun 17, 2:28 pm, Lieven Marchand <m...(a)wyrd.be> 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. (defun occurrences (list) (let ((ht (make-hash-table))) (dolist (x list) (incf (gethash x ht 0))) (sort (let ((result nil)) (maphash (lambda (k v) (push (cons k v) result)) ht) result) #'> :key #'cdr))) Just as an antidote to the LOOP style :) Really, I don't see that LOOP is any help here at all. I will grudgingly grant that there are some cases LOOP does a good job with that are difficult to do elegantly otherwise, but this is clearly not one of them. -- Scott
From: Lieven Marchand on 18 Jun 2010 14:28 pjb(a)informatimago.com (Pascal J. Bourguignon) writes: > Lieven Marchand <mal(a)wyrd.be> writes: >> (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. Indeed. Thanks for bringing this up. Lispworks accepts this without a warning. I'll have to check my code for other occurrences :)
From: Tim Bradshaw on 18 Jun 2010 15:01 On 2010-06-18 17:59:32 +0100, RG said: > dictionary.lisp is only 295 LOC including comments and blank lines. > Even if you add in rg-utils (only a tiny part of which is used by > dictionary.lisp) that's only an addition 970 LOC. That is not "huge" by > any stretch of the imagination. It's about two orders of magnutude larger than simple versions of occurrence-counting funcions using alists or hashtables (both of which come out at around 7 lines without comments, so maybe 9 with): (defun occ/alist (list &key (test #'eql)) (loop with al = '() for e in list for a = (or (assoc e al :test test) (first (push (cons e 0) al))) do (incf (cdr a)) finally (return al))) (defun occ/hash (list &key (test #'eql)) (loop with ht = (make-hash-table :test test) for e in list do (incf (gethash e ht 0)) finally (return (loop for k being the hash-keys of ht using (hash-value v) collect (cons k v))))) That's just dictionaries. It's OK, I don't expect you to understand the point I'm making, or agree.
From: Bob Felts on 18 Jun 2010 17:01
Tim Bradshaw <tfb(a)tfeb.org> wrote: > On 2010-06-18 17:59:32 +0100, RG said: > > > dictionary.lisp is only 295 LOC including comments and blank lines. Even > > if you add in rg-utils (only a tiny part of which is used by > > dictionary.lisp) that's only an addition 970 LOC. That is not "huge" by > > any stretch of the imagination. > > It's about two orders of magnutude larger than simple versions of > occurrence-counting funcions using alists or hashtables (both of which > come out at around 7 lines without comments, so maybe 9 with): You're arguing about LOC, Ron is arguing about correct abstraction. I have to side with Ron on this one: getting the correct abstraction is paramount above everything else. Small LOC is good if the abstraction doesn't matter; it's easy to change programs with small LOC. [...] > > It's OK, I don't expect you to understand the point I'm making, or agree. Do you not expect Ron to understand it because you haven't explained it well, or because you think Ron doesn't have the mental horsepower to understand it? Ron and I don't agree on a number of things, but he isn't stupid. Pigheaded, possibly, but I'm looking in a mirror as I say that. |