[m-dev.] Foreign type compare and unification

[Ralph Becket]

Zoltan Somogyi, Sunday, 12 May 2002:
> On 12-May-2002, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> > Is there any reason why we have user-defined equality but not
> > user-defined comparison? Not having user-defined comparison
> > makes it difficult to use data types such as cords (strings
> > represented as trees for constant-time append).
> 
> Yes. In many cases, the user-defined comparison routine would work with
> a partial order, not a total order, and this is incompatible with the
> determinism of compare/3.
> 
> Ideally, we should let users whose define types with non-standard equality
> choose between three options:
> 
> - no comparison defined on the type;
> - comparison defined on the type as a total order;
> - comparison defined on the type as a partial order.
> 
> Implementing this three-way would be quite difficult, since we would need
> to modify the builtin assumption that the types bound to universally
> quantified type variables have a total order comparison. (At the moment,
> we make this assumption come true for user defined types by automatically
> aborting on attempts to compare them.)
> 
> Implementing a choice between the first two alternatives should not be too
> difficult, and as you say, may be useful enough to justify the effort.

My intuition is that insisting on totally-ordered comparison (leaving
the proof obligation to the programmer as we do for user defined
equality) would get you 90% of what is wanted.

> - no comparison defined on the type;

Can be handled with a comparison method that always throws an exception.

We could also omit any need for a separate equality method.

On a related note, would there be any problem with defining

	X  < Y  <=>  compare((<), X, Y)
	X =< Y  <=>  not compare((>), X, Y)
	X >  Y  <=>  compare((>), X, Y)
	X >= Y  <=>  not compare((<), X, Y)

for all types?

(Aside: can we also ultimately replace the unfortunately moded compare/3
with a function, without too much pain?)

- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------