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 CAA17724; Mon, 11 Oct 2004 02:36:16 +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 CAA17732 for ; Mon, 11 Oct 2004 02:36:15 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i9B0aDrw027474 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Mon, 11 Oct 2004 02:36:14 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.13.1/8.12.11) with ESMTP id i9B0a6Ru007066 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sun, 10 Oct 2004 19:36:09 -0500 (CDT) Date: Sun, 10 Oct 2004 19:44:25 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Keith Wansbrough cc: Luca Pascali , Subject: Re: [Caml-list] Recursive lists In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 4169D57D.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 buffer:01 elem:01 rec:01 rec:01 exists:01 overflow:02 match:02 match:02 circular:03 circular:03 wrote:03 recursive:03 recursive:03 oct:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Sorry for the late reply. On Fri, 8 Oct 2004, Keith Wansbrough wrote: > > > Can some functions of the List library support the use of the recursive > > lists? > > I mean: can some scanning functions such as map, for_all, exists, mem, > > filter, and so on understand if they are working on recursive lists and > > act correctly without going in buffer overflow or infinite loops? > > How could they do this? It's just a list; there's nothing special > about it, except that it has no end. You can detect circular lists in O(N) thusly: let is_circular lst = let rec loop p1 p2 = match p1, p2 with | (a :: t1), (b :: c :: t2) -> if (a == b) || (a == c) then true else loop t1 t2 | _ -> false in match lst with | _ :: t -> loop lst t | [] -> false ;; let circular_part lst = let rec find_an_element p1 p2 = (* find an element in the circular part of the list *) match p1, p2 with | (a :: t1), (b :: c :: t2) -> if (a == b) || (a == b) then p1 else find_and_element t1 t2 | _ -> [] in let find_circular_length lst = (* find the number of elements in the circular part of the list *) let rec loop c p = if lst == p then c else match p with | _ :: t -> loop (c+1) t | [] -> 0 in match lst with | _ :: t -> loop 1 t | [] -> 0 in let rec nth_tail cnt lst = if cnt == 0 then lst else nth_tail (cnt-1) (List.tl lst) in let rec find_loop p1 p2 = if (p1 == p2) then p1 else find_loop (List.tl p1) (List.tl p2) in match lst with | [] -> [] | _ :: t -> match find_an_elem lst t with | [] -> [] | cirelem -> let cirlen = find_circular_length cirelem in let p = nth_tail cirlen lst in find_loop lst p ;; Note: I haven't tested the above functions, but they give you the idea of how to handle circular lists. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- 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