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 QAA29057; Thu, 30 Jan 2003 16:54:23 +0100 (MET) 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 QAA28860 for ; Thu, 30 Jan 2003 16:54:22 +0100 (MET) Received: from epexch01.qlogic.org ([63.170.40.3]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h0UFsKr06809 for ; Thu, 30 Jan 2003 16:54:21 +0100 (MET) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Thu, 30 Jan 2003 09:53:57 -0600 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Thu, 30 Jan 2003 09:53:57 -0600 Date: Thu, 30 Jan 2003 10:03:30 -0600 (CST) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: Christophe Raffalli cc: Ocaml Mailing List Subject: Re: [Caml-list] @, List.append, and tail recursion In-Reply-To: <3E38F6F6.7000206@univ-savoie.fr> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 30 Jan 2003 15:53:57.0673 (UTC) FILETIME=[CC75C990:01C2C877] Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, 30 Jan 2003, Christophe Raffalli wrote: > To compute append l1 l2 in a tail recursive way the only solution I see > (in a pure functionnal program) is to traverse l1 twice (to reverse it > first), which replaces using memory on the stack by using memory to > build an intermediate list (and this use more memory ?). In a purely functional way, yes. > > Usually in recursive program, when you limit youself to tail recursive > function, you have often to reverse list and lisp languages always > provide the rev_append function which is tail recursive and very often > what you need (often l1 is an accumulator and is naturaly reversed > compared with l2). This traverses the list twice, and worse yet, allocates the list twice (once backwards, once forwards). Which makes it slower than tail recursion. Actually, the data structures with a hole optimization is more general than even I was thinking of. Read the paper. > > May be rev_append could be added to the list module (despite the fact it > is trivial to write it yoursleft) ? Already there. I am, when I have the time, staring at the ocaml code generation code, trying to get my mind around it. I hope to eventually have something, but don't expect it soon. :-) Brian ------------------- 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