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 NAA00900; Wed, 13 Oct 2004 13:28:14 +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 NAA00686 for ; Wed, 13 Oct 2004 13:28:13 +0200 (MET DST) Received: from alex.barettalocal.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i9DBSCCb014653 for ; Wed, 13 Oct 2004 13:28:12 +0200 Received: from [127.0.0.1] (localhost.localdomain [127.0.0.1]) by alex.barettalocal.com (Postfix) with ESMTP id 65FC32BAA5A for ; Wed, 13 Oct 2004 13:29:47 +0200 (CEST) Message-ID: <416D11AB.10503@baretta.com> Date: Wed, 13 Oct 2004 13:29:47 +0200 From: Alex Baretta User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.3) Gecko/20040913 X-Accept-Language: it, en-us, en MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] Recursive lists References: <20041011063203.GA13870@force.stwing.upenn.edu> <416A2D98.8050604@exomi.com> In-Reply-To: <416A2D98.8050604@exomi.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 416D114C.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; baretta:01 baretta:01 caml-list:01 lovas:01 2004:99 pointers:01 tails:01 circularity:01 implemented:01 monadic:01 tails:01 allocates:01 alex:01 alex:01 complexity:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Ville-Pertti Keinonen wrote: > William Lovas wrote: > >> On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote: >> > 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. You can't say that there is no need for it. Think of a monadic composition of this algorithm with a list traversal which actually gets some work done. The need to maintain the list of tails appears in this context, where I know that only *some tails* are worth stacking into the cycle detection list, depending on the result of processing the single node. Besides the tortoise and hare algorithm is not really any better than mine, at least in terms of asymptotic worst case complexity, except that it allocates less. Alex ------------------- 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