On Mon, 2005-10-10 at 09:36 +0200, Alain Frisch wrote:
> skaller wrote:
> > The reason may be because the equality of integers
> > isn't the same as algebraic equality of the data structures:
> 
> Indeed, but this is not about maintaining an invariant. Because of the
> representation of Big_int.big_int as a pair (sign,absolute value), the
> polymorphic comparison would give (-1) < (-2) if the custom comparison
> were used for Nat.nat.

Yes. There are really two separate issues here I think.

First, comparison is required for total ordering 
or perhaps just equality is required for use in some data 
structures (Hashtbl only needs equality and hash, a polymorphic
set would need the total order, but there isn't one ..) 

In this case, only a bijection  between abstract values 
and representation is required,
which can obtained by a suitable representation invariant.
So here -1 < -2 may be counterintuitive, but irrelevant.

Second, comparison is required for user ordering of values.
Of course here -1 < -2 would be a disaster.

This is the same issue with floating comparison vs
polymorphic comparison of floats.

Of course the client can provide an ordering for (most)
functorised data structures -- the problem is if the data
type is complicated, it can be very hard to construct
the ordering, which is where the polymorphic comparison
proves useful.

An interesting tradeoff.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net