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 LAA32462; Mon, 11 Oct 2004 11:04:41 +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 LAA32348 for ; Mon, 11 Oct 2004 11:04:40 +0200 (MET DST) Received: from mta1.cl.cam.ac.uk (mta1.cl.cam.ac.uk [128.232.0.15]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i9B94eMd015779 for ; Mon, 11 Oct 2004 11:04:40 +0200 Received: from zonule.cl.cam.ac.uk ([128.232.9.23] helo=cl.cam.ac.uk ident=[A54oU28okynyjKDphgk9N9KEhsqga9s0]) by mta1.cl.cam.ac.uk with esmtp (Exim 3.092 #1) id 1CGw6f-0003Ec-00; Mon, 11 Oct 2004 10:04:37 +0100 X-Mailer: exmh version 2.6.3-CL 04/04/2003 with nmh-1.0.4 X-Exmh-Isig-CompType: repl X-Exmh-Isig-Folder: inbox To: Brian Hurt cc: Luca Pascali , caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists In-reply-to: Your message of "Sun, 10 Oct 2004 19:44:25 CDT." Mime-Version: 1.0 Content-Type: text/plain Date: Mon, 11 Oct 2004 10:04:36 +0100 From: Keith Wansbrough Message-Id: X-Miltered: at nez-perce with ID 416A4CA8.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 circular:03 circular:03 wrote:03 algorithm:03 recursive:03 oct:03 let:04 pointed:04 detect:06 quite:06 fri:07 fold:07 lists:91 lists:91 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > On Fri, 8 Oct 2004, 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. > > You can detect circular lists in O(N) thusly: > > let is_circular lst = Yes, of course (and this is quite neat - I knew there was a reasonable-space algorithm but couldn't recall it off the top of my head). But this is hardly something you want built into List.map and List.fold_{left,right}. (as others have pointed out) --KW 8-) ------------------- 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