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 RAA29130; Tue, 12 Oct 2004 17:20:00 +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 RAA29214 for ; Tue, 12 Oct 2004 17:19:59 +0200 (MET DST) Received: from smtp.cegetel.net (mf00.sitadelle.com [212.94.174.77]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i9CFJwKa019445 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Tue, 12 Oct 2004 17:19:59 +0200 Received: from univ-savoie.fr (unknown [80.125.86.209]) by smtp.cegetel.net (Postfix) with ESMTP id 3A27067149; Tue, 12 Oct 2004 17:19:57 +0200 (CEST) Message-ID: <416BF61C.1040702@univ-savoie.fr> Date: Tue, 12 Oct 2004 17:19:56 +0200 From: Christophe Raffalli User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040115 X-Accept-Language: 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> X-Enigmail-Version: 0.83.3.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Miltered: at nez-perce with ID 416BF61E.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; raffalli:01 raffalli:01 univ-savoie:01 caml-list:01 woodyatt:01 38,:01 filliatre:01 sensibly:01 immutable:01 immutable:01 indirection:01 slower:01 savoie:01 chablais:01 73376:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk james woodyatt wrote: > On 11 Oct 2004, at 06:38, Christophe Raffalli wrote: > >> Jean-Christophe Filliatre wrote [quite sensibly]: >> >>> >>> [...] >>> This shouldn't be advised, and not even posted on this list. >> >> >> And how do you write a tail recursive map doing only one structure >> traversal (which is important with the penalty for memory access) on >> immutable list without the Obj module ? > > > By using a more appropriate data structure, e.g. a lazy list. It's a > pay-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 } This data structure uses 5 words and 2 indirection per cons cell (instead of 3 and 1 for standard list). So it will be slower on all operations. Moreover you may want immutable list with tail recursive and one mono-traversal map and fold_right. -- Christophe Raffalli Université de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tél: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature --------------------------------------------- ------------------- 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