Proposal: Bounded instance for IntSet (ticket #1953)

[Yitzchak Gale]

Yitzchak Gale wrote:
>> In this case, the Ord instance is not really natural; it is defined
>> for technical reasons for use by the library itself (and its
>> friends). The library has no need for a Bounded instance, so why
>> should we prevent people from defining one for some other purpose?

David Benbennick wrote:
> Note that in one sense, people are already prevented from defining a
> different Bounded instance.  Any Bounded instance other than the one
> suggested in this proposal would fail to obey the axioms of the
> Bounded class.  In other words, there is a unique largest element, and
> a unique smallest element, an no one can legitimately define a
> different Bounded instance.

Where are these axioms? I only see the Haddocks in the Prelude:

"Ord is not a superclass of Bounded since types that are not
totally ordered may also have upper and lower bounds."

I think that is the case here. There is no unique
notion of order for this type. The Ord instance
only exists so that you can insert these things into
containers. So Ord is used up now for this type,
a pity. Why should the fact that we want
to be able to use containers force us to
clobber the Bounded class as well?

I think that Henning's point is well-taken. This use
of Ord in the Data.<container> series has effectively
changed the semantics of Ord. If a type has an
Ord instance, it might mean that the type is ordered,
but it also might mean only that the type has been
enabled for convenient use with containers.

If we allow the use of an alternative class for
key indexing for types that are not naturally ordered,
as Henning suggests, then we will be able
to impose a relationship between Bounded
and Ord as you suggest.

Regards,
Yitz