Counting occurences [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: Eric Wolf on 17 Jun 2010 16:46

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

From: Frode V. Fjeld on 17 Jun 2010 17:23

Eric Wolf <eric(a)boese-wolf.eu> writes:

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

Note that this isn't "functional" in the sense "side-effect-free", as
you're clearly modifying the result list. That's fine, CL is not abount
such "functional" programming, although you end up here with a somewhat
strange mix of programming styles.

I'd use a plist because of the existence of (setf getf):

(defun occurences-helper (list result)
(if (null list)
result
(progn
(incf (getf result (car list)))
(occurences-helper (cdr list) result))))

But really I'd iterate normally:

(defun occurences-helper (list)
(loop with result = nil
for element in list
do (incf (getf result element))
finally (return result)))

> (defun occurences (lst)
> (sort
> (occurences-helper lst ())
> #'(lambda (x y)
> (>
> (cdr x)
> (cdr y)))))

Assuming an assoc result again, this can be written like so:

(defun occurences (list)
(sort (occurences-helper list nil)
#'>
:key #'cdr))

A different approach:

(defun occurences (list)
(sort (mapcar (lambda (element)
(cons element
(count element list)))
(remove-duplicates list))
#'>
:key #'cdr))

--
Frode V. Fjeld

From: Lieven Marchand on 17 Jun 2010 17:28

From: Pascal J. Bourguignon on 17 Jun 2010 17:37

Eric Wolf <eric(a)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.

--
__Pascal Bourguignon__ http://www.informatimago.com/

From: Pascal J. Bourguignon on 17 Jun 2010 18:17

Lieven Marchand <mal(a)wyrd.be> writes:

> Eric Wolf <eric(a)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?
>
> (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.

--
__Pascal Bourguignon__ http://www.informatimago.com/

| Next | Last
Pages: 1 2 3 4 5 6 7 8 9 10 11
Prev: Black-Jewish History FAQ - Is The Secret Relationship between blacks and jews a “hate literature”?
Next: which library to generate xml with namespaces?