English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Polymorphic comparison
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 1994-10-18 (12:54)
From: John Harrison <John.Harrison@c...>
Subject: Re: Polymorphic comparison

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).