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 QAA19345; Fri, 8 Oct 2004 16:41:19 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA19334 for ; Fri, 8 Oct 2004 16:41:18 +0200 (MET DST) Received: from alex.barettalocal.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i98EfHed032098 for ; Fri, 8 Oct 2004 16:41:17 +0200 Received: from [127.0.0.1] (localhost.localdomain [127.0.0.1]) by alex.barettalocal.com (Postfix) with ESMTP id 70324F386A; Fri, 8 Oct 2004 16:42:45 +0200 (CEST) Message-ID: <4166A764.3010905@baretta.com> Date: Fri, 08 Oct 2004 16:42:44 +0200 From: Alex Baretta User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.3) Gecko/20040913 X-Accept-Language: it, en-us, en MIME-Version: 1.0 To: Keith Wansbrough Cc: Luca Pascali , caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4166A70D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; baretta:01 baretta:01 caml-list:01 cyclic:01 cyclic:01 decidable:01 tails:01 model:01 model:01 modelling:01 modelled:01 ocaml:01 caml:01 equality:01 equality:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Keith Wansbrough wrote: > > How could they do this? It's just a list; there's nothing special > about it, except that it has no end. Lists can be recursive. This means that the list type models a set of values which includes the cyclic lists. The ocaml type system allow both for such values and for functions manipulating them, so it's perfectly natural to expect the List module to treat cyclic lists correctly. Besides, the cyclicity of a list is a perfectly decidable property by virtue of the pumping lemma. > You might be able to do it by keeping a list of all the nodes you've > visited, and using physical equality to check if you have already > visited a node. Good point; however, we must keep a list of tails of visited nodes. Physical equality of nodes is a necessary but insufficient condition for recursiveness. On the other hand, if two nodes of the list have the same tail, then we have proven that the list is cyclic. > But it would be better to design a more appropriate > data structure for your application, one for which such tricks are not > needed. There is no more appropriate data structure than a cyclic list to model a possibily infinite (cyclic) sequence of input data. Have you ever seen type schemas like the following: # type 'a t = 'a -> 'a t;; type 'a t = 'a -> 'a t This is a perfectly sensible use of recursive data structures: there is no other way to model a type whose expanded representation is infinite. type 'a t = 'a -> 'a -> 'a -> ... > What are you trying to do? We are modelling an optimization problem where a finite number of requests must be served, as efficiently as possible, from a possibly infinite set of instances of a finite number of classes of resources. Each resource class is modelled by a list element. The cyclicity of the resource list can be used to express no limits on the amount of resources available. Yet, the optimization program must know better than simply scan the list sequentially, or unsatisfiable constraint sets cannot be identified in finite time. Our algorithm works now, so we do not depend on the availability of cyclic-list aware standard library. We are simply trying to point out that the current List module is very naif about infinite lists. I would like to start a discussion as to whether the List module ought to correctly handle cyclic lists or not. 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. 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