Using Ord for keys of maps and sets

Yitzchak Gale gale at
Mon Dec 3 07:47:00 EST 2007

Henning Thielemann wrote:
> I already told about by scepticism about using Ord for keys of maps and
> sets:

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

3. An application-specific ordering.

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

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.


More information about the Libraries mailing list