Re: [Caml-list] User-defined equality on types?

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> I'd like to suggest allowing the user to define a chosen interpretation
> of the equality symbol, and perhaps the polymorphic orderings too, on
> each new (maybe just abstract) data type. This seems natural in the 
> context of abstract data types with non-canonical representation, giving
> a kind of quotient type. Has this ever been considered? 

Yes.  This was one of the first motivations for Haskell type classes,
I believe.

> Are there good reasons against it?

It's not easy to implement.  One can do it the Haskell way, by passing
around compiler-generated functions as extra arguments, but the
language extensions needed to declare ad-hoc polymorphic operations
and define implementations for these operations at particular types 
are fairly complex.  I'd rather not add Haskell's type classes to
OCaml :-)

Another route is to attach the special equality operation to values of
the types of interest.  OCaml allows this for abstract types that are
implemented entirely in C, via the "custom block" mechanism, but not
currently for datatypes implemented in Caml, like the "num" type.

The example of "num" is particularly tricky, since it is not even an
abstract type, just a regular sum type with 3 constructors.  Hence,
even if custom blocks were extended to contain pointers back into the
Caml heap, it would still be hard to use them for representing values
of the "num" type.

One workaround would be to implement the "num" type entirely in C,
which is what the ML-GMP library does, I think.  Another would be to
keep "num" values normalized at all times, so that structural equality
coincides with numeric equality.  Both may entail performance
penalties in some cases, though.

> At present, I find that it's often quite inconvenient to use complicated
> structures involving abstract types. In particular, I use the type of
> arbitrary-precision numbers a lot, and frequently end up having to
> define variants of standard polymorphic operations like set union for
> several different types involving ":num".

Agreed.  In OCaml, sets are presented as a functor, so you can easily
pass a non-standard ordering function and you don't have to duplicate
the code implementing sets.  But you still have to define the ordering
functions, which can be a bit of a pain for complex data structures
containing nums.

Cheers,

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr