Using Ord for keys of maps and sets

[Yitzchak Gale]

Henning Thielemann wrote:
> I already told about by scepticism about using Ord for keys of maps and
> sets:
>   http://www.haskell.org/pipermail/libraries/2007-April/007411.html

Yes. There are a number of different scenarios for the
ordering that you want to use for indexing:

1. A default ordering for the type that is a natural ordering.

2. A default ordering for indexing that is not a natural
   ordering.

3. An application-specific ordering.

4. More than one ordering for the same type, determined
   statically.

5. More than one ordering for the same type, determined
   dynamically, i.e., parameterized orderings.

My experience has been that all of these cases do come
up quite often in real life.

One solution would be to have Data.Map.Indexable, etc.
as alternatives using Indexable instead of Ord, so that
we could avoid newtype wrapping in case 2.

We could allow for case 3 by not providing any default
instances for Indexable. Or we could provide default
instances in a separate module, Data.Indexable.Instances
(or something), that you could choose whether or not to import.

Newtype wrapping is still required in case 4, so
Indexable doesn't add much here.

We have not yet said anything helpful about case 5.

-Yitz