From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA09674; Tue, 29 Oct 2002 18:21:58 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA08708 for ; Tue, 29 Oct 2002 18:21:57 +0100 (MET) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from athlon.baretta.com ([62.211.4.217]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g9THLuD12589 for ; Tue, 29 Oct 2002 18:21:56 +0100 (MET) Received: from baretta.com (localhost.localdomain [127.0.0.1]) by athlon.baretta.com (Postfix) with ESMTP id 2D43F273CB; Tue, 29 Oct 2002 18:20:48 +0100 (CET) Message-ID: <3DBEC36F.3070802@baretta.com> Date: Tue, 29 Oct 2002 18:20:47 +0100 From: Alessandro Baretta Organization: Baretta srl -- www.baretta.com User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.1) Gecko/20020826 X-Accept-Language: it, en MIME-Version: 1.0 To: brogoff@speakeasy.net, ocaml Subject: Re: [Caml-list] CamlP4 Revised syntax comment References: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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