Re: definition recursive de valeur

[rugger@cc.umanitoba.ca (Kip Rugger)]

>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