Unordered map

[Jan-Willem Maessen]

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 implementing collections---one more imperative, the  
other more functional.

Of course, if one is simply looking for INefficient collections that  
require only (Eq a), this probably doesn't matter.  But in that case  
it's hard to do much better than [(a,b)] and lookup (it's possible to  
do better, using e.g. unboxed tuple arrays and seekrit mutation, but  
probably only worth it for stuff that's big enough that we should have  
been using a proper map anyway).

-Jan-Willem Maessen