From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr 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 8D5EBBB81 for ; Sat, 3 Dec 2005 01:28:22 +0100 (CET) Received: from web30515.mail.mud.yahoo.com (web30515.mail.mud.yahoo.com [68.142.201.243]) by concorde.inria.fr (8.13.0/8.13.0) with SMTP id jB30SL0J013786 for ; Sat, 3 Dec 2005 01:28:22 +0100 Received: (qmail 44842 invoked by uid 60001); 3 Dec 2005 00:28:21 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:Received:Date:From:Subject:To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=N1XBUFeW/zE7ouwU6lalJOJ2eQkRBm0rEwavMbw+yuflwUWk8/DzY6idbRusOXq0RG6PSVkSYjg+wdUaOVEFR5EFSHbPOpEAbK94gi+Xr1hPHid9BGo0ba9EeLg2z79lSP66+5hz1+GNxqM1IEISu6JJIkOXlqxfhQPAbLxhndk= ; Message-ID: <20051203002821.44840.qmail@web30515.mail.mud.yahoo.com> Received: from [69.129.111.12] by web30515.mail.mud.yahoo.com via HTTP; Fri, 02 Dec 2005 16:28:21 PST Date: Fri, 2 Dec 2005 16:28:21 -0800 (PST) From: David Thomas Subject: Re: [Caml-list] Reporting on sucess/failure of tail recursion To: caml-list@yquem.inria.fr MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 4390E6A5.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursion:01 stack:01 recursive:01 wrote:01 sourceforge:01 tail:01 tail:01 explicitly:01 library:03 library:03 implies:04 implies:04 space:07 space:07 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.2 required=5.0 tests=FORGED_YAHOO_RCVD autolearn=disabled version=3.0.3 Particularly with respect to list operations, "non-tail-recursive" usually implies stack space used is O(n) to the length of the list, whereas "tail recursive" implies O(1). I, for one, would love to see these figures explicitly, instead. --- skaller wrote: > What needs to be documented for a library function is its > complexity (time/space etc). In this sense the documentation > of the C++ Standard Library should be taken as an examplar. __________________________________ Start your day with Yahoo! - Make it your home page! http://www.yahoo.com/r/hs