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 6A8187FACD for ; Mon, 29 Sep 2014 17:44:39 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of yminsky@janestreet.com) identity=pra; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="yminsky@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of yminsky@janestreet.com designates 38.105.200.229 as permitted sender) identity=mailfrom; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="yminsky@janestreet.com"; 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@mxout3.mail.janestreet.com) identity=helo; client-ip=38.105.200.229; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="postmaster@mxout3.mail.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: As4BAM99KVQmacjlnGdsb2JhbABgg2FXBIJ9tg2RCodOAoEKCBYBEQEBAQEBCBQJQIQEAQEEEhEdAQEsCwEPCwsNAgIJHQICIhIBBQEKEgYTEhCICAMRAwqdPW6KOHiFAgEFiS4DEIcGAREGCoEijhtXB4J4gVOFGQWRBocJgWKFcIwZGCmFMFCBB4FDAQEB X-IPAS-Result: As4BAM99KVQmacjlnGdsb2JhbABgg2FXBIJ9tg2RCodOAoEKCBYBEQEBAQEBCBQJQIQEAQEEEhEdAQEsCwEPCwsNAgIJHQICIhIBBQEKEgYTEhCICAMRAwqdPW6KOHiFAgEFiS4DEIcGAREGCoEijhtXB4J4gVOFGQWRBocJgWKFcIwZGCmFMFCBB4FDAQEB X-IronPort-AV: E=Sophos;i="5.04,620,1406584800"; d="scan'208";a="98461107" Received: from mxout3.mail.janestreet.com ([38.105.200.229]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 29 Sep 2014 17:44:38 +0200 Received: from tot-oib-smtp1 ([172.27.22.15] helo=tot-smtp) by mxout3.mail.janestreet.com with esmtps (UNKNOWN:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.82) (envelope-from ) id 1XYd7s-0003Lm-HA for caml-list@inria.fr; Mon, 29 Sep 2014 11:44:36 -0400 Received: from [172.27.229.230] (helo=mxgoog1.mail.janestreet.com) by tot-smtp with esmtps (UNKNOWN:AES256-GCM-SHA384:256) (Exim 4.72) (envelope-from ) id 1XYd7s-000834-EL for caml-list@inria.fr; Mon, 29 Sep 2014 11:44:36 -0400 Received: from mail-la0-f41.google.com ([209.85.215.41]) by mxgoog1.mail.janestreet.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.72) (envelope-from ) id 1XYd7s-0001ye-7c for caml-list@inria.fr; Mon, 29 Sep 2014 11:44:36 -0400 Received: by mail-la0-f41.google.com with SMTP id pn19so2987279lab.28 for ; Mon, 29 Sep 2014 08:44:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=/vDHfl/ZZ2urvNi/DtNcgfT5F703CGX0SGkoywD5t6I=; b=LAWbXYc1aP1UYX2uztF9B/REf7b2R71L821gBOYcyP/z72gE18gK0wB3V9Z0SfLwff 1NAemCkmUXz93RNBMVKYx5pWgG43JJI1yVslnr0Aes0KCs1TeqsZfu73D8gu8tb7CNFu aSqDyxgWflTcr5e8d/3hPA3vPxNjd2xt7RhPQ= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=/vDHfl/ZZ2urvNi/DtNcgfT5F703CGX0SGkoywD5t6I=; b=MwcyBAFXair/Dq4xYuEbhtbrld/PDaupNZ04quoJjuhWd+iOjEB6pK2Lb473moL9rk NiwQ8HSQbC0cOYJSoKowTnAIoacCwWHNEQpACfN3FZDD+x50qGrq/f1U4yNkBpqb76c6 rAFwakQoqSTkqNNsqMA+Ba6Ts9mKEqT16lJophklOsPQTkfKLDz+d/yDBneUznmzNNNx Cgo4oVu8IZcw2icsNu/n7VxBhYJCi6vu9eUXGn/ZKak4YiEVHv5/qGDXzXmvU8mHB/JH RlZs8FYtpddPrQVRI8t7cE1to/47gWwNHhd/QtjCZmn0pxncMAsmi/yj+9BsEh1hTYeX zsxA== X-Gm-Message-State: ALoCoQmUhKr3oSmxTWEyS9dBJqYH/JVJmpigY8Kf56uPsO9zMYlPvxWIkjdVy1uoyoYQUlDFwWKurLYQIXkFgEvla7YaMmgQCJTTATR3jniC274DznxouPVxeKstdobRqYVNdOSixYo8 X-Received: by 10.152.87.193 with SMTP id ba1mr10726074lab.83.1412005475115; Mon, 29 Sep 2014 08:44:35 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.152.87.193 with SMTP id ba1mr10726063lab.83.1412005475031; Mon, 29 Sep 2014 08:44:35 -0700 (PDT) Received: by 10.112.56.136 with HTTP; Mon, 29 Sep 2014 08:44:34 -0700 (PDT) In-Reply-To: <54296663.8080902@laposte.net> References: <20140929120817.GB20628@frosties> <54296663.8080902@laposte.net> Date: Mon, 29 Sep 2014 11:44:34 -0400 Message-ID: From: Yaron Minsky To: Pierre Chambart Cc: Goswin von Brederlow , "caml-list@inria.fr" Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively? Agreed. To be clear, there's a "hack" in Core_kernel's List module that does more or less what is described, but the gluing together isn't hacky, i.e., uses no Obj.magic and no mutation. It's both fast for short lists and doesn't blow the stack for long lists. y On Mon, Sep 29, 2014 at 10:02 AM, 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 > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs