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

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