Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
equality of Big_ints
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] equality of Big_ints
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++: