From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.6.10/8.6.6) id MAA02279 for caml-redistribution; Wed, 6 Mar 1996 12:29:26 +0100
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.6.10/8.6.6) with ESMTP id AAA23771 for <caml-list@pauillac.inria.fr>; Wed, 6 Mar 1996 00:08:29 +0100
Received: from rugger.nodomain.ca (dyn3-297.cc.umanitoba.ca [130.179.233.42]) by concorde.inria.fr (8.7.1/8.7.1) with SMTP id AAA29552 for <caml-list@pauillac.inria.fr>; Wed, 6 Mar 1996 00:08:13 +0100 (MET)
Received: by rugger.nodomain.ca (Smail3.1.28.1 #3)
	id m0tu4NT-0007ILC; Tue, 5 Mar 96 15:34 CST
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
Cc: rugger@cc.umanitoba.ca
Sender: weis


>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