From mboxrd@z Thu Jan 1 00:00:00 1970 Received: by pauillac.inria.fr; Tue, 18 Oct 94 19:19:52 +0100 Received: from concorde.inria.fr by pauillac.inria.fr; Tue, 18 Oct 94 13:54:34 +0100 Received: from swan.cl.cam.ac.uk (pp@swan.cl.cam.ac.uk [128.232.0.56]) by concorde.inria.fr (8.6.9/8.6.9) with ESMTP id NAA28585 for ; Tue, 18 Oct 1994 13:54:33 +0100 Received: from auk.cl.cam.ac.uk (user jrh (rfc931)) by swan.cl.cam.ac.uk with SMTP (PP-6.5) to cl; Tue, 18 Oct 1994 13:54:13 +0100 To: caml-list@pauillac.inria.fr Cc: John.Harrison@cl.cam.ac.uk Subject: Re: Polymorphic comparison In-Reply-To: Your message of "Tue, 18 Oct 94 11:40:09 BST." <9410181040.AA18410@lip.ens-lyon.fr> Date: Tue, 18 Oct 94 13:54:01 +0100 From: John Harrison Message-Id: <"swan.cl.cam.:256500:941018125425"@cl.cam.ac.uk> Sender: weis@pauillac.inria.fr Judicael Courant writes: | I think this polymorphic comparison is quite easy to implement in the | following way: | | #open "hashtbl";; | let c x y = (hash x) <= (hash y);; | #infix "c";; I should have pointed out that I want a true ordering, i.e. something antisymmetric. (Presumably the above isn't, since several different items might yield the same hash value). The idea is to be able to sort a list of elements of any type into an arbitrary but fixed order. Pierre Weis adds: | In the next 0.7 version of Caml Light, we plan to extend comparisons to a | polymorphic function (i.e. prefix < : 'a -> 'a -> bool, instead of the | now available prefix < : int -> int -> bool). That would be all I want, I think. | To extend comparisons to unrelated pairs of values, that is defining | prefix < with type scheme 'a -> 'b -> bool seems a bit strange to me. | What do you plan to do with such a general type scheme for comparisons ? I don't foresee any use for such a general mechanism, although that's how it was in Classic ML. The applications I have in mind are in theorem proving; for example canonicalizing expression trees based on an associative-commutative operation. However I can envisage some other uses, e.g. set/multiset comparison. I suspect that if you can only do pairwise comparison this is O(n^2), whereas just sorting both sets first then comparing should be O(n log n). John.