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 RAA21462; Fri, 8 Oct 2004 17:13:55 +0200 (MET DST) 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 RAA21445 for ; Fri, 8 Oct 2004 17:13:54 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i98FDrPi032005 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 8 Oct 2004 17:13:54 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1CFwRM-0004rW-5f for caml-list@inria.fr; Fri, 08 Oct 2004 15:13:52 +0000 From: Jon Harrop To: caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists Date: Fri, 8 Oct 2004 16:09:30 +0100 User-Agent: KMail/1.6.2 References: <41669437.3010201@yahoo.it> <41669EAA.7000509@tni-software.com> <4166A7E3.6010908@baretta.com> In-Reply-To: <4166A7E3.6010908@baretta.com> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200410081609.30732.jon@jdh30.plus.com> X-Miltered: at nez-perce with ID 4166AEB1.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 44,:01 baretta:01 cyclic:01 cyclic:01 slower:01 non-cyclic:01 caml:01 equality:01 imho:01 alex:01 lazy:02 complexity:02 nodes:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Friday 08 October 2004 15:44, Alex Baretta wrote: > Lazy lists or streams are not good enough in the general scenario. We > don't need to exhaustively explore the cyclic data structures. Yes. > The > properties we are interested in can be proven in finite time by > analyzing the list structure with the physical equality operator. No. I think you'll want "physical comparison operators" to do this efficiently, e.g. to build a set of visited nodes, otherwise you'll have to loop through all the possible ones giving you a search complexity of O(n) instead of O(ln n). As "physical comparison operators" don't exist, I think you'd be better off using a directed cyclic graph with the notion of "physical" replaced with a notion of "index", so you number the nodes. Then you can build a set of visited nodes and search it to check for cyclic bits. > I argue that since they are > legimitate citizens of the language, the standard library should handle > them correctly. We are willing to contribute our code, so that this > might not weigh on the Caml breeders. IMHO, this should certainly not go in the core library. These functions are much more specialised that the current code and are likely to be significantly slower. Perhaps the library documentation should state which functions assume a non-cyclic list. Also, I'd be surprised if the required functionality didn't already exist in a graph library, although perhaps not specialized to one root and one edge out of each vertex. Cheers, Jon. ------------------- 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