Unordered map

[Aaron Denney]

On 2008-08-01, Johannes Waldmann <waldmann at imn.htwk-leipzig.de> wrote:
> 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.)

You would have to ask the Java designers.

> The practical problem with Haskell's type class mechanism
> is that all instances (of Eq, Ord) are global,

This is a feature, not a bug.  It helps ensure that manipulations
on maps will always use compatible functions.  If, instead,
you constructed maps by passing in a comparison function, what
happens when you merge two maps?  Which function gets used?  Normally
you would be able to re-use the structure of each map in combining them.
But if the functions they used are different, than they have to be
resorted according to the kept function.  Or, you have an obscure,
difficult to track down bug, rather than an error at compile time.

> so if one library (Data.Map) requires them,
> then you're stuck with these instances for all of your program.
> Of course the same thing holds for Java's "implements Comparable<>"
> but they have local types. Well, Haskell has newtype,
> but that's (module-)global.

They don't have local types.  They have inner classes, and objects get
passed.

Newtypes do work.  The newtype deriving extension works even better.
If something has multiple ways of comparing, then the context in which
they are used should be tagged differently.  Haskell types are cheap,
both in the compiler, and when typing, because it's nowhere near as
verbose as Java.

-- 
Aaron Denney
-><-