Polymorphic comparison

Polymorphic comparison

[Pierre Weis]

To: caml-list@pauillac.inria.fr
Cc: John.Harrison@cl.cam.ac.uk
Subject: Polymorphic <<
Date: Mon, 17 Oct 94 16:10:57 +0100


Classic ML had a polymorphic test comparison "$<< : * -> ** -> bool"
(or in CAML parlance, "prefix << : 'a -> 'b -> bool"). This was claimed
to be substitutive w.r.t ML equality, i.e. if x = x' and y = y' then x
<< y iff x' << y' (I'm not sure about function types). Thus, unless
the implementation is globally hash-consed, it isn't just pointer comparison.

Anyway, though a bit of a hack, it's quite a handy thing to have around for
performing arbitrary canonicalizations. Does CAML Light have anything similar?

John.

Polymorphic comparison

[Pierre Weis]

To: caml-list@pauillac.inria.fr
Cc: John.Harrison@cl.cam.ac.uk
Subject: Polymorphic <<
Date: Mon, 17 Oct 94 16:10:57 +0100


Caml has a polymorphic equality with type scheme 'a -> 'a -> bool. It
tests structural equality between values of the same type
(isomorphism), and fails when applied to functions.

On the other hand comparisons are monomorphic: we have comparisons for
integers (prefix <=), strings (le_string), floatting point numbers
(le_float) but no polymorphic comparisons.
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).

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 ?

Pierre

Polymorphic comparison

[Judicael Courant]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 552 bytes --]

Hello,

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";;


#3 c true;;
- : bool = true
#[ "hello" ; "world" ] c 3.14159;;
- : bool = false


But, as Pierre Weis, I am wondering what to do with such a function...

Maybe
let c (x:'a) (y:'a) = (hash x) <= (hash y);;
would be more suitable ?

-- 
Judicaël COURANT           tel. : 72 72 85 82
ENSL - LIP                 email : Judicael.Courant@ens-lyon.fr
46, allée d'Italie
69364 Lyon cedex 07
--

Re: Polymorphic comparison

[John Harrison]

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.

Re: Polymorphic comparison

[Xavier Leroy]

Yes, I have been thinking for a while about generalizing the
generic equality function to a generic ordering function (with three
possible results: "equal", "less than", "greater than").

It's a simple extension of the code for generic equality (order base
types as usual and use a lexicographic extension for data structures)
--- no more of a hack than generic equality itself.

Usefulness: canonical representatives (as John Harrison mentioned),
ordered binary trees such as those implementing sets and maps (but the
problem remains to attach user-defined orderings to some types), and a
unified notation for comparisons over integers, floats, strings and
characters.

There are a few difficulties in the implementation that remain to iron out
(what to do with pointers outside the heap which may point to
well-formed objects, in which case a recursive descent is needed,
but may also point to foreign objects, in which case comparison should
fail), so I can't promise this will be in the next release, but I'll
give it a try.

- Xavier Leroy

Polymorphic comparison

[Franck.Delaplace]

>I think this polymorphic comparison is quite easy to implement in the
>following way:

>#open "hashtbl";;
>let c x y = (hash x) <= (hash y);;
>

this kind of comparison would not be  appropriate in some cases.
for example when you want to use it for sorting strings 

    c "ace" "af";;

gives

- : bool = false


by convention, we intend to have this relation "ace" <= "af" since the comparison is defined
by comparing the substrings "ac" "af"