brogoff@speakeasy.net wrote:
> On Tue, 29 Oct 2002, Pierre Weis wrote:

>>We thus may need a deeper equality to test graph equivalence! (You can
>>argue that = could behave like that, but this is not easy to implement
>>efficiently.)
>>
>>Since this new predicate is inherently costy (we need to keep track of
>>all already visited nodes), a longer name reminiscent of its equality
>>semantics could be ``===''.
> 
> 
> I hadn't thought of that, and I'm not even sure if you're just pulling my leg, 
> but it's a good argument anyways. Is this an abstract point, or has anyone 
> really needed a graph equivalence test over recursively defiend values in 
> practice? 
> 
> -- Brian

I have a case where I actually need to test for structural 
equality over cyclic data structures--essentially top-down 
trees, with an upward link from nodes to their parents. 
These structures are necessary whenever the tree traversal 
starting point can be any node in the structure. This 
happens, for example, when you import a relational database 
and model foreign key fields with actual references between 
records.

Of course, it is fairly easy to devise a specific equality 
test for such cases, but, in general, one such equality 
function is needed for every datatype appearing in the 
graph. This can get painful if the number of different 
datatypes (tables) gets large. In such cases a "graph 
equivalence" operator would be a useful bonus. Still, I 
don't think this is a major issue with O'Caml.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners