Unordered map

[David MacIver]

On Fri, Aug 1, 2008 at 1:19 PM, Jan-Willem Maessen
<jmaessen at alum.mit.edu> wrote:
>
> On Aug 1, 2008, at 6:18 AM, Johannes Waldmann wrote:
>
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Aaron Denney wrote:
>>
>>> If you're going to make users write an
>>> equality function, making them write an ordering adds little effort, and
>>> a reasonable amount of gain.  Usually.
>>
>> Then why is there a distinction between e.g.
>> Map and SortedMap (and Set and SortedSet) in the Java libraries?
>>
>> Yes yes I know Haskell is not Java etc. but they must have given
>> this some thought. (Of course them making everything an instance of
>> Eq and Hash is a design error but that's not the point here.)
>
> Au contraire, it's *exactly* the point!  Java uses the hash code to
> implement collections that only require equality and hashing, but no
> ordering.  Haskell, as a functional language, instead prefers equality and
> ordering---because trees admit efficient pure update, whereas hash tables
> generally do not.  Two different languages, two different approaches to

You know, this isn't actually true. You can implement an immutable HashMap as

newtype HashMap a b = HashMap (IntMap [(a, b)])

Where you basically store association lists of things with the same
hash code as they values of the IntMap.

This has fairly good merge and update properties, and performs quite
reasonably. I haven't tried this with the Haskell implementations, but
I've benchmarked my Scala implementation of the same idea and, while
not as fast as a normal array based HashMap, it seems to be a
significance performance improvement over the red black tree based
maps I've compared it against and supports pretty comparable amounts
of sharing.