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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id E89D2BB81 for ; Mon, 13 Feb 2006 03:47:08 +0100 (CET) Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.199]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1D2l8iu021302 for ; Mon, 13 Feb 2006 03:47:08 +0100 Received: by wproxy.gmail.com with SMTP id 69so305400wri for ; Sun, 12 Feb 2006 18:47:07 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=aIgR10vZwPaU9/JEsBEFdME0D0i2IU6reiDrnUz/oVxNkMbg1FYIAFTrslJcemtiu22WiE0Er5yPIHQPYOD5z6KeqxAD1KhRl3tNLHpBa6Wy2t56mS0cCBbvildJBHaizyiC25Gm9jBcggHJdllxx0gRhzsmfw7TwlLj9H3dsz0= Received: by 10.65.230.17 with SMTP id h17mr749978qbr; Sun, 12 Feb 2006 18:47:07 -0800 (PST) Received: by 10.65.35.3 with HTTP; Sun, 12 Feb 2006 18:47:07 -0800 (PST) Message-ID: Date: Mon, 13 Feb 2006 15:47:07 +1300 From: Jonathan Roewen To: skaller Subject: Re: [Caml-list] HOFs, recursion, and being tail-rec... Cc: caml-list@yquem.inria.fr In-Reply-To: <1139796314.8591.79.camel@rosella.wigram> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <20060213.085348.126575598.garrigue@math.nagoya-u.ac.jp> <1139796314.8591.79.camel@rosella.wigram> X-Miltered: at nez-perce with ID 43EFF32C.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 hofs:01 recursion:01 hofs:01 compiler:01 exists:01 exists:01 btw:02 tree:02 tree:02 linear:02 linear:02 construct:02 sentence:04 indeed:05 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled version=3.0.3 > So it isn't a well formed sentence to say depth first > search cannot be tail-rec, it is easy to construct a > depth first search in any FPL that is. > > However, no matter what you do, you will indeed need > memory linear in the tree depth (unless it is 1-ary tree as > pointed out). Yes, but tail-rec would mean the function call trace does not use memory linear in the tree depth, which would be a positive optimisation. BTW: the memory linear to the tree depth is used in the list passed to search, 'visited'. I'm just wondering if using List.exists and HOFs prevents the compiler from generating tail-rec code (I presume that List.exists is already tail-rec). As it wouldn't be hard to make it tail-rec I'd imagine.. Jonathan