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 NAA01384; Wed, 13 Oct 2004 13:41:27 +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 NAA01556 for ; Wed, 13 Oct 2004 13:41:26 +0200 (MET DST) Received: from alex.barettalocal.com (h213-255-109-130.albacom.net [213.255.109.130] (may be forged)) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i9DBfPmF009092 for ; Wed, 13 Oct 2004 13:41:26 +0200 Received: from [127.0.0.1] (localhost.localdomain [127.0.0.1]) by alex.barettalocal.com (Postfix) with ESMTP id 26FB92BAA5A; Wed, 13 Oct 2004 13:43:00 +0200 (CEST) Message-ID: <416D14C3.4030902@baretta.com> Date: Wed, 13 Oct 2004 13:42:59 +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: james woodyatt Cc: Caml List Subject: Re: [Caml-list] About Obj (was Recursive lists) References: <41669437.3010201@yahoo.it> <4166A395.70301@yahoo.fr> <4166DC42.3090602@baretta.com> <16746.15832.409677.764564@gargle.gargle.HOWL> <416A8CDA.7060407@univ-savoie.fr> <00F89380-1BA2-11D9-B4CE-000A958FF2FE@wetware.com> In-Reply-To: <00F89380-1BA2-11D9-B4CE-000A958FF2FE@wetware.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 416D1465.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 woodyatt:01 immutable:01 immutable:01 decidable:01 cyclic:01 abstraction:01 cyclic:01 abstraction:01 modeled:01 caml:01 mutable:01 mutable:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk james woodyatt wrote: me-now-or-pay-me-later sort of game you're playing here. > > Rather than whack on the immutable list, maybe you should consider doing > this: > > type 'a mlist = N | C of 'a mcell > and 'a mcell = { mutable cdr: 'a; mutable car: 'a mlist } > > No need to thank me. This point of view is simply wrong. We use immutable lists, which can be infinite. This data structure, or I should say this module interface, perfectly models our program's needs. However, as I discussed with Xavier, we must guarantee that the algorithm which scans this list will, at some point terminate, whether the list is finite or not. This can be done because cycle detection is decidable and it's complexity in realistic scenarios (ours, as far as I'm concerned) is O(1), the constant complexity being achieved through the tail-stacking algorithm which only stacks a small number of nodes, number which is indipendent of the problem size. The need for a List (or Cyclic_list) module encapsulating the abstraction of a cyclic list emerges when we try to build an input data-structure to feed our algorithm. The use of Obj within a specific module is perfectly acceptable so long as it is needed to implement functionality which cannot be achieved in the core language. The example of the tail recursive implementation of List.map is pertinent, and shows the point. You might have noticed that Caml breeders use Obj fairly liberally when it is needed to achieve a higher of abstraction which cannot be modeled in the core language. 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