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 IAA27287; Mon, 11 Oct 2004 08:32:09 +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 IAA27193 for ; Mon, 11 Oct 2004 08:32:08 +0200 (MET DST) Received: from nexus.stwing.upenn.edu (NEXUS.STWING.UPENN.EDU [165.123.132.61]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i9B6W6aB029796 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Mon, 11 Oct 2004 08:32:08 +0200 Received: from force.stwing.upenn.edu (force.stwing.upenn.edu [165.123.132.65]) by nexus.stwing.upenn.edu (8.12.10/8.12.9) with ESMTP id i9B6W5HA021348 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Mon, 11 Oct 2004 02:32:06 -0400 (EDT) Received: from force.stwing.upenn.edu (localhost [127.0.0.1]) by force.stwing.upenn.edu (8.12.10/8.12.9) with ESMTP id i9B6W4h4029710 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 11 Oct 2004 02:32:05 -0400 (EDT) Received: (from wlovas@localhost) by force.stwing.upenn.edu (8.12.10/8.12.9/Submit) id i9B6W4eg029668 for caml-list@inria.fr; Mon, 11 Oct 2004 02:32:04 -0400 (EDT) Date: Mon, 11 Oct 2004 02:32:04 -0400 From: William Lovas To: caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists Message-ID: <20041011063203.GA13870@force.stwing.upenn.edu> Mail-Followup-To: caml-list@inria.fr References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.4i X-Miltered: at nez-perce with ID 416A28E6.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; lovas:01 wlovas:01 stwing:01 caml-list:01 2004:99 tails:01 bool:01 alex:01 rec:01 match:02 match:02 circular:03 circular:03 wrote:03 recursive:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote: > 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 > ;; # is_circular [true; true; true];; - : bool = true > [...] > > Note: I haven't tested the above functions, but they give you the idea of > how to handle circular lists. ... and this isn't it :) I think Alex was more on the right track with the idea of maintaining a list of tails... cheers, William ------------------- 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