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 RAA22850; Fri, 8 Oct 2004 17:43:56 +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 RAA22839 for ; Fri, 8 Oct 2004 17:43:54 +0200 (MET DST) Received: from mail.davidb.org (adsl-64-172-240-129.dsl.sndg02.pacbell.net [64.172.240.129]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i98Fhq9I008286 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 8 Oct 2004 17:43:54 +0200 Received: from davidb by mail.davidb.org with local (Exim 4.41 #1 (Debian)) id 1CFwuJ-0003iM-GV; Fri, 08 Oct 2004 08:43:47 -0700 Date: Fri, 8 Oct 2004 08:43:47 -0700 From: David Brown To: Alex Baretta Cc: Keith Wansbrough , Luca Pascali , caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists Message-ID: <20041008154347.GA14210@old.davidb.org> References: <4166A764.3010905@baretta.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4166A764.3010905@baretta.com> User-Agent: Mutt/1.5.6i X-Miltered: at concorde with ID 4166B5B8.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 caml-list:01 2004:99 baretta:01 cyclic:01 cyclic:01 decidable:01 ocaml:01 alex:01 0200,:01 module:03 overhead:03 dave:03 wrote:03 wrote:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, Oct 08, 2004 at 04:42:44PM +0200, Alex Baretta wrote: > 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. I doubt that most users of list operations want the extra overhead needed to check for cycles. Recursive lists are fairly rare in strict languages. Dave ------------------- 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