[plt-scheme] help on how to write a frequency-counting function in a more functional way

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sat Apr 18 16:34:09 EDT 2009

Frequencies come in ranges and my guess is that you have the full  
range of them.

If so, I would have no hesitations giving up pure FP and use a vector  
in the proper range. I doubt very much any FP technique comes close  
in efficiency.

-- Matthias

On Apr 18, 2009, at 4:18 PM, keydana at gmx.de wrote:

> Hi,
> today on one of the extremely rare occasions where I can use scheme  
> at work, I had to get at the frequencies for a list of ids  
> extracted from a logfile. E.g., I had a list like
> '(1234 1234 5678 1234)
> and wanted to, on the one hand, remove the duplicates and, on the  
> other hand, store how many instances there were of each id.
> For example, if represented as an alist, the result might have  
> looked like this:
> '((1234 3) (5678 1))
> However, I could not imagine a "purely functional" way to do this,  
> and so I used a box to update the frequencies, like so:
> (define count
>  (lambda (lst)
>    (let count-accum ((lst lst) (frequencies '()))
>      (if (null? lst)
>          frequencies
>          (let ((first (car lst)))
>            (cond ((assoc first frequencies)
>                   (let ((count-box (cdr (assoc first frequencies))))
>                     (begin (set-box! count-box (+ 1 (unbox count- 
> box)))
>                            (count-accum (cdr lst) frequencies))))
>                  (else (count-accum (cdr lst) (cons (cons first  
> (box 1)) frequencies)))))))))
> (I also considered a hashtable, which would have been equally  
> "impure" and less practical, because the next processing step again  
> required a list).
> I suppose there must be "more functional" (if I may say so) and  
> more elegant ways to perform this task. I'd be glad to learn and  
> thankful for any suggestions :-)
> Ciao
> Sigrid
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090418/9fa34888/attachment.html>

Posted on the users mailing list.