Path: g2news2.google.com!news2.google.com!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!spln!extra.newsguy.com!newsp.newsguy.com!enews2
From: "WJ" <w_a_x_...@yahoo.com>
Newsgroups: comp.lang.lisp
Subject: Re: Counting occurences
Date: 6 Mar 2011 13:47:44 GMT
Organization: NewsGuy - Unlimited Usenet $19.95
Lines: 120
Message-ID: <il03a001tgg@enews2.newsguy.com>
References: <87vfr3Ft2dU1@mid.individual.net> <87wrtxnxw1.fsf@kuiper.lan.informatimago.com>
NNTP-Posting-Host: p21ec0f4c3bc7d40cb9910074ab6552dbae3cf5a0695c6330050eb6cee3a4af5b.newsdawg.com
User-Agent: XanaNews/1.18.1.6
X-Antivirus: avast! (VPS 110306-0, 03/06/2011), Outbound message
X-Antivirus-Status: Clean

Pascal J. Bourguignon wrote:

> Eric Wolf <e...@boese-wolf.eu> writes:
> 
> > 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?
> 
> SORT takes both a comparison  predicate, and a key function.  This let
> you avoid building an anonymous function.
> 
> You can avoid the helper function by using an optional parameter.
> 
> But I would keep the helper function since the signature of OCCURENCES
> doesn't involve an optional parameter per se, and it's often more
> efficient to have functions with fixed number of parameters. Just put
> it as a local function using LABELS.
> 
> The best advice, is to avoid SETF.  Try to think functionnaly.  Of
> course, Common Lisp is multi-paradigm, and we don't refuse an
> occasional state modification, as long as it's of limited scope, and
> the alternative would be more costly and less readable.  So I still
> use INCF to increment the counter, but this is done on a data
> structure that is being built by the count-occurences function, and
> the alternative would be to cons the backbone of the a-list again and
> again or using even more complex functional data structures.
> 
> 
> 
> (defun occurences (list &optional counts)
>   (if (null list)
>       (sort counts (function >) :key (function cdr))
>       (let ((pair (assoc (first list) counts)))
>         (if (null pair)
>             (occurences (rest list) (acons (first list) 1 counts))
>             (progn
>               (incf (cdr pair))
>               (occurences (rest list) counts))))))
> 
> 
> 
> (defun occurences (list)
>   (labels ((count-occurences (list counts)
>              (if (null list)
>                  (sort counts (function >) :key (function cdr))
>                  (let ((pair (assoc (first list) counts)))
>                    (if (null pair)
>                        (count-occurences (rest list) (acons (first list) 1
> counts))                        (progn
>                          (incf (cdr pair))
>                          (count-occurences (rest list) counts)))))))
>     (count-occurences list '())))
> 
> 
> (occurences '(a b c a b c a b a))
> --> ((A . 4) (B . 3) (C . 2))
> 
> 
> 
> Of course, in Common Lisp, we would just use an interation construct:
> 
> (defun occurences (list)
>  (loop
>    :with counts = '()
>    :for item :in list
>    :for pair = (assoc item counts)
>    :if pair 
>    :then (incf (cdr pair))
>    :else (push (cons item 1) counts)
>    :finally (return (sort counts (function >) :key (function cdr)))))
> 
> 
> A good compiler would generate the same code for both sources, so it's
> up to you to see which is clearer.

Guile Scheme:

(use-modules (srfi srfi-69)) ; hash-tables
(use-modules (srfi srfi-26)) ; currying (cut)

(define (with f g)(lambda (a b) (f (g a) (g b))))

(define (occur lst)
  (let ((h (make-hash-table)))
    (for-each 
      (cut hash-table-update!/default h <> 1+ 0)
      lst)
    (sort (hash-table->alist h) (with > cdr))))