From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <oliver@first.in-berlin.de>
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id E1351BC32
	for <caml-list@yquem.inria.fr>; Fri, 18 Mar 2005 00:47:33 +0100 (CET)
Received: from first.in-berlin.de (dialin-145-254-054-039.arcor-ip.net [145.254.54.39])
	by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2HNlWsI004200
	for <caml-list@yquem.inria.fr>; Fri, 18 Mar 2005 00:47:33 +0100
Received: by first.in-berlin.de (Postfix, from userid 501)
	id 6818CBD43D; Thu, 17 Mar 2005 22:41:13 +0100 (CET)
Date: Thu, 17 Mar 2005 22:41:13 +0100
From: Oliver Bandel <oliver@first.in-berlin.de>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] tail-recursion vs. no tail-recursion in list functions
Message-ID: <20050317214113.GC397@first.in-berlin.de>
References: <200503161951.48923.jon@ffconsultancy.com> <OF0054F385.DFC19FEB-ONC1256FC7.003D8A20-C1256FC7.003F728A@philips.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <OF0054F385.DFC19FEB-ONC1256FC7.003D8A20-C1256FC7.003F728A@philips.com>
User-Agent: Mutt/1.5.6i
X-Miltered: at concorde with ID 423A1714.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; oliver:01 bandel:01 oliver:01 in-berlin:01 caml-list:01 rec:01 recursion:01 heap:01 stack:01 recursion:01 imho:01 ...:98 ...:98 wrote: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: 

On Thu, Mar 17, 2005 at 12:31:57PM +0100, sebastian.egner@philips.com wrote:
> Just to chime in on this...
> 
> Did anybody every consider the following simple solution for the 'map' 
> problem?
> 
> 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.

Better use the match on limit and then call one of the
functions (which both are without a limit-incrementor).

BTW: As stated out by other people, the needed limit can vary.
     so it should be possible to give it as argument (at least
     as an optional value).


Ciao,
   Oliver