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

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Sat Apr 18 16:57:20 EDT 2009

Robby wrote:

> If the list is very long, an equal-key hash table is definitely the
> way to go (unless you expect there to be very few duplicates). If it
> is very long (with lots of duplicates) and you really want to do
> something purely functional, there are some clever purely function
> balanced binary tree algorithms out there (I'd start with Chris
> Okasaki's book to learn more about them). 

If the IDs can be totally ordered, sorting by ID puts the duplicates 
together, after which a single pass produces the frequency counts in O(n 
log n) time for a purely-functional solution (which is what you'll get 
with a messier data structure anyway). But the hash table (followed by a 
hash-map to convert to a list for the next step) will be faster, I 
suspect. --PR

Posted on the users mailing list.