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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 94528BBAF for ; Mon, 2 Nov 2009 20:56:18 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhACAJfI7kpKfU4ZkGdsb2JhbACCIzCNKoFtiS0/AQEBAQkJDAcTA7EwgTmFFYhoAQMDBYQ3BA X-IronPort-AV: E=Sophos;i="4.44,669,1249250400"; d="scan'208";a="36040208" Received: from ey-out-2122.google.com ([74.125.78.25]) by mail2-smtp-roc.national.inria.fr with ESMTP; 02 Nov 2009 20:56:18 +0100 Received: by ey-out-2122.google.com with SMTP id 22so1153400eye.31 for ; Mon, 02 Nov 2009 11:56:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type; bh=zTdbDsTm0vVKCzPFazivkS28Ehhov07AEr36hH6GkuM=; b=Bo8d883MSFUrw+zvENXGJBWCAKEMK5iE7kzFw33ycyfNg+/nFJzMi19kZlCXrqvgaK Gvges9kCKI1rt7lsblTnDCDyAFmBRI9N1t2bipNupUy1v/Sic7z4cq8LkF4Q2q+wv7Jx WlD05qE95vkdkQikc0lgKlyf5s2Fz0Bvh9Zwk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=VXdfVTtK3n2FCB4Ew59nuMgvt71uIkE0KeNWpYYNKOtwdNdY9oCSlKfHIGoP2lWknq NPEnGohKOfi2QqRsAt1Np87E/7z8+MhDIsZffushDc43jbYZ1fdkZmUpQPGaOVaq7bU/ lDh2CEMIAsP3OSqQzJMLQu9nNH1bIIN4Pl51Y= MIME-Version: 1.0 Received: by 10.216.85.132 with SMTP id u4mr5342501wee.191.1257191777807; Mon, 02 Nov 2009 11:56:17 -0800 (PST) In-Reply-To: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> References: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> Date: Mon, 2 Nov 2009 12:56:17 -0700 Message-ID: Subject: Re: [Caml-list] tip for tail recursive map From: Julien Verlaguet To: Damien Doligez Cc: OCaml List Content-Type: multipart/alternative; boundary=0016e6d5669854b69c047768c5b8 X-Spam: no; 0.00; recursive:01 damien:01 damien:01 recursive:01 ad-hoc:01 beginner's:01 ocaml:01 bug:01 ad-hoc:01 beginner's:01 ocaml:01 bug:01 2009:98 2009:98 23,:98 --0016e6d5669854b69c047768c5b8 Content-Type: text/plain; charset=ISO-8859-1 Thanks for the tip ! I used this trick on every function of the List module and didn't try to go a step further in specific cases. Main problem being List.fold_right ... I couldn't figure out a way to encode a more efficient continuation encoding than the good old CPS, any ideas ? Thanks 2009/11/2 Damien Doligez > > 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 > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > --0016e6d5669854b69c047768c5b8 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Thanks for the tip !

I used this trick on every function of the List= module and didn't try to go a step further in specific cases.
Main = problem being List.fold_right ... I couldn't figure out a way to encode= a more efficient continuation encoding
than the good old CPS, any ideas ?

Thanks

2009/11/2 Damien Doligez <damien.doligez@inria.fr>

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 no= t 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 =3D function
=A0| [] =A0 =A0-> k []
=A0| 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 =3D function
=A0| [] -> List.rev k
=A0| 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

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.in= ria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

--0016e6d5669854b69c047768c5b8--