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

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Sun Apr 19 11:56:28 EDT 2009

At Sat, 18 Apr 2009 22:57:59 -0400, Matthias Felleisen wrote:
> 
> Sigrid, just to get a first idea, I coded up the four most natural  
> solutions to this problem with a simple stress test and timed them:
> 
>   -- vector
>   -- sort and count (PR's suggestion)
>   -- association list
>   -- binary search tree

Here's one more, using a functional "hash table":

 (define (cnt-ht f)
    (cnt-fp f
            (lambda () #hash())
            (lambda (ht freq)
              (hash-update ht freq add1 0))))

The performance is close to the binary-tree performance, probably
because that's how functional hash tables are implemented internally
(but as red-black trees, so they're always balanced).



Posted on the users mailing list.