From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA20583 for caml-red; Fri, 7 Jul 2000 16:29:30 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA30376 for <caml-list@pauillac.inria.fr>; Thu, 6 Jul 2000 00:40:33 +0200 (MET DST)
Received: from hebe.or.intel.com (hebe.or.intel.com [134.134.248.4])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e65MeVX25442
	for <caml-list@inria.fr>; Thu, 6 Jul 2000 00:40:31 +0200 (MET DST)
Received: from ichips-jf.jf.intel.com (ichips-jf-hme1.jf.intel.com [134.134.100.112])
	by hebe.or.intel.com (8.9.1a+p1/8.9.1/d: relay.m4,v 1.30 2000/06/08 18:25:35 dmccart Exp $) with ESMTP id PAA24687
	for <caml-list@inria.fr>; Wed, 5 Jul 2000 15:52:03 -0700 (PDT)
Received: from dtthp127.pdx.intel.com (dtthp127.pdx.intel.com [134.134.102.82])
	by ichips-jf.jf.intel.com (8.9.1a/8.9.1/d: internal.m4,v 1.2 1998/11/09 19:18:37 iwep Exp iwep $) with ESMTP id PAA11087;
	Wed, 5 Jul 2000 15:40:29 -0700 (PDT)
Received: from ichips.intel.com (johnh@localhost [127.0.0.1])
	by dtthp127.pdx.intel.com (8.9.1a/8.9.1/d: client-jf.m4,v 1.1 1998/12/24 19:00:41 jamesw Exp jamesw $) with ESMTP id PAA21974;
	Wed, 5 Jul 2000 15:40:29 -0700 (PDT)
Message-Id: <200007052240.PAA21974@dtthp127.pdx.intel.com>
To: caml-list@inria.fr
cc: John Harrison <johnh@ichips.intel.com>
Subject: Re: polymorphic equality and overloading
Date: Wed, 05 Jul 2000 15:40:28 -0700
From: John R Harrison <johnh@ichips.intel.com>
Sender: weis@pauillac.inria.fr


Eijiro Sumii writes:

| But as you know (and as I wrote in my previous messages), the
| polymorphic equality in Caml is not at all the "equality in
| mathematics" for many (or most?) datatypes.

Probably "most" is an exaggeration. But there are quite a few examples.
One I haven't seen mentioned in this thread is the type of floating point
numbers. The equality relation defined in the main standard for binary
floating point arithmetic (IEEE 754) is not reflexive. Specifically x = x
is false if x is a NaN ("not a number"). So again, this is really an
instance of overloading in CAML:

  #let x = 0.0 /. 0.0;;
  x : float = nan.0
  #x = x;;
  - : bool = false
  #x == x;;
  - : bool = true

Nevertheless, I find the CAML polymorphic equality and orderings pretty
useful and superficially simple, even if they sometimes have a touch of
arbitrariness about them.

Is it possible using just equality, not orderings, to write a set-compare
operation on polymorphic lists using fewer than 0(n^2) operations?
Trivially, using orderings, one can just sort both lists in O(n log n)
operations then run along them in order. Is there something comparably
efficient just using equality?

John.