Unordered map

[Andrew Wagner]

All,
Forgive me if this has been brought up before, but I was just thinking
about the fact that there's no Map structure in the standard library
that doesn't pretty much require an Ord instance for its keys. I say
"pretty much" because, while you can declare a Map with keys of a type
that's not an Ord instance, you can't do hardly anything with it.
E.g., you can't do an insert. Makes it kind of pointless. Now, I
understand the fact that this is for efficiency purposes, but it does
seem a bit inconsistent. Why allow the construction of a Map you can't
do anything with? Here are two possible more consistent ways of
handling this:

Suppose I have some data structure that is inherently unordered, and I
want to use it as a key into a Map. How would I get around this
limitation on the client side? Well, the most obvious way is to create
some nonsensical Ord instance, like compare _ _ = Eq. Is that the
recommended solution? If so, we could create unordered versions of all
the ordered methods that assume this 'ordering'. If not, what is the
recommended way, and why not create unordered versions that use that?

The other way to make the library more consistent, perhaps, would be
to simply move the Ord requirement up to that data structure: that is,
make it Ord k => Map k a, and then have a new data structure like
UnorderedMap (or, to use a more standard term, Dictionary).

Thoughts? Am I completely missing something?