From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 1124FBB81 for ; Mon, 10 Oct 2005 17:02:06 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j9AF25xO018905 for ; Mon, 10 Oct 2005 17:02:05 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA25169 for ; Mon, 10 Oct 2005 17:02:05 +0200 (MET DST) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j9AF22A8016583; Mon, 10 Oct 2005 17:02:04 +0200 Received: from rosella (ppp2-148.lns1.syd7.internode.on.net [59.167.2.148]) by smtp1.adl2.internode.on.net (8.12.9/8.12.6) with ESMTP id j9AF20uv086543; Tue, 11 Oct 2005 00:32:01 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] equality of Big_ints From: skaller To: Alain Frisch Cc: caml-list@inria.fr In-Reply-To: <434A19FA.4080805@inria.fr> References: <87br1yhuxl.fsf@buug.org> <1128925132.7508.21.camel@rosella> <434A19FA.4080805@inria.fr> Content-Type: text/plain Date: Tue, 11 Oct 2005 01:02:00 +1000 Message-Id: <1128956520.7507.9.camel@rosella> Mime-Version: 1.0 X-Mailer: Evolution 2.2.1.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 434A826D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 434A826A.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 frisch:01 integers:01 nat:01 nat:01 hashtbl:01 hash:01 wrote:01 wrote:01 sourceforge:01 equality:01 equality:01 polymorphic:01 polymorphic:01 abstract:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 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 Felix, successor to C++: http://felix.sf.net