Message-Id: <m0tu4NT-0007ILC@rugger.nodomain.ca>
Date: Tue, 5 Mar 96 15:34 CST
From: rugger@cc.umanitoba.ca (Kip Rugger)
To: caml-list@pauillac.inria.fr
Subject: Re: definition recursive de valeur
>As you may know, Caml offers two polymorphic predicates to compare
>values, that is == (physical identity) and = (re'cursive descent into
>values to find differences). None of these is the mathematical
>equality, except for some basic data types such that integers. In the
>library of the Caml V3.1 system, we have a third ``equal''
>predicate that ``Compare graphs''. Unfortunately this ``equal''
>predicate is hard to implement efficiently, is highly not portable,
>and moreover was found not very useful in practice: when people need
>such a sophisticated predicate, they need a complex semantic equality,
>upto some equivalence relationship, this predicate by no means
>correspond to ``equal'', so that they must write the predicate by themselves.
>Pierre Weis
The ``equal'' predicate does suggest an implementation using mark bits
in the data structure, making it not portable. The only portable
algorithm that I know is as follows (in pseudo C code):
if ( {terminal case} ) ...
if ( *p == *q ) return true;
save( p, *p );
t = *p, *p = *q;
return compare( t, *q );
so given the initial conditions:
p --> x = 1 :: y
q --> y = 1 :: x
this is reduced after one iteration to:
q --> x = 1 :: x
p --> y = 1 :: x
from which equality follows. Unfortunately, both data structures are
potentially destroyed in the process, making it necessary to save and
restore the modifications on a stack.
I agree that ``equal'' is of limited use, even if it could handle
cyclical structures. It is usually better to build unique representations
of the underlying structures so that ``=='' can be used instead.
What is useful is a ``shallow equal'' which applies ``=='' to the top
level of a data structure. This allows easy comparison of records,
tuples, or arrays of scalar objects, as well as supplying the terminal
condition for recursive data structures.
Kip Rugger