Re: [Caml-list] Type abstraction and (polymorphic) equality

[Jon Harrop <jon@ffconsultancy.com>]

On Wednesday 29 June 2005 01:31, Christophe TROESTLER wrote:
> One may argue that its my fault: I should have declared from the start
> a function
>
>   val eq : t -> t -> bool

Yes, if you're doing anything which you think may be extended later then I 
think it is a good idea to try to discipline yourself in this way (don't use 
built-in polymorphic equality).

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

I do not believe so. IIRC, SML has equality types to help with this problem.

> * 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?)

That looks lovely. Apparently a similar facility is available in Haskell. 
However, there are disadvantages. Unless you're doing whole-program 
compilation, you'll need to carry a compare function with every datum. That's 
a huge performance cost and it probably isn't too easy to optimise it away.

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

Yes. It seems that this kind of thing is best done by a MLton-like compiler. 
If this is a trade-off then I prefer OCaml's current position - MLton is an 
order of magnitude slower to compile small programs, no dynamic code loading, 
no marshalling etc.

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

I had a similar problem when I extended an AST type to include lazily 
evaluated information. I suddenly got comparisons raising "function type" 
exceptions everywhere. The best solution recommended to me was to temporarily 
replace "=" with my own monomorphic version. That's hardly elegant and only 
works well if you've only used "=" on the one type that you're interested in.

I was convinced that there must be a simpler solution to this problem, using a 
static checker. However, the more I looked into my seemingly great idea, the 
harder it got... :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Technical Presentation Software
http://www.ffconsultancy.com/products/presenta