From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 8EEC4BC32 for ; Fri, 18 Mar 2005 01:02:41 +0100 (CET) Received: from woodstock.1969.ws (64-215-156-42.eosinc.net [64.215.156.42]) by nez-perce.inria.fr (8.13.0/8.13.0) with SMTP id j2I02cN6017141 for ; Fri, 18 Mar 2005 01:02:40 +0100 Received: (qmail 17312 invoked from network); 18 Mar 2005 00:02:37 -0000 Received: from karl.1969.ws (HELO ?10.3.2.15?) (10.3.2.15) by woodstock.1969.ws with SMTP; 18 Mar 2005 00:02:37 -0000 Message-ID: <423A1B7D.3070301@1969.ws> Date: Thu, 17 Mar 2005 16:06:21 -0800 From: Karl Zilles Organization: 1969 Communications, Inc. User-Agent: Mozilla Thunderbird 1.0 (Windows/20041206) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Oliver Bandel Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] tail-recursion vs. no tail-recursion in list functions References: <200503161951.48923.jon@ffconsultancy.com> <20050317214113.GC397@first.in-berlin.de> In-Reply-To: <20050317214113.GC397@first.in-berlin.de> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 423A1A9E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 oliver:01 bandel:01 rec:01 recursion:01 heap:01 stack:01 recursion:01 imho:01 timings:01 ...:98 wrote:01 wrote:01 integer:01 integer:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.2 X-Spam-Level: Oliver Bandel wrote: > On Thu, Mar 17, 2005 at 12:31:57PM +0100, sebastian.egner@philips.com wrote: >>let unbreakable_map f xs = >> let rec >> map limit f xs = (* recursion depth limited to limit *) >> match xs with >> [] -> [] >> | x::xs when limit > 0 -> let f_x = f x in f_x::(map (limit-1) f >>xs) >> | _ -> List.rev_append (List.rev_map f xs) [] >> in map 512 f xs;; >> >>The function is not tail-recursive for lists of length up to 512---at >>which point it >>switches to a tail-recursive algorithm and uses the heap instead of the >>stack >>to keep track of structural recursion. > > IMHO this does not makes sense. > Better checking listlength with List.length and then calling the > needed function directly. > Why using an integer counter... this introduces overhead. Well, if you use List.length, then you're running an integer counter over the entire length of the list. His way, you only count the first 512 items. However, given the weird benchmark timings, God knows which would be faster :)