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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 4C03FBBAF for ; Mon, 2 Nov 2009 11:33:31 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.44,665,1249250400"; d="scan'208";a="39354258" Received: from macabane.inria.fr ([128.93.8.160]) by mail1-relais-roc.national.inria.fr with ESMTP/TLS/AES128-SHA; 02 Nov 2009 11:33:31 +0100 Message-Id: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> From: Damien Doligez To: OCaml List In-Reply-To: Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v936) Subject: Re: [Caml-list] tip for tail recursive map Date: Mon, 2 Nov 2009 11:33:30 +0100 References: X-Mailer: Apple Mail (2.936) X-Spam: no; 0.00; damien:01 damien:01 recursive:01 recursive:01 ad-hoc:01 2009:98 23,:98 doligez:01 doligez:01 closures:01 closures:01 wrote:01 rec:01 rec:01 caml-list:01 On 2009-10-23, at 21:55, pikatchou pokemon wrote: > I know this topic has been discussed several times, but I don't > think I have seen the solution I use for functions of the List > module which are not tail recursive. > I thought sharing the tip could be nice. > I will take an example, List.map. > When rewritten in CPS map becomes: > > let rec map k f = function > | [] -> k [] > | x :: rl -> map (fun res -> k ((f x) :: res)) f rl You can do better with an ad-hoc encoding of the continuation instead of using closures: let rec map k f = function | [] -> List.rev k | x :: rl -> map (f x :: k) f rl ;; The memory footprint is smaller, and you spend much less time invoking closures. Note that I haven't bothered benchmarking these two functions. -- Damien