From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id DDCACBBAF for ; Thu, 26 Mar 2009 15:59:32 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.38,426,1233529200"; d="scan'208";a="26383122" Received: from estephe.inria.fr ([128.93.11.95]) by mail1-relais-roc.national.inria.fr with ESMTP; 26 Mar 2009 15:59:32 +0100 Message-ID: <49CB9854.1020707@inria.fr> Date: Thu, 26 Mar 2009 15:59:32 +0100 From: Xavier Leroy User-Agent: Thunderbird 2.0.0.17 (X11/20080929) MIME-Version: 1.0 To: David.Bulone@ulp.u-strasbg.fr Cc: caml-list@inria.fr Subject: Re: [Caml-list] =?ISO-8859-1?Q?R=E9cursivit=E9_terminale?= References: <20090326153839.8kzcsd6k0sg0csoc@webmail.u-strasbg.fr> In-Reply-To: <20090326153839.8kzcsd6k0sg0csoc@webmail.u-strasbg.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Spam: no; 0.00; terminale:01 recursive:01 terminale:01 recursive:01 caml-list:01 functions:01 data:02 caml:02 rewritten:02 structures:02 parameter:02 complex:05 transform:05 accumulator:05 accumulator:05 > Je voudrais savoir s'il existait un moyen de transformer une fonction > récursive non terminale en fonction récursive terminale avec Caml. [ Translation: is there a way to transform a non-tail-recursive function into a tail-recursive function? ] A technique that always works is to convert your function to continuation-passing style. The resulting code is hard to read and not particularly efficient, though. It is possible to do better in a number of specific cases. Functions operating over lists can often be made tail-rec by adding an "accumulator" parameter and reversing the accumulator at the end. For instance, List.map f l (not tail-rec) can be rewritten as List.rev (List.rev_map f l) (tail-rec). For more complex data structures than lists, Huet's zippers can often be used for the same purpose. Happy Googling, - Xavier Leroy