Hi,

I'd like here to present a problem that I think is fairly common (and
likely probably discussed) to have suggestions about what is the best
way to deal with it.

Let me start with a little story that happened to me recently.
Suppose one has a module A declaring an abstract type t and some
functions.  You are happy with the interface of A and have a working
implementation so you go on and write programs using A.  Later on, you
realize that you could improve A implementation by attaching
additional information to each variable of type t (this does not
change the interface of A).  Then all of a sudden, your programs
start to die with Out_of_memory exceptions...

The problem was that the attached information (an additional field in
a record) was a cyclic data structure.  From there on, all equality
tests became deadly! (I would have preferred to have the exception
Invalid_argument "equal: abstract value".)  What made matters worse is
that the compiler could not help me to find the locations of such
problems -- which can be hidden e.g. in List.mem.  Not a nice job to
do...

One may argue that its my fault: I should have declared from the start
a function

  val eq : t -> t -> bool

While that would have solved some of the problems I have, it would
have introduced new ones.  In particular, some functions relying on
equality couldn't be used anymore (but, again, without the compiler
helping to fund them).  An example is List.mem.  Of course, there is
List.exists to achieve the same goal but maybe one uses a library
declaring internally

  type 'a s = X | Y of 'a

and using equality on values of type ['a s] (here the default
structural equality is arguably what we want).  You may not even be
aware that the library does so if you did not write it.  However, for
values of type [t s] on needs a special equality...  which in practice
precludes the use of this library!

Here one sees that the problems with equality stand in the way of
abstraction and code reusability.

Now the questions are:

* Is there a solution in the current state of OCaml? (I'll be glad if
  there is.)

* If the first answer is "no", is there a medium term perspective to
  bring a solution to this problem?  I can see two:

  - one allows to redefine equality for new types, say with a syntax
    like

    type t = ... with compare x y = ...

    as this is already done for blocks with custom tags.  (BTW, why
    aren't Big_int such blocks with an appropriate compare?)

  - One introduces the same capability of providing a special equality
    (comparison) for certain types but, during compilation, "expand"
    functions till the type for "=" is given by known functions
    (something like a "generic" equality).  I guess however that that
    may cause problems with separate compilation...

I'll be glad to hear similar experiences and comments about the above
ideas.

Regards,
ChriS