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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 6CBBEBBAF; Mon, 2 Nov 2009 21:04:40 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkoDAIfJ7krBMHhLhWdsb2JhbACPfYtZAQEBCgsKBRXAe4Q8BA X-IronPort-AV: E=Sophos;i="4.44,669,1249250400"; d="asc'?scan'208";a="37424106" Received: from net.univ-savoie.fr ([193.48.120.75]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/EDH-RSA-DES-CBC3-SHA; 02 Nov 2009 21:04:39 +0100 Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by net.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id nA2K4Wpk030798 ; Mon, 2 Nov 2009 21:04:32 +0100 Received: from [193.48.123.45] (d45.lama.univ-savoie.fr [193.48.123.45]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id nA2K4UYp014287 ; Mon, 2 Nov 2009 21:04:31 +0100 Message-ID: <4AEF3B55.2060604@univ-savoie.fr> Date: Mon, 02 Nov 2009 21:04:37 +0100 From: Christophe Raffalli User-Agent: Thunderbird 2.0.0.23 (X11/20090817) MIME-Version: 1.0 To: Julien Verlaguet Cc: Damien Doligez , OCaml List Subject: Re: [Caml-list] tip for tail recursive map References: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> In-Reply-To: X-Enigmail-Version: 0.95.7 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigE387060ABC6EE431A4AAB5B7" X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 recursive:01 cheers:01 damien:01 damien:01 recursive:01 ad-hoc:01 beginner's:01 ocaml:01 bug:01 beginner's:01 X-Attachments: type="application/pgp-signature" name="signature.asc" name="signature.asc" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigE387060ABC6EE431A4AAB5B7 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Julien Verlaguet a =E9crit : > Thanks for the tip ! >=20 > I used this trick on every function of the List module and didn't try t= o > 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 ? reverse the list before and then to a fold_left ? Cheers, Christophe >=20 > Thanks >=20 > 2009/11/2 Damien Doligez > >=20 >=20 > On 2009-10-23, at 21:55, pikatchou pokemon wrote: >=20 > 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: >=20 > let rec map k f =3D function > | [] -> k [] > | x :: rl -> map (fun res -> k ((f x) :: res)) f rl >=20 >=20 > You can do better with an ad-hoc encoding of the continuation > instead of using closures: >=20 >=20 > let rec map k f =3D function > | [] -> List.rev k > | x :: rl -> map (f x :: k) f rl > ;; >=20 > The memory footprint is smaller, and you spend much less time > invoking closures. >=20 > Note that I haven't bothered benchmarking these two functions. >=20 > -- Damien >=20 > _______________________________________________ > 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 >=20 >=20 >=20 > -----------------------------------------------------------------------= - >=20 > _______________________________________________ > 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 --=20 Christophe Raffalli Universite de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tel: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature. The public key is stored on www.keyserver.net --------------------------------------------- --------------enigE387060ABC6EE431A4AAB5B7 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkrvO1UACgkQi9jr/RgYAS6gbACgweoKaVETxTegrMIntyiPX5M2 VIcAoM81a01CmcZq4Ef/71QRrCgXikkp =Z9Qy -----END PGP SIGNATURE----- --------------enigE387060ABC6EE431A4AAB5B7--