Re: definition recursive de valeur
 rugger@c...
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  rugger@c... 
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