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 IAA28063; Mon, 11 Oct 2004 08:52:28 +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 IAA28056 for ; Mon, 11 Oct 2004 08:52:27 +0200 (MET DST) Received: from will.iki.fi (will.iki.fi [217.169.64.20]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i9B6qRvZ003671 for ; Mon, 11 Oct 2004 08:52:27 +0200 Received: from [10.0.20.56] (fa-3-0-0.fw.exomi.com [217.169.64.99]) by will.iki.fi (Postfix) with ESMTP id E2C2D18; Mon, 11 Oct 2004 09:52:26 +0300 (EEST) Message-ID: <416A2D98.8050604@exomi.com> Date: Mon, 11 Oct 2004 09:52:08 +0300 From: Ville-Pertti Keinonen User-Agent: Mozilla Thunderbird 0.7.3 (X11/20040828) X-Accept-Language: en-us, en MIME-Version: 1.0 To: William Lovas Cc: caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists References: <20041011063203.GA13870@force.stwing.upenn.edu> In-Reply-To: <20041011063203.GA13870@force.stwing.upenn.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 416A2DAB.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 lovas:01 2004:99 pointers:01 tails:01 circularity:01 implemented:01 bool:01 alex:01 rec:01 node:02 match:02 match:02 circular:03 circular:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk William Lovas wrote: >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 > > This can be fixed by comparing the list node pointers rather than the contents. I'm sure Brian meant the match in the above to look like: match p1, p2 with | (_ :: t1), (_ :: (_ :: t2) as p3) -> if p1 == p2 or p1 == p3 then true else loop t1 t2 | _ -> false >... and this isn't it :) I think Alex was more on the right track with the >idea of maintaining a list of tails... > > There's no need for such a thing, at least for determining circularity, the "tortoise and hare" algorithm is well-known and works just fine, as long as it's implemented correctly. ------------------- 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