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

On Wed, Apr 29, 2009 at 5:53 PM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> At Tue, 28 Apr 2009 23:02:37 -0400, Doug Orleans wrote:
>> On Sun, Apr 19, 2009 at 11:56 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
>> > 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).
>>
>> I had been naively assuming that immutable hash tables were as
>> efficient as mutable ones.  It would be good to say more about their
>> relative performance in the reference manual than just "immutable
>> tables support constant-time functional update."
>
> Ok, I extended the note there.

(There's a "the the" in the extended note.)  I guess my main question
was, how do hash-remove and hash-remove! compare?  And, come to think
of it, I don't understand how hash-ref and hash-set are constant-time
if they use red-black trees.

> I don't think the write
> barrier is not a significant cost in mutating an object.

(I assume you meant a single-negative, not a double-negative...)

> With our implementation, immutable hash tables are probably only better
> when they give you a better algorithm --- one that can needs O(1)
> operations on a mapping and where the operations are aren't
> "single-threaded" in the cumulative sense (i.e., you start with some
> mapping and you want to extend it in different, independent ways).

Sure, hash-set is better than hash-copy + hash-set!.

--dougorleans at gmail.com