From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 5CE8D7FACD for ; Tue, 30 Sep 2014 08:29:12 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of goswin-v-b@web.de) identity=pra; client-ip=212.227.17.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of goswin-v-b@web.de designates 212.227.17.11 as permitted sender) identity=mailfrom; client-ip=212.227.17.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mout.web.de) identity=helo; client-ip=212.227.17.11; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="goswin-v-b@web.de"; x-sender="postmaster@mout.web.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlECAMdMKlTU4xELnGdsb2JhbABg0DqCUIMhAoENFgERAQEBAQEGDQkJFCyEBAEBBDo/EAsYCSUPBSghiDwBGLcnH4dWARePR1cHgy6BHQWdJ4c7E5F1gXGBQwEBAQ X-IPAS-Result: AlECAMdMKlTU4xELnGdsb2JhbABg0DqCUIMhAoENFgERAQEBAQEGDQkJFCyEBAEBBDo/EAsYCSUPBSghiDwBGLcnH4dWARePR1cHgy6BHQWdJ4c7E5F1gXGBQwEBAQ X-IronPort-AV: E=Sophos;i="5.04,625,1406584800"; d="scan'208";a="98540773" Received: from mout.web.de ([212.227.17.11]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 30 Sep 2014 08:29:12 +0200 Received: from frosties.localnet ([95.208.222.117]) by smtp.web.de (mrweb102) with ESMTPSA (Nemesis) id 0MYw1v-1XllEj3OD5-00Vegy; Tue, 30 Sep 2014 08:29:10 +0200 Received: from mrvn by frosties.localnet with local (Exim 4.82) (envelope-from ) id 1XYqvu-0000eL-0o; Tue, 30 Sep 2014 08:29:10 +0200 Date: Tue, 30 Sep 2014 08:29:09 +0200 From: Goswin von Brederlow To: Pierre Chambart Cc: caml-list@inria.fr Message-ID: <20140930062909.GA2383@frosties> References: <20140929120817.GB20628@frosties> <54296663.8080902@laposte.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <54296663.8080902@laposte.net> User-Agent: Mutt/1.5.23 (2014-03-12) X-Provags-ID: V03:K0:LtZ/bWHP9chJKBW3xnfhZP07TjnPZx1nsff98+m80NmXjRAYph3 bhNcKnpsl2j1PcFk8cLiG36jQ1omXuemVlES3TQIPVDZsR+ZQMqDnfXSNAsDp0C7k8IczG/ ZInjbYqRthoxeErP0ywD/wR4PabQlHIjIjElT7Rheimhh3tVvu+L5H+2J9IBKTZraiHfBYO 1ZuFtIswT1v9bYjviilBQ== X-UI-Out-Filterresults: notjunk:1; Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? On Mon, Sep 29, 2014 at 04:02:11PM +0200, Pierre Chambart wrote: > On 29/09/2014 14:08, Goswin von Brederlow wrote: > > And I'll will do the same, reply anyway. > > > > You can't write List.map tail recursive unless: > > > > 1) You use List.rev (List.rev_map fn list). > > > > or > > > > 2) Use hacks to create a mutable list so you can grow it head to tail > > instead of tail to head. > > > > The fastest code seems to be when you do List.map recursively up to > > some limit (say 1000 items) and return the remainder. Repeat and glue > > the lists together into one large list using hacks. > > > > MfG > > Mrvn > > > Please, don't do that hack ! The compiler assumes immutable data are not > mutated and optimise knowing that. > -- > Pierre > I didn't describe the hack. The hack would be to build the result as mutable list (so the compiler uses write barriers when mutating and such). But you only mutate once every 1000 items so the cost is minimal. And at the end you cast the mutable list to an immutable list (the actual list type). While still a huge hack I believe going from mutable to immutable is safe. MfG Goswin